Posted on | In

Test case

1
2
3
4
5
6
7
8
9
10
11
12
[]
[1]
[1,2]
[2,1]
[1,3,2]
[1,2,3]
[1,2,3,4,5,6,8]
[8,6,5,4,3,2,1]
[1,2,3,4,5,6,7,8]
[8,7,6,5,4,3,2,1]
[1,0,3,5,6,4,1,4,2,9,5,8]
[1,0,3,5,6,4,1,4,2,9,5,8,6]

Solution 1: accepted 0ms

Time: O(n), Space: O(1)
Based on the solution of House Robber 1, the only difference is that, we cannot rob both of the first and the last house at one time. So we assume two situations, one includes only the first house, the other includes only the last house. 

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 rob(int[] nums) {
        int len = nums.length;
        if (len == 1) return nums[0];
        int group1 = robRange(nums, 1, len);        
        int group2 = robRange(nums, 0, len-1);
        return Math.max(group1, group2);
    }
    
    private int robRange(int nums[], int start, int end) {
        int doit = 0; // total stash if we do rob the current house
        int dont = 0; // total stash if don't rob the current house
        for(int i = start; i < end; i++) {
            int current = dont + nums[i];
            dont = Math.max(doit, dont);
            doit = current;
        }       
        return Math.max(dont, doit);
    }
}

Posted on | In

Solution 1: accepted 3ms

