Question

link

Stats

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Solution

This is not an easy question, though it’s similar to the question “Merge Intervals”.

First code is my solution.

Second code is from this repo. This is only 1 iteration, but in 3 stages. First, add all intervals ahead of newInterval into ans. Second, merge anything that can be merged with newInterval, and add to ans. Third, add the rest of intervals into ans.

Third code is from this blog. It’s a very tricky solution.

My code

My code

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
public class Solution {
    public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
        if (intervals == null) {
            return null;
        }
        int p = 0;
        while (p < intervals.size() && intervals.get(p).start < newInterval.start) {
            p++;
        }
        intervals.add(p, newInterval);
        if (p > 0) {
            p--;
        }
        // start merging from (p)th element
        while (p < intervals.size() - 1) {
            if (intervals.get(p).end >= intervals.get(p + 1).start) {
                intervals.get(p).end = Math.max(intervals.get(p).end, intervals.get(p + 1).end);
                intervals.remove(p + 1);
            } else {
                p++;
            }
        }
        return intervals;
    }
}

Second code.

public ArrayList<Interval> insert(ArrayList<Interval> intervals, Interval newInterval) {
    ArrayList<Interval> re = new ArrayList<Interval>();
    int len = intervals.size();
    int i = 0;
    while (i < len) {
        Interval temp = intervals.get(i);
        if (temp.end < newInterval.start)
            re.add(temp);
        else if (temp.start > newInterval.end)
            break;
        else {
            newInterval.start = Math.min(temp.start, newInterval.start);
            newInterval.end = Math.max(temp.end, newInterval.end);
        }
        i++;
    }
    re.add(newInterval);
    while (i < len) {
        re.add(intervals.get(i));
        i++;
    }
    return re;
}

Third code, a popular solution. Very tricky and concise.

public ArrayList<Interval> insert(ArrayList<Interval> intervals, Interval newInterval) {
    ArrayList<Interval> result = new ArrayList<Interval>();
    for(Interval interval: intervals){
        if(interval.end < newInterval.start){
            result.add(interval);
        }else if(interval.start > newInterval.end){
            result.add(newInterval);
            newInterval = interval;        
        }else if(interval.end >= newInterval.start 
                || interval.start <= newInterval.end){
            newInterval = new Interval(
                Math.min(interval.start, newInterval.start), 
                Math.max(newInterval.end, interval.end));
        }
    }
    result.add(newInterval); 
    return result;
}

Question

link

Stats

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Solution

The idea of the solution is not difficult. First, sort the entire collection list by start time. Secondly, merge it.

The real difficult part is how to sort the collection.

We can of course do insertion sort, or binary insertion sort. However, from this article:

The straight insertion algorithm presented in the preceding section does a linear search to find the position in which to do the insertion. However, since the element is inserted into a sequence that is already sorted, we can use a binary search instead of a linear search. Whereas a linear search requires O(n) comparisons in the worst case, a binary search only requires O(logn) comparisons. Therefore, if the cost of a comparison is significant, the binary search may be preferred.

And from wikipedia:

If the cost of comparisons exceeds the cost of swaps, as is the case for example with string keys stored by reference or with human interaction (such as choosing one of a pair displayed side-by-side), then using binary insertion sort may yield better performance. Binary insertion sort employs a binary search to determine the correct location to insert new elements, and therefore performs ⌈log2(n)⌉ comparisons in the worst case, which is O(n log n). The algorithm as a whole still has a running time of O(n²) on average because of the series of swaps required for each insertion.

So insertion sort algorithm may not be the best choice for us!

A more popular solution is using Collection.sort function.

java.util.Collections

public static void sort(List list, Comparator<? super T> c)

Parameters: c

The comparator to determine the order of the list. A null value indicates that the elements' natural ordering should be used.

A new class that implements the Comparator interface is created, and inside there is compare(Interval, Interval) method. Here is one example of such solution.

The third solution is same as the second, but only different in implementing the comparator object. Note the following code from this blog:

Comparator intervalComperator = new Comparator(){ public int compare(Interval i1, Interval i2){ Integer i1St=i1.start; Integer i2St=i2.start; return i1St.compareTo(i2St); } };

Read 3 pieces of code below.

My code

insertion sort, then merge:

