Posted on | In

Test cases

1
2
3
4
[[0,0]]
[[0,0,0],[0,1,0],[0,0,0]]
[[0,0,0,0],[0,1,0,0],[0,0,0,1],[0,0,0,0]]
[[0,0,0,0],[0,1,0,0],[0,0,0,1],[0,0,0,1]]

Solution 1: accepted 2ms

DP: do we really need to create another grid? Nope.
Time: O(mn)
Space: O(2mn) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
    if (obstacleGrid[0][0] == 1) return 0;
    int m = obstacleGrid[0].length;
    int n = obstacleGrid.length;
    int[][] dp = new int[m][n];
    for(int i = 0; i < m; i++) {
        for(int j = 0; j < n; j++) {
            if(i==0 && j == 0) { 
                dp[i][i] = 1;
            }
            else {
                if (obstacleGrid[j][i] == 1)
                    dp[i][j] = 0;
                else 
                    dp[i][j] = dp[Math.max(0, i-1)][j] + dp[i][Math.max(0, j-1)];
            }
        }
    }
    return dp[m-1][n-1];
}

Solution 2: accepted 2ms

Time: O(mn)
Space: O(mn) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int uniquePathsWithObstacles(int[][] input) {
    if (input[0][0] == 1) return 0;
    int m = input[0].length;
    int n = input.length;
    for(int i = 0; i < m; i++) {
        for(int j = 0; j < n; j++) {
            if(i == 0 && j == 0) 
                input[j][i] = 1;
            else
                input[j][i] = (input[j][i] == 1)? 0 : input[Math.max(0, j-1)][i] + input[j][Math.max(0, i-1)];
        }
    }
    return input[n-1][m-1];
}

Posted on | In

Solution 1: accepted 1ms

Two-dimension DP: For ways to current position, w(current), equals to ways to its top plus ways to its left, w(current) = w(top) + w(left).
Time: O(mn)
Space: O(mn) 

1
2
3
4
5
6
7
8
9
10
11
12
public int uniquePaths(int m, int n) {
      int[][] dp = new int[m][n];
      for(int i = 0; i < m; i++) {
          for(int j = 0; j < n; j++) {
              if(i==0 && j == 0) 
                  dp[i][i] = 1;
              else
                  dp[i][j] = dp[Math.max(0, i-1)][j] + dp[i][Math.max(0, j-1)];
          }
      }
      return dp[m-1][n-1];
}

Solution 2:

One-dimension DP.

Posted on | In

Solution 1: accepted 5ms

DP.
Time: O(n)
Space: O(n) (extra space 0)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {
    public int minPathSum(int[][] grid) { 
        for(int i = 0; i < grid.length; i++) {
            for(int j = 0; j < grid[0].length; j++) {
                if (i == 0 && j == 0) 
                    continue;
                else if (i == 0)
                    grid[i][j] = grid[i][j] + grid[i][j-1];
                else if (j == 0)
                    grid[i][j] = grid[i][j] + grid[i-1][j];
                else
                    grid[i][j] = grid[i][j] + Math.min(grid[i][j-1], grid[i-1][j]);
            }
        }
        return grid[grid.length-1][grid[0].length-1];
    }
}

Posted on | In

Solution 1: accepted 6%

Brute force with low efficiency.
Q: How to add a new digit at the beginning of an array efficiently? 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public class Solution {
    public int[] plusOne(int[] digits) {
        
        int len = digits.length;
        int tail = len - 1;
        
        // Increment the last digit
        digits[tail]++;
        
        // Check whether digits are carried over
        while (digits[tail] > 9 && tail > 0) {
            digits[tail] = 0;
            digits[tail - 1]++;
            tail -= 1;
        }
        
        // If the first number is incremented and cause a new digit at the beginning
        if (digits[0] > 9) {
            digits[0] = 0;
            int[] update = new int[len + 1];
            update[0] = 1;
            for (int i = 1; i < len + 1; i++) {
                update[i] = digits[i - 1];
            }
            return update;
        }
        
        return digits;
        
        
        
    }    
}

Solution 2: accepted