Two pointers. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int minSubArrayLen(int s, int[] nums) {        
        int start = 0;
        int end = 0;
        int sum = 0;
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            end = i;
            if (sum >= s) {
                while (sum - nums[start] >= s) {
                    sum -= nums[start];
                    start++;
                }
                min = Math.min(min, end - start + 1);
            }
        }
        return min == Integer.MAX_VALUE ? 0 : min;
    }
}

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
public class Solution {
    public void rotate(int[][] matrix) {
        for(int i = 0; i<matrix.length; i++){
            for(int j = i; j<matrix[0].length; j++){
                int temp = 0;
                temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }
        for(int i =0 ; i<matrix.length; i++){
            for(int j = 0; j<matrix.length/2; j++){
                int temp = 0;
                temp = matrix[i][j];
                matrix[i][j] = matrix[i][matrix.length-1-j];
                matrix[i][matrix.length-1-j] = temp;
            }
        }
    }
}

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
public String multiply(String num1, String num2) {
    int m = num1.length(), n = num2.length();
    int[] pos = new int[m + n];
   
    for(int i = m - 1; i >= 0; i--) {
        for(int j = n - 1; j >= 0; j--) {
            int mul = (num1.charAt(i) - '0') * (num2.charAt(j) - '0'); 
            int p1 = i + j, p2 = i + j + 1;
            int sum = mul + pos[p2];
            pos[p1] += sum / 10;
            pos[p2] = (sum) % 10;
        }
    }  
    
    StringBuilder sb = new StringBuilder();
    for(int p : pos) if(!(sb.length() == 0 && p == 0)) sb.append(p);
    return sb.length() == 0 ? "0" : sb.toString();
}

Posted on | In

Test cases

1
2
3
4
5
6
7
8
9
10
[[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]]
4
[[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]]
30
[]
0
[[1]]
1
[[]]
0

Solution 1: accepted 18ms

Binary search for each row.

Time: O(nlogn)
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
24
25
26
27
28
29
public boolean searchMatrix(int[][] matrix, int target) {       
    int m = matrix.length - 1;
    if (m < 0) return false;
    int n = matrix[0].length - 1;
    if (n < 0) return false;
    for (int i = 0; i <= m; i++) {
      if (target < matrix[i][0] || target > matrix[i][n]) {
          continue;
      } else {
        // Binary search for each row
        int lo = 0;
        int hi = n;
        while (lo <= hi) {
          int mid = lo + (hi - lo) / 2;
          if (target > matrix[i][mid]) {
            lo = mid + 1;
          } else if (target < matrix[i][mid]) {
            hi = mid - 1;
          } else {
            return true;
          }
        }
        if (matrix[i][lo] == target)
            return true;
      }
    } 
    return false;
}

Solution 2: accepted 13ms

Seach from top-right or bottom left.

Time: O(nm)
Space: O(1) 

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

Follow-up: if every row is straightly ascending (the first element of this row is larger than the last element in last row), the complexity could be O(logM+logN). Treate it as a 1D array, do a binary search (row = mid/column, col = mid%column).

Posted on | In

Solution 1: accepted 18ms

Binary search.

Feel the differences and commonalities. The first solution is recommended, as it is a wild card solution. 

1
2
3
4
5
6
7
8
9
10
11
12
13
public int firstBadVersion(int n) {
    int lo = 1;
    int hi = n;
    while (lo + 1 < hi) {
        int mid = lo + (hi - lo) / 2;
        if (isBadVersion(mid)) {
            hi = mid;
        } else {
            lo = mid;
        }
    }
    return isBadVersion(lo)? lo : hi;
}
1
2
3
4
5
6
7
8
9
10
11
12
public int firstBadVersion(int n) {
    int lo = 1;
    int hi = n;
    while(lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (isBadVersion(mid))
            hi = mid;
        else 
            lo = mid + 1;
    }
    return lo; // hi is ok as well
}
1
2
3
4
5
6
7
8
9
10
11
12
public int firstBadVersion(int n) {
    int lo = 1;
    int hi = n;
    while(lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (isBadVersion(mid))
            hi = mid - 1;
        else 
            lo = mid + 1; 
    }
    return lo;  
}

Posted on | In

Solution 1: accepted

A primitive solution that manipulates Strings. Spent 7 ms and beats 9.5%.

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
public static int myAtoi(String str) {
	str = str.trim();
	if (str.length() == 0)
		return 0;
	if ((str.charAt(0) < '0' || str.charAt(0) > '9') && str.charAt(0) != '-' && str.charAt(0) != '+') {
		return 0;
	}
	String sign = "";
	int index = 0;
	if (str.charAt(0) == '-' || str.charAt(0) == '+') {
		index = 1;
		if (str.length() == 1 || str.charAt(1) < '0' || str.charAt(1) > '9')
			return 0;
		if (str.charAt(0) == '-')
			sign = "-";
	}
	StringBuilder sb = new StringBuilder();
	for (int i = index; i < str.length(); i++) {
		if (str.charAt(i) >= 48 && str.charAt(i) <= 57) {
			sb.append(str.charAt(i));
		} else
			break;
	}
	String value = sb.toString();
	if (value.length() >= 10 && sign.equals("-")) {
		if (value.length() >= 11)
			return Integer.parseInt("-2147483648");
		else if (value.length() == 10 && value.compareTo("2147483648") > 0)
			return Integer.parseInt("-2147483648");
		else
			return Integer.parseInt(sign + value);
	}
	else if (value.length() >= 10 && sign.equals("")) {
		if (value.length() >= 11)
			return Integer.parseInt("2147483647");
		else if (value.length() == 10 && value.compareTo("2147483647") > 0)
			return Integer.parseInt("2147483647");
		else
			return Integer.parseInt(value);
	} else
		return Integer.parseInt(sign + value);
}

Solution 2: accepted

Improved based on the first one, it now beats 14.9%.

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
public static int myAtoi(String str) {
	int max = Integer.MAX_VALUE;
	int min = Integer.MIN_VALUE;
	int sign = 1;
	boolean start = false;
	StringBuilder sb = new StringBuilder();
	for (int i = 0; i < str.length(); i++) {
		char thisChar = str.charAt(i);
		if (thisChar == ' ' && !start) {
			continue;
		} else if ((thisChar == '-' || thisChar == '+') && !start) {
			start = true;
			if (thisChar == '-')
				sign = -1;
		} else if (thisChar < '0' || thisChar > '9')
			break;
		else {
			start = true;
			sb.append(thisChar);
		}
	}
	if (sb.length() == 0)
		return 0;
	String value = sb.toString();
	if (value.length() >= 10 && sign == -1) {
		if (value.length() >= 11)
			return min;
		else if (value.length() == 10 && value.compareTo("2147483648") >= 0)
			return min;
		else
			return Integer.parseInt(value) * sign;
	}
	else if (value.length() >= 10 && sign == 1) {
		if (value.length() >= 11)
			return max;
		else if (value.length() == 10 && value.compareTo("2147483647") >= 0)
			return max;
		else
			return Integer.parseInt(value);
	} else
		return Integer.parseInt(value) * sign;
}

Solution 3: accepted

Manipulate numbers are more efficient than manipulating Strings. Now we have 85%.

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
public static int myAtoi(String str) {
	int max = Integer.MAX_VALUE;
	int min = Integer.MIN_VALUE;
	int digit; 
	int result = 0; 
	boolean isNegative = false;
	boolean start = false; //whether we have the first valid character 
	for (int i = 0; i < str.length(); i++) {
		char thisChar = str.charAt(i);
		if (!start && thisChar == ' ') {
			continue;
		} else if (!start && (thisChar == '-' || thisChar == '+')) {
			start = true;
			if (thisChar == '-')
				isNegative = true;
		} else if (thisChar < '0' || thisChar > '9')
			break;
		else {
			start = true;
			digit = thisChar - '0';
			if (result > max / 10 || (result == max / 10 && digit > 7)) { // 7 is max % 10
				if (isNegative)
					return min;
				else
					return max;
			}
			result = result * 10 + digit;
		}
	}

Posted on | In

Solution 1: accepted 48ms

  1. Base case: dp[0] = 0;
  2. Induction rule:
    dp[i] = min(dp[i - j j] + 1) where j j <= i
    dp[1] = dp[0] + 1 = 1;
    dp[2] = dp[1] + 1 = 2;
    dp[3] = dp[3] + 1 = 3;
    dp[4] = min(dp[4-11=3] + 1, dp[4-22=0] + 1) = 1; 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int numSquares(int n) {
    int[] dp = new int[n + 1];
    Arrays.fill(dp, Integer.MAX_VALUE);
    dp[0] = 0;
    for (int i = 1; i <= n; i++) {
        int j = 1; 
        while (j * j <= i) {
            dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
            j++;
        }
    }
    return dp[n];
}

Posted on | In

Solution 1: accepted 6ms

The input contain integers between [1,n]. If the maximum value is n, then the array has to have n + 1 elements to make sure that there are repeated values.

For this question, we don’t divide the elements inside the array as we do for regular binary search questions. Instead, we divide the range and compare the mid point with every element in the array. For example, for range [1,10], mid is 5, if there are more than five elements are smaller than 5, we know the repeated value is smaller than 5 (Pigeonhole principle), so we get a new range [1,5].

Time: O(nlogn)
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
24
25
26
class Solution {
    public int findDuplicate(int[] nums) {
        if (nums == null || nums.length < 2) {
            return -1;
        }
        
        int lo = 1;
        int hi = nums.length - 1;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            int count = 0;
            for (int n: nums) {
                if (n <= mid) {
                    count++;
                }
            }
            if (count <= mid) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        
        return lo;
    }
}

The old way (lo + 1 < hi) will have extra long code, not very elegant

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
class Solution {
    public int findDuplicate(int[] nums) {
        if (nums == null || nums.length < 2) {
            return -1;
        }
        
        int lo = 1;
        int hi = nums.length - 1;
        while (lo + 1 < hi) {
            int mid = lo + (hi - lo) / 2;
            int count = 0;
            for (int n: nums) {
                if (n <= mid) {
                    count++;
                }
            }
            if (count <= mid) {
                lo = mid;
            } else {
                hi = mid;
            }
        }
        
        int count = 0;
        for (int n: nums) {
            if (n == lo) {
                count++;
            }
            if (count > 1) {
                return lo;
            }
        }
        
        return hi;
    }
}

Posted on | In

Test cases

1
2
3
4
5
6
7
[10,9,2,5,3,7,101,18]
[2,5,3,4]
[2,5,3,4,6]
[2,3,4,5]
[5,4,3,2]
[0]
[1,1,1,1]

Solution 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Solution {
    public int lengthOfLIS(int[] nums) {
        
        int len = nums.length;
        if (len < 2) return len;
        
        HashMap<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < len; i++) {
            map.put(i, 1);
        }
        
        int max = 1;
        for (int i = 1; i < len; i++) {
            for (int j = 0; j < len; j++) {
                if (nums[j] < nums[i]) {
                    int bigger = map.get(i) > map.get(j) + 1 ? map.get(i) : map.get(j) + 1;
                    map.put(i, bigger);
                }
            }
            max = max > map.get(i)? max :  map.get(i);
        }
        return max;
    }
}