public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
    ArrayList<Interval> ans = new ArrayList<Interval>();
    int len = intervals.size();
    if (len == 0) return ans;
    ans.add(intervals.get(0));
    if (len == 1) return ans;
    // now intervals length is >= then 2
    if (intervals.get(0).start < intervals.get(1).start)
        ans.add(intervals.get(1));
    else ans.add(0, intervals.get(1));
    for (int i = 2; i < len; i++) {
        int cur = intervals.get(i).start;
        // now find number cur from ans<list>
        int left = 0, right = ans.size() - 1;
        while (right - left > 1) {
            int mid = (left + right) / 2;
            if (ans.get(mid).start < cur) left = mid;
            else right = mid;
        }
        // insert cur between left and right, unless:
        if (left == 0 && cur < ans.get(0).start)
            ans.add(0, intervals.get(i));
        else if (right == ans.size() - 1
                && cur > ans.get(ans.size() - 1).start)
            ans.add(intervals.get(i));
        else
            ans.add(right, intervals.get(i));
    }
    // now merge ans
    int k = 0;
    while (k < ans.size() - 1) {
        while (k < ans.size() - 1 && ans.get(k).end >= ans.get(k + 1).start) {
            ans.get(k).end = Math.max(ans.get(k).end, ans.get(k + 1).end);
            ans.remove(k + 1);
        }
        k++;
    }
    return ans;
}

Recommended solution. Creating a new Comparator class

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
public class Solution {
    public List<Interval> merge(List<Interval> intervals) {
        if (intervals == null || intervals.size() == 0) {
            return intervals;
        }
        Collections.sort(intervals, new IntervalComparator());
        int p = 0;
        // if p is the last element of the list, we should stop merging
        while (p < intervals.size() - 1) {
            // merge p with the next interval, if possible
            if (intervals.get(p).end >= intervals.get(p + 1).start) {
                intervals.get(p).end = Math.max(intervals.get(p).end, intervals.get(p + 1).end);
                intervals.remove(p + 1);
            } else {
                p++;
            }
        }
        return intervals;
    }

    class IntervalComparator implements Comparator<Interval> {
        public int compare(Interval a, Interval b) {
            return a.start - b.start;
        }
    }
}

Third solution, different way of writing Comparator.

public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
    if (intervals == null || intervals.size() < 2)
        return intervals;
    ArrayList<Interval> result = new ArrayList<Interval>();

    Comparator<Interval> intervalComperator = new Comparator<Interval>() {
        public int compare(Interval i1, Interval i2) {
            Integer i1St = i1.start;
            Integer i2St = i2.start;
            return i1St.compareTo(i2St);

        }
    };
    Collections.sort(intervals, intervalComperator);

    Interval current = intervals.get(0);
    int i = 1;
    while (i < intervals.size()) {
        Interval currentToCompare = intervals.get(i);
        if (current.end < currentToCompare.start) {
            result.add(current);
            current = currentToCompare;
        } else
            current.end = Math.max(current.end, currentToCompare.end);
        i++;
    }
    result.add(current);
    return result;
}

Question

link

[
 [ 1, 2, 3 ],
 [ 8, 9, 4 ],
 [ 7, 6, 5 ]
]

Stats

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

This question is basic mathematics. There is another similar question [LeetCode 54] Spiral Matrix.

The difficult part is writing the code.

My code

Updated on Oct 9th, 2014:

public int[][] generateMatrix(int n) {
    int small = 0;
    int large = n - 1;
    int num = 1;

    int[][] ans = new int[n][n];
    while (small < large) {
        for (int i = small; i < large; i++) {
            ans[small][i] = num++;
        }
        for (int i = small; i < large; i++) {
            ans[i][large] = num++;
        }
        for (int i = large; i > small; i--) {
            ans[large][i] = num++;
        }
        for (int i = large; i > small; i--) {
            ans[i][small] = num++;
        }
        small++;
        large--;
    }
    if (small == large) {
        ans[small][small] = num;
    }
    return ans;
}

Question

link

[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]

Stats

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

This question is basic mathematics. The difficulty is the coding part.

My code