No array manipulation. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
    public int[] plusOne(int[] digits) {
        
        int len = digits.length;
        
        // If the current digit does not cause a carry, return the updated array immediately
        for (int i = len - 1; i >= 0; i--) {
          if (digits[i] < 9) {
              digits[i]++;
              return digits;
          }
          digits[i] = 0;
        }
        
        // If the entire array is consisted of "9"s, return a new array leading with a "1" followed by "0"s
        int[] update = new int[len + 1];
        update[0] = 1;
        return update;        
    }    
}

Posted on | In

Test cases

1
2
3
4
5
6
7
8
9
10
"1"
"1"
"0"
"0"
"0"
"1010101"
"1100011"
"10101101010"
"10011"
"11011"

Solution 1: accepted 3ms 81%

The performance is good, but the style is a diseaster man.

Time: O(n)
Space: O(n) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
public String addBinary(String a, String b) {
    int la = a.length();
    int lb = b.length();
    int common = la < lb? la : lb;
    boolean carry = false;
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < common; i++ ) {
        char ca = a.charAt(la - i - 1);
        char cb = b.charAt(lb - i - 1);
        if (ca != cb) {  // 1 and 0
            if(carry) {
                sb.insert(0, "0"); // keep carrying on
            } else {
                sb.insert(0, "1");   
            }
        } else if (ca == '1') { // 1 and 1
            if(carry) {
                sb.insert(0, "1"); // keep carrying on
            } else {
                sb.insert(0, "0");
                carry = true;
            }
        } else { // 0 and 0
            if(carry) {
                sb.insert(0, "1");
                carry = false;
            } else {
                sb.insert(0, "0");   
            }
        }
    }
    String longer = la < lb? b : a;
    for (int j = longer.length() - common - 1; j >= 0; j--) {
        if (longer.charAt(j) == '1') {
            if (carry) {
                sb.insert(0, "0"); // keep carrying on
            } else {
                sb.insert(0, "1");
            }
        } else {
            if (carry) {
                sb.insert(0, "1");
                carry = false;
            } else {
                sb.insert(0, "0");
            }
        }
    }
    if (carry) {
        sb.insert(0, "1");
    }
    return sb.toString();
}

Solution 2: accepted 6ms

Looks better, but worse performance than solution 1. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public String addBinary(String a, String b) {       
    int i = a.length() - 1;
    int j = b.length() - 1;
    int carry = 0;
    StringBuilder sb = new StringBuilder();
    while (i >= 0 || j >= 0) {
        int sum = carry;
        if (i >= 0) 
            sum += Character.getNumericValue(a.charAt(i--));
        if (j >= 0) 
            sum += Character.getNumericValue(b.charAt(j--));
        sb.insert(0, Integer.toString(sum % 2));
        carry = sum >= 2? 1 : 0;
    }
    if (carry > 0)
        sb.insert(0, "1");
    return sb.toString();
}

Further improvement: 4ms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public String addBinary(String a, String b) {       
    int i = a.length() - 1;
    int j = b.length() - 1;
    int carry = 0;
    StringBuilder sb = new StringBuilder();
    while (i >= 0 || j >= 0) {
        int sum = carry;
        if (i >= 0) 
            sum += a.charAt(i--) - '0'; // get numeric value: ('9' = 57)-('0' = 48) = 9, worth 2ms
        if (j >= 0) 
            sum += b.charAt(j--) - '0'; 
        sb.insert(0, Integer.toString(sum % 2));
        carry = sum >= 2? 1 : 0;
    }
    if (carry > 0)
        sb.insert(0, "1");
    return sb.toString();
}

Posted on | In

Solution 1: accepted

Binary search. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int mySqrt(int x) {
    if (x == 0)
        return 0;
    int left = 1;
    int right = Integer.MAX_VALUE;
    while (true) {
        int mid = left + (right - left)/2;  // prevent integer overflow
        if (mid > x/mid) {                  // prevent integer overflow
            right = mid - 1;
        } 
        else {
            if (mid + 1 > x/(mid + 1))      // prevent integer overflow
                return mid;
            left = mid + 1;
        }
    }
}

Solution 2: accepted

Newton method. Can also be used on other polynomial equations (please save my poor math).
Mathmatical reference: http://www.matrix67.com/blog/archives/361 

1
2
3
4
5
6
7
public int mySqrt(int x) {
    long root = x / 2 + 1; // without 1, test case 1 will always be smaller than 1
    while (root * root > x) {
        root = (root + x / root) / 2; 
    }
    return (int)root;
}

