Posted on | In

Solution 1: accepted 30ms

Recursive DFS. Check all possible paths from each node.
Time: O(n^2)
Space: O(n) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
    public int pathSum(TreeNode root, int sum) {
        if (root == null) return 0;
        return rootSum(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
    }
    
    // Check all paths starts from this node
    private int rootSum (TreeNode root, int sum) {
        int result = 0;
        if (root == null) return result;
        if (sum == root.val) result++;
        result += rootSum(root.left, sum - root.val);
        result += rootSum(root.right, sum - root.val);
        return result;   
    }
}

Posted on | In

Solution 1: accepted 3ms

DP.

  1. Base case: M[0] = 0;
  2. Induction rule: M[i] = M[i - 2^n] + 1, n = the max possible n <= i

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int[] countBits(int num) {
    int[] result = new int[num + 1];
    result[0] = 0;
    int next = 1; // 2^0
    int flag = 0; // when digit increases (2^n), we restart from the first position
    for (int i = 1; i <= num; i++) {
        if (i == next) {
            flag = 0;
            next *= 2; // 2^(n+1), each will add one more digit
        } 
        result[i] = 1 + result[flag];
        flag++;
    }
    return result;
}

Posted on | In

Test Cases

1
2
3
4
5
6
7
8
9
10
[1,5]
-6
[23, 2, 4, 6, 7]
6
[23 ,2, 4, 6, 7]
0
[0, 0]
0
[0, 0]
100

Solution 1: accepted 29%

Time: O(n^2)
Brute force with double loops

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
public boolean checkSubarraySum(int[] nums, int k) {
        int len = nums.length;
        if (len < 2)
          return false;
        // Only if all elements in nums are 0, can k be 0
        if (k == 0) {
          for (int n : nums) {
            if (n != 0)
              return false;
          }
          return true;
        }
        // Double loop to check all possible combinations
        for (int i = 0; i < len - 1; i++) {
          int sum = nums[i];
          for (int j = i + 1; j < len; j++) {
            if ((sum + nums[j]) % k == 0)
              return true;
            sum += nums[j];
          }
        }
        return false;
    }

Posted on | In

Solution 1: accepted 64ms 10%

1
2
3
4
5
6
7
8
9
10
public int arrangeCoins(int n) {
    int row = 0;
    int cost = 1;
    while (n >= cost) {
        n -= cost;
        row++;
        cost++;
    }
    return row;
}

Solution 2: accepted 46ms 69%

Cost of coins: 1+2+3+…+k = k(1+k)/2
Calculate the maximum of k where k(1+k) <= 2n
(0 <= k < n) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int arrangeCoins(int n) {
    long lo = 0;
    long hi = n;
    while (lo < hi) {
        long mid = lo + (hi - lo + 1) / 2; // why + 1? prevent the infinite loop for lo
        if (mid * (mid + 1) < (long)2 * n) {
            lo = mid;
        } else if (mid * (mid + 1) > (long)2 * n) {
            hi = mid - 1;  // since lo is inclusive, hi can be exclusive
        } else {
            return (int)mid;
        }
    }
    return (int)lo;
}

Alternative from this post

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int arrangeCoins(int n) {   
    //convert int to long to prevent integer overflow
    long nLong = (long)n;
    long st = 0;
    long ed = nLong;
    long mid = 0;
    while (st <= ed){
        mid = st + (ed - st) / 2;
        if (mid * (mid + 1) <= 2 * nLong){
            st = mid + 1;
        }else{
            ed = mid - 1;
        }
    } 
    return (int)(st - 1);
}

Solution 3

We have many math solutions.

Posted on | In

Solution 1: accepted 7ms

Increment and simply mapping the index. 

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
public class Codec {
    