public class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> ans = new ArrayList<Integer>();
        if (matrix == null || matrix.length == 0 
            || matrix[0] == null || matrix[0].length == 0) {
            return ans;
        }
        int m = matrix.length;
        int n = matrix[0].length;
        int a = 0;
        int b = 0;
        while (a < (m + 1) / 2 && b < (n + 1) / 2) {
            // special cases
            if (2 * a + 1 == m && 2 * b + 1 == n) {
                ans.add(matrix[a][b]);
                break;
            } else if (2 * a + 1 == m) {
                for (int j = b; j <= n - 1 - b; j++) {
                    ans.add(matrix[a][j]);
                }
                break;
            } else if (2 * b + 1 == n) {
                for (int i = a; i <= m - 1 - a; i++) {
                    ans.add(matrix[i][b]);
                }
                break;
            }
            // now is the general case
            // first horizontal row without last element
            for (int j = b; j < n - 1 - b; j++) {
                ans.add(matrix[a][j]);
            }
            // vertical column on right-hand side
            for (int i = a; i < m - 1 - a; i++) {
                ans.add(matrix[i][n - 1 - b]);
            }
            for (int j = n - 1 - b; j > b; j--) {
                ans.add(matrix[m - 1 - a][j]);
            }
            for (int i = m - 1 - a; i > a; i--) {
                ans.add(matrix[i][b]);
            }
            a++;
            b++;
        }
        return ans;
    }
}

Question

link

Stats

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Solution

I posted 2 solution by me. Second code is same as this guy’s code.

My code

Using global variable (similar to [LeetCode 51] N-Queens)

public class Solution {

    int total = 0;

    public int totalNQueens(int n) {
        if (n <= 0) {
            return 0;
        }
        int[] map = new int[n];
        helper(map, 0, n);
        return total;
    }

    private void helper(int[] map, int row, int n) {
        if (row == n) {
            total++;
            return;
        }
        for (int i = 0; i < n; i++) {
            map[row] = i;
            // check if map[row] conflicts with any row above
            boolean valid = true;
            for (int k = 0; k < row; k++) {
                if (Math.abs(map[k] - map[row]) == row - k || map[k] == map[row]) {
                    // not valid!
                    valid = false;
                    break;
                }
            }
            if (valid) {
                helper(map, row + 1, n);
            }
        }
    }
}

Without using global variable

public class Solution {
    public int totalNQueens(int n) {
        return solve(0, n, new int[n]);
    }

    private int solve(int cur, int n, int[] list) {
        if (cur == n) return 1;
        int ans = 0;
        for (int i = 0; i < n; i++) {
            boolean conflict = false;
            for (int j = 0; j < cur; j++)
                if (i == list[j] || cur - j == Math.abs(i - list[j]))
                    conflict = true;
            if (conflict) continue;
            list[cur] = i;
            ans += solve(cur + 1, n, list);
        }
        return ans;
    }
}

Question

link

[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]

Stats

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

This is one of the most classic problems of NP (to be precise, NP-hard).

A lot of NP problems are be solved using similar approach, for example: Sudoku, Combinations, Combination Sum, Permutation, Work Break II, Palindrome Partitioning…

I posted my code below. It is very standard solution.

Solution

My solution is similar to the one written in this post.

My code

public class Solution {
    public List<String[]> solveNQueens(int n) {
        List<String[]> ans = new ArrayList<String[]>();
        if (n <= 0) {
            return ans;
        }
        int[] map = new int[n];
        helper(ans, map, 0, n);
        return ans;
    }

    private void helper(List<String[]> ans, int[] map, int row, int n) {
        if (row == n) {
            ans.add(convert(map, n));
            return;
        }
        for (int i = 0; i < n; i++) {
            map[row] = i;
            // check if map[row] conflicts with any row above
            boolean valid = true;
            for (int k = 0; k < row; k++) {
                if (Math.abs(map[k] - map[row]) == row - k || map[k] == map[row]) {
                    // not valid!
                    valid = false;
                    break;
                }
            }
            if (valid) {
                helper(ans, map, row + 1, n);
            }
        }
    }

    private String[] convert(int[] map, int n) {
        String[] strs = new String[n];
        for (int i = 0; i < n; i++) {
            StringBuilder str = new StringBuilder();
            for (int a = 0; a < map[i]; a++) {
                str.append('.');
            }
            str.append('Q');
            for (int a = map[i] + 1; a < n; a++) {
                str.append('.');
            }
            strs[i] = str.toString();
        }
        return strs;
    }
}

Question

link

Stats

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Solution

This is a easy question.

My code