Posted on | In

Solution 1: accepted 1ms

Time: O(log(m*n)) = O(logm + logn)
Space: O(1) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public boolean searchMatrix(int[][] matrix, int target) {
  if (matrix.length < 1 || matrix[0].length < 1) 
      return false;
  int m = matrix.length;
  int n = matrix[0].length;
  int lo = 0;
  int hi = m * n - 1;
  while (lo + 1 < hi) {
    int mid = lo + (hi - lo) / 2;
    int row = mid / n;
    int col = mid % n;
    if (matrix[row][col] > target)
      hi = mid;
    else if (matrix[row][col] < target)
      lo = mid;
    else
      return true;
  }
  if (matrix[lo/n][lo%n] == target || matrix[hi/n][hi%n] == target)
    return true;
  else
    return false;
}

Solution 2: accepted 0ms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public boolean searchMatrix(int[][] matrix, int target) {
  if (matrix.length < 1 || matrix[0].length < 1) 
      return false;
  int m = matrix.length;
  int n = matrix[0].length;
  int lo = 0;
  int hi = m * n - 1;
  while (lo <= hi) {  // optimized binary structure
    int mid = lo + (hi - lo) / 2;
    int value = matrix[mid / n][mid % n];  // where the improvements from 
    if (value > target)
      hi = mid - 1;
    else if (value < target)
      lo = mid + 1;
    else
      return true;
  }
  return false;
}

Posted on | In

Solution 1: time limit exceeded

Time: O(2^n)
I forget to remove “static” on ways and it accumulates the results of all test cases. 

1
2
3
4
5
6
7
8
9
10
11
12
public class Solution {
    int ways = 0;
    public synchronized int climbStairs(int n) {
        if (n > 1) 
          climbStairs(n - 2);
        if (n > 0) 
          climbStairs(n - 1);
        if (n == 0)
          ways++;
        return ways;
    }
}

A better alternative

1
2
3
4
5
public int climbStairs(int n) {
    if(n == 0 || n == 1) 
        return 1;
    return climbStairs(n-1) + climbStairs(n-2);
}

Solution 2: accepted 0ms

Time: O(n)
Straight fibonacci: f(n) = f(n-1) + f(n-2) 

1
2
3
4
5
6
7
8
9
10
11
12
public int climbStairs(int n) {
    if(n < 3) return n;
    int f1 = 1;
    int f2 = 2;
    for(int i = 3; i <= n; i++) {
        int temp = f2;
        f2 += f1;
        f1 = temp;
    }
    return f2;
}

Posted on | In

Solution 1: accepted

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public class Solution {
    public String longestCommonPrefix(String[] strs) {
        int length = strs.length;
        if (length == 0) {
            return "";
        }
        else if (length == 1){
            return strs[0];
        }
        else {
            String answer = strs[0];
            for (int i = 1; i < length; i++) {
                if (answer.equals(""))
                    break;
                else if (strs[i].startsWith(answer)) {
                   continue;
                }
                else {
                	while (!strs[i].startsWith(answer)) {
                		answer = answer.substring(0, answer.length() - 1);
                	}
                }
            }
            return answer;
        }
    }
}

Posted on | In

Solution 1: skipped

Brute force with 3 loops, time complexity O(n^3)

Solution 2: accepted 58%

Two-pointer after sorting. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
public class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        
        int len = nums.length;
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if (nums == null || len < 3)
            return result;
        Arrays.sort(nums);
        
        for (int i = 0; i < len - 2; i++) {
            if (i == 0 || nums[i] > nums[i - 1]) {
                int j = i + 1;
                int k = len - 1;
                while (k > j) {
                    int sum = nums[i] + nums[j] + nums[k];
                    if (sum == 0) {
                        List<Integer> al = new ArrayList<>();
                        al.add(nums[i]);
                        al.add(nums[j]);
                        al.add(nums[k]);
                        result.add(al);
                        
                        j++;
                        k--;
                        while (k > j && nums[j] == nums[j - 1])
                            j++;
                        while (k > j && nums[k] == nums[k + 1])
                            k--;
                    }
                    else if (sum < 0)
                        j++;
                    else
                        k--;
                }
            }
        }
        return result;
    }
}