    private static HashMap<String, String> stl = new HashMap<>();
    private static HashMap<String, String> lts = new HashMap<>();
    private final String BASE_URL = "http://tinyurl.com/";
    private static char[] dic = {'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z','a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
    
    // Encodes a URL to a shortened URL.
    public String encode(String longUrl) {
        int size = stl.size();
        String tiny = getTiny(size);
        stl.put(tiny, longUrl);
        lts.put(longUrl, tiny);
        return BASE_URL + tiny;
    }
    // Decodes a shortened URL to its original URL.
    public String decode(String shortUrl) {
        String tiny = shortUrl.substring(shortUrl.length() - 6, shortUrl.length());
        return stl.get(tiny);
    }
    
    public String getTiny(int size) {
        String tiny = "";
        for (int i = 0; i < 6; i++) {
            tiny += dic[size%62];
            size /= 62;
        }
        return tiny;
    }
}

Solution 2: accepted 5ms

This solution will use more space but has better performance. 

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 class Codec {
    
    private static HashMap<String, String> stl = new HashMap<>();
    private static HashMap<String, String> lts = new HashMap<>();
    private final String BASE_URL = "http://tinyurl.com/";
    private static char[] dic = {'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z','a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
    
    // Encodes a URL to a shortened URL.
    public String encode(String longUrl) {
        int size = stl.size();
        String tiny = BASE_URL + getTiny(size); // store the leading url as well
        stl.put(tiny, longUrl);
        lts.put(longUrl, tiny);
        return tiny;
    }
    // Decodes a shortened URL to its original URL.
    public String decode(String shortUrl) {
        return stl.get(shortUrl);
    }
    
    public String getTiny(int size) {
        String tiny = "";
        for (int i = 0; i < 6; i++) {
            tiny += dic[size%62];
            size /= 62;
        }
        return tiny;
    }
}

Notes

Integer.toString(i, radix), 2 <= radix <= 36. For example, Integer.toString(11112222, 0) will give 6m68u.

Posted on | In

Solution 1: accepted 2ms

DP. The same as the cutting rope issue.
Time: O(n^2)
Space: O(n) 

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

Solution 2:

Could use math method.

Posted on | In

Solution 1: accepted 22ms

Iteration.
Time: O(n)
Space: O(1) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public double findMaxAverage(int[] nums, int k) {
    int len = nums.length;
    if (len < k) return 0;
    double sum = 0;
    for(int i = 0; i < k; i++) {
        sum += nums[i] / (double) k;
    }
    double max = sum;
    for(int i = 1; i < len - k + 1; i++) {
        sum = sum - nums[i-1] / (double) k + nums[i+k-1] / (double) k;
        max = Math.max(max, sum);
    }
    return max;  
}

Solution 2: accepted 19ms

Calculate the average at last - be flexible man. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public double findMaxAverage(int[] nums, int k) {
    int len = nums.length;
    if (len < k) return 0;
    double sum = 0;
    for(int i = 0; i < k; i++) {
        sum += nums[i];
    }
    double max = sum;
    for(int i = 1; i < len - k + 1; i++) {
        sum = sum - nums[i - 1] + nums[i + k - 1];
        max = Math.max(max, sum);
    }
    return max / (double) k;  
}

Posted on | In

Solution 1: accepted 28ms

DP.

  1. Base case: A[1] = 0
  2. Induction rule: A[n]
    if n%2 == 0, A[n] = dp[n] + 2
    if n%2 != 0, A[n] = max(dp[j] + n/j), where n%j = 0 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int minSteps(int n) {
        if (n < 1) {
            return 0;
        }
        int[] dp = new int[n + 1];
        for (int i = 2; i <= n; i++) {
            if (i % 2 == 0) {
                dp[i] = dp[i / 2] + 2;
            } else {
                for (int j = 3; j < i / 2; j++) {
                    if (i % j == 0 && dp[j] != 0) {
                        dp[i] = dp[j] + (i / j);
                    }
                }
                if (dp[i] == 0) {
                    dp[i] = i;
                }
            }
        }
        return dp[n];
    }
}

Posted on | In

665. Non-decreasing Array

Given an array with n integers, your task is to check if it could become non-decreasing by modifying at most 1 element.

We define an array is non-decreasing if array[i] <= array[i + 1] holds for every i (1 <= i < n).

Example 1:
Input: [4,2,3]
Output: True
Explanation: You could modify the first 4 to 1 to get a non-decreasing array.
Example 2:
Input: [4,2,1]
Output: False
Explanation: You can’t get a non-decreasing array by modify at most one element.
Note: The n belongs to [1, 10,000].

Test cases

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

Solution 1: accepted

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public boolean checkPossibility(int[] nums) {
    int len = nums.length;
    boolean once = false;
    for (int i = 1; i < len; i++) {
        if (nums[i] < nums[i - 1]) {
            if (once) {
                return false;
            } else if (i - 2 >= 0 && i < len - 1) {
                if (nums[i - 2] > nums[i] && nums[i + 1] < nums[i - 1])
                    return false;
            }
            once = true;
        }
    }
    return true;
}

Posted on | In

Test cases

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

Solution 1: accepted 35ms

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 int[][] imageSmoother(int[][] M) {
    if (M.length == 0) return M;
    int [][] A = new int[M.length][M[0].length];
    for (int row = 0; row < M.length; row++) {
        for (int col = 0; col < M[0].length; col++) {
            int sum = 0;
            int xStart = row == 0? 0 : -1;
            int xEnd = row == M.length - 1? 0 : 1;
            int yStart = col == 0? 0 : -1;
            int yEnd = col == M[0].length - 1? 0: 1;
            int divisor = 0;
            for (int x = xStart; x <= xEnd; x++) {
                for (int y = yStart; y <= yEnd; y++) {
                    sum += M[row + x][col + y];
                    divisor ++;
                }
            }
            A[row][col] = (int)(sum / (double)divisor);
        }
    }
    return A;
}