public class Solution {
    public int lengthOfLastWord(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        int p = s.length() - 1;
        while (p >= 0 && s.charAt(p) == ' ') {
            p--;
        }
        if (p == -1) {
            return 0;
        }
        int q = p;
        while (q >= 0 && s.charAt(q) != ' ') {
            q--;
        }
        return p - q;
    }
}

Question

link

Stats

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

This is a standard DP problem.

My code

public class Solution {
    public boolean canJump(int[] A) {
        if (A == null || A.length <= 1) {
            return true;
        }
        int len = A.length;
        int left = 0;
        int right = 0;
        while (left <= right && right < len -1) {
            right = Math.max(right, left + A[left]);
            left++;
        }
        return right >= len - 1;
    }
}

Question

link

'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "*") → true
isMatch("aa", "a*") → true
isMatch("ab", "?*") → true
isMatch("aab", "c*a*b") → false

Stats

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

This question is similar to “Regex Matching”, and in fact can be solved using similar (DFS recursion) approach. This blog has the best analysis and solutions.

The solution is DP. The equation is not very difficult to write, but keep in mind to check character count before entering the algorithm. Failing to do so results in TLE.

My code

public class Solution {
    public boolean isMatch(String s, String p) {
        if (s == null || p == null) {
            return true;
        }

        // pre-check
        int count = 0;
        for (int i = 0; i < p.length(); i++) {
            if (p.charAt(i)!='*') count++;
        }
        if(count > s.length()) {
            return false;  
        }
        // end of pre-check

        int m = s.length();
        int n = p.length();
        // note the order is n,m, 
        // cuz we match each chars of p with chars of s
        boolean[][] dp = new boolean[n + 1][m + 1];
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                if (i == 0 && j == 0) {
                    dp[i][j] = true;
                } else if (i == 0) {
                    dp[i][j] = false;
                } else if (j == 0) {
                    // there is a special case: ("", "*")
                    if (p.charAt(i - 1) == '*' && dp[i-1][j]) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = false;
                    }
                } else if (p.charAt(i - 1) != '*') {
                    if (dp[i-1][j-1]) {
                        if (p.charAt(i - 1) == '?' || p.charAt(i - 1) == s.charAt(j - 1)) {
                            // single char matches
                            dp[i][j] = true;
                        }
                    }
                } else {
                    // current char from p is a star
                    // find the first place at which p matches with s
                    int pos = 0;
                    while (pos <= m && !dp[i-1][pos]) {
                        pos++;
                    }
                    // starting from pos, all subsequent substring of s matches p
                    while (pos <= m) {
                        dp[i][pos++] = true;
                    }
                    // important to break the for loop here and do not check for row i any more
                    // this requires changing the nested loop to put j outside of i
                    // the execution time decrease from TLE/1800ms to 800ms by adding this line
                    break;
                    // this break finished off all check for row i, and i advance to next row
                }
            }
        }
        return dp[n][m];
    }
}

Question

link

Stats

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Solution

This question have many interesting solutions. The bottom line is solving in O(lgn) time.

First approach, we can keep cumulating power(x, 2 ^ n).

Second approach, divide and conquer which is explained in this blog and this code.

Read code below.

My code

code 1, divide and conquer

public class Solution {
    public double pow(double x, int n) {
        if (n == 0) {
            return 1;
        } else if (n < 0) {
            if (n == Integer.MIN_VALUE) {
                // since the negate of Integer.MIN_VALUE overflows... 
                return (1 / x) / pow(x, Integer.MAX_VALUE);
            } else {
                return 1 / pow(x, -1 * n);
            }
        } else if (n % 2 == 0) {
            return pow(x * x, n / 2);
        } else {
            return x * pow(x, n - 1);
        }
    }
}

code 2, divide and conquer

public double pow(double x, int n) {
    if (n < 0) return 1 / helper(x, 0-n);
    else return helper(x, n);
}

private double helper(double x, int n) {
    if (n == 0) return 1;
    double half = helper(x, n / 2);
    return n % 2 == 1 ? x * half * half : half * half;
}

code 3

public double pow(double x, int n) {
    if (n == 0) return 1;
    if (n == 2) return x * x;

    if (n % 2 == 0) return pow(pow(x, n / 2), 2);
    else if (n > 0) return x * pow(pow(x, n / 2), 2);
    else return 1 / x * pow(pow(x, n / 2), 2);
}