265. Paint House II

There are a row of n houses, each house can be painted with one of the k colors. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.

The cost of painting each house with a certain color is represented by a n x k cost matrix. For example, costs[0][0] is the cost of painting house 0 with color 0; costs[1][2] is the cost of painting house 1 with color 2, and so on... Find the minimum cost to paint all houses.

Note:
All costs are positive integers.

Example:

Input: [[1,5,3],[2,9,4]]
Output: 5
Explanation: Paint house 0 into color 0, paint house 1 into color 2. Minimum cost: 1 + 4 = 5; 
             Or paint house 0 into color 2, paint house 1 into color 0. Minimum cost: 3 + 2 = 5. 

Follow up:
Could you solve it in O(nk) runtime?

My answer:

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 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81

class Solution { public int minCostII(int[][] costs) { // Solution 1: O(n*k^2) time, space O(nk) // dp[n][k] // dp[i][0] min cost given color0 is painted to ith house // dp[i][1] min cost given color1 is painted to ith house // dp[i][2] min cost given color2 is painted to ith house // if (costs == null || costs.length == 0) { // return 0; // } // int[][] dp = new int[costs.length][costs[0].length]; // for (int i = 0; i < costs[0].length; i ++) { // dp[0][i] = costs[0][i]; // } // for (int i = 1; i < costs.length; i ++) { // for (int j = 0; j < costs[i].length; j ++) { // int minValidPreCost = Integer.MAX_VALUE; // for (int k = 0; k < costs[i].length; k ++) { // if (j == k) { // continue; // } // minValidPreCost = Math.min(minValidPreCost, dp[i-1][k]); // } // dp[i][j] = costs[i][j] + minValidPreCost; // } // } // int minCost = Integer.MAX_VALUE; // for (int i = 0; i < dp[costs.length - 1].length; i ++) { // minCost = Math.min(minCost, dp[costs.length - 1][i]); // } // return minCost; // Solution 2: only keep track of second min and min of previous row // because each time we only add min/second min to current row // second min is only for index of min // time O(nk), space is O(1) if (costs == null || costs.length == 0) { return 0; } int preMin = -1; int preSecondMin = -1; int preMinIdex = -1; for (int i = 0; i < costs[0].length; i ++) { if (preMin == -1 || costs[0][i] < preMin) { preSecondMin = preMin; preMin = costs[0][i]; preMinIdex = i; } else if (preSecondMin == -1 || costs[0][i] < preSecondMin) { preSecondMin = costs[0][i]; } } for (int i = 1; i < costs.length; i ++) { int currentMin = -1; int currentSecondMin = -1; int currentMinIndex = 0; for (int j = 0; j < costs[i].length; j ++) { int currentCost = costs[i][j]; if (j != preMinIdex) { currentCost += preMin; } else { currentCost += preSecondMin; } if (currentMin == -1 || currentCost < currentMin) { currentSecondMin = currentMin; currentMin = currentCost; currentMinIndex = j; } else if (currentSecondMin == -1 || currentCost < currentSecondMin) { currentSecondMin = currentCost; } } preMin = currentMin; preSecondMin = currentSecondMin; preMinIdex = currentMinIndex; } return preMin; } }

611. Valid Triangle Number

Given an array consists of non-negative integers, your task is to count the number of triplets chosen from the array that can make triangles if we take them as side lengths of a triangle.

Example 1:

Input: [2,2,3,4]
Output: 3
Explanation:
Valid combinations are: 
2,3,4 (using the first 2)
2,3,4 (using the second 2)
2,2,3

Note:

1. The length of the given array won't exceed 1000.
2. The integers in the given array are in the range of [0, 1000].

My answer: thought of backtrack in the beginning, didn't think about 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 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92

class Solution { private int result = 0; public int triangleNumber(int[] nums) { // backtrack -- O(n^3) [,aka Cn3] // time limit exceeded. // List<Integer> singleCombination = new ArrayList<Integer>(); // helper(nums, 0, singleCombination); // return result; // Solution 2: O(n^2 lg(n)) // sort, then start with left/right most value, // get expected threshold value for triangle, // use bs to find the smallest bigger element than threshold // int count = 0; // Arrays.sort(nums); // int l = 0; // int r = nums.length - 1; // for (int i = 0; i < nums.length - 2; i ++) { // for (int j = nums.length - 1; j >= i + 2; j --) { // int threshold = nums[j] - nums[i]; // // find index of smallest element bigger than threshold // int idx = bs(nums, i, j, threshold); // // if idx == i, meaning threshold is smaller than num[i] // count += idx == i ? j - idx - 1 : j - idx; // } // } // return count; //Solution 3: //sort, start from end, fix it as largest side, //find the other 2 sides fromt left elements of end value int count = 0; Arrays.sort(nums); for (int k = nums.length - 1; k >= 2; k --) { int i = 0; int j = k - 1; while (i < j) { if (nums[i] + nums[j] > nums[k]) { // count options when j,k is fixed count += j - i; j --; } else { i ++; } } } return count; } private int bs (int[] nums, int l, int r, int threshold) { while (l < r) { int m = (l + r)/2; if (nums[m] > threshold) { r = m; } else { l = m + 1; } } return l; } private void helper(int[] nums, int start, List<Integer> singleCombination) { if (singleCombination.size() == 3) { if (isValid(singleCombination)) { result += 1; } return; } for (int i = start; i < nums.length; i ++) { singleCombination.add(nums[i]); helper(nums, i + 1, singleCombination); singleCombination.remove(singleCombination.size() - 1); } } private boolean isValid(List<Integer> combination) { int v0 = combination.get(0); int v1 = combination.get(1); int v2 = combination.get(2); if ((v2 + v1 <= v0) || (v2 + v0 <= v1) || (v0 + v1 <= v2) ) { return false; } return true; } }

53. Maximum Subarray

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

 

Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Example 2:

Input: nums = [1]
Output: 1

Example 3:

Input: nums = [0]
Output: 0

Example 4:

Input: nums = [-1]
Output: -1

Example 5:

Input: nums = [-100000]
Output: -100000

 

Constraints:

• 1 <= nums.length <= 3 * 104
• -105 <= nums[i] <= 105

 

Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle. 

My answer:

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

public class Solution { public int maxSubArray(int[] nums) { // answer before 2021 // int globalMax = nums[0]; // int localMax = nums[0]; // for (int i = 1; i < nums.length; i ++) { // // localMax is the bigger value which includes "i"th number, so that the globalMax can be the result of contiguous subarray // localMax = Math.max(nums[i], localMax + nums[i]); // globalMax = Math.max(globalMax, localMax); // } // return globalMax; // answer on 2021 if (nums == null || nums.length == 0) { return 0; } if (nums.length == 1) { return nums[0]; } // dp is the value where max sum given i th element must be included int[] dp = new int[nums.length]; dp[0] = nums[0]; for (int i = 1; i < nums.length; i ++) { dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]); } int maxSum = dp[0]; for (int i = 1; i < dp.length; i ++) { maxSum = Math.max(maxSum, dp[i]); } return maxSum; } }

Regarding the follow up via Divide and Conqure: below answer is from Leetcode forum. 

Divide and Conquer

The Divide-and-Conquer algorithm breaks nums into two halves and find the maximum subarray sum in them recursively. Well, the most tricky part is to handle the case that the maximum subarray spans the two halves. For this case, we use a linear algorithm: starting from the middle element and move to both ends (left and right ends), record the maximum sum we have seen. In this case, the maximum sum is finally equal to the middle element plus the maximum sum of moving leftwards and the maximum sum of moving rightwards.

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        return maxSubArray(nums, 0, nums.size() - 1);
    }
private:
    int maxSubArray(vector<int>& nums, int l, int r) {
        if (l > r) {
            return INT_MIN;
        }
        int m = l + (r - l) / 2, ml = 0, mr = 0;
        int lmax = maxSubArray(nums, l, m - 1);
        int rmax = maxSubArray(nums, m + 1, r);
        for (int i = m - 1, sum = 0; i >= l; i--) {
            sum += nums[i];
            ml = max(sum, ml);
        }
        for (int i = m + 1, sum = 0; i <= r; i++) {
            sum += nums[i];
            mr = max(sum, mr);
        }
        return max(max(lmax, rmax), ml + mr + nums[m]);
    

366. Find Leaves of Binary Tree

Given a binary tree, collect a tree's nodes as if you were doing this: Collect and remove all leaves, repeat until the tree is empty.

 

Example:

Input: [1,2,3,4,5]
  
          1
         / \
        2   3
       / \     
      4   5    

Output: [[4,5,3],[2],[1]]

 

Explanation:

1. Removing the leaves [4,5,3] would result in this tree:

          1
         / 
        2          

 

2. Now removing the leaf [2] would result in this tree:

          1          

 

3. Now removing the leaf [1] would result in the empty tree:

          []          

[[3,5,4],[2],[1]], [[3,4,5],[2],[1]], etc, are also consider correct answers since per each level it doesn't matter the order on which elements are returned. 

My answer:

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 60 61 62 63 64 65 66 67 68 69 70 71

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public List<List<Integer>> findLeaves(TreeNode root) { // Solution 1 // List<List<Integer>> result = new ArrayList<List<Integer>>(); // TreeNode resultNode = root; // while(resultNode != null) { // List<Integer> singleResult = new ArrayList<Integer>(); // resultNode = removeLeaves(root, singleResult); // result.add(singleResult); // } // return result; // Solution 2: add leaf to its correspondig node's height // node's height is number of edges to its deepest leaf List<List<Integer>> result = new ArrayList<List<Integer>>(); height(root, result); return result; } private int height(TreeNode node, List<List<Integer>> result) { if (node == null) { return -1; } int currentHeight = 1 + Math.max(height(node.left, result), height(node.right, result)); if (result.size() == currentHeight) { // found a new level/height for result // because largest index of result is size - 1 result.add(new ArrayList<Integer>()); } result.get(currentHeight).add(node.val); // left child is already null in last recursion, thus no need to do that // node.left = null; // node.right = null; node = null; return currentHeight; } private TreeNode removeLeaves(TreeNode node, List<Integer> leaves) { if (node == null) { return null; } // found leaf node if (node.left == null && node.right == null ) { leaves.add(node.val); return null; } TreeNode left = removeLeaves(node.left, leaves); TreeNode right = removeLeaves(node.right, leaves); node.left = left; node.right = right; return node; } }

437. Path Sum III

Medium

You are given a binary tree in which each node contains an integer value.

Find the number of paths that sum to a given value.

The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).

The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.

Example:

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1

Return 3. The paths that sum to 8 are:

1.  5 -> 3
2.  5 -> 2 -> 1
3. -3 -> 11

 

My answer is: basic idea to compute suffix sum of each path when node is being traversed. Thus complexity is O(n^2). Better solution is shown below, which is O(n).

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private int pathFound = 0;
    private Map<TreeNode, Integer> nodesSum = new HashMap<TreeNode, Integer>();
    public int pathSum(TreeNode root, int sum) {
        
        List<List<Integer>> expectedValuesInPaths = new ArrayList<List<Integer>>();
        List<TreeNode> currentNodes = new ArrayList<TreeNode>();
        helper(root, sum, currentNodes);
        return pathFound;
    }
    
    private void helper(TreeNode node, int sum, List<TreeNode> currentNodesInPath) {
        
        if (node == null) {
            return;
        }
        int paths = getSuffixPaths(currentNodesInPath, node, sum);
        pathFound += paths;
        currentNodesInPath.add(node);
        helper(node.left, sum, currentNodesInPath);
        helper(node.right, sum, currentNodesInPath);
        // remove last added node
        currentNodesInPath.remove(currentNodesInPath.size() - 1);
    }
    
    private int getSuffixPaths(List<TreeNode> previousNodes, TreeNode currentNode, int sum) {
        int paths = 0;
        List<Integer> nodeSums = new ArrayList<Integer>();
        int currentSum = currentNode.val;
        // in case currentNode itself can be sufficient
        nodeSums.add(currentSum);
        if (currentSum == sum) {
                paths ++;
        }
        for (int i = previousNodes.size() - 1; i >= 0; i--) {
            TreeNode prevNode = previousNodes.get(i);
            currentSum += prevNode.val;
            nodeSums.add(currentSum);
            if (currentSum == sum) {
                paths ++;
            }
        }
        return paths;
    }
}

Best O(n) solution: calculate prefix sum for path. On 1 path, (prefix sum on index j - prefix sum on index i) = sum[i:j]. Thus, if prefixSum == targetValue OR (prefixSum - targetValue) in prefixSumsMap.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

public int pathSum(TreeNode root, int sum) { HashMap<Integer, Integer> preSum = new HashMap(); preSum.put(0,1); return helper(root, 0, sum, preSum); } public int helper(TreeNode root, int currSum, int target, HashMap<Integer, Integer> preSum) { if (root == null) { return 0; } currSum += root.val; int res = preSum.getOrDefault(currSum - target, 0); preSum.put(currSum, preSum.getOrDefault(currSum, 0) + 1); res += helper(root.left, currSum, target, preSum) + helper(root.right, currSum, target, preSum); // remove current node's impact preSum.put(currSum, preSum.get(currSum) - 1); return res; }