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; }

113. Path Sum II

 Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.

Note: A leaf is a node with no children.

Example:

Given the below binary tree and sum = 22,

      5
     / \
    4   8
   /   / \
  11  13  4
 /  \    / \
7    2  5   1

Return:

[
   [5,4,11,2],
   [5,8,4,5]
]

My answer is:

/**
 * 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>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        helper(root, sum, 0, new ArrayList<Integer>(), result);
        return result;
    }
    
    public void helper(TreeNode node, int sum, int currentSum, List<Integer> currentNodes, List<List<Integer>> result) {
        if (node == null) {
            return;
        }
        currentSum += node.val;
        currentNodes.add(node.val);
        if (node.left == null && node.right == null) {
            if (currentSum == sum) {
                List<Integer> foundNodes = new ArrayList<Integer>(currentNodes);
                result.add(foundNodes);
            }
            currentNodes.remove(currentNodes.size() - 1);
            return;
        }
        
        helper(node.left, sum, currentSum, currentNodes, result);
        helper(node.right, sum, currentSum, currentNodes, result);
        currentNodes.remove(currentNodes.size() - 1);
    }
}

112. Path Sum

 Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

Note: A leaf is a node with no children.

Example:

Given the below binary tree and sum = 22,

      5
     / \
    4   8
   /   / \
  11  13  4
 /  \      \
7    2      1

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

My answer is:

/**
 * 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 boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) {
            return false;
        }
        return helper(root, 0, sum);
    }
    
    private boolean helper(TreeNode node, int currentSum, int sum) {
        if (node == null) {
            return false;
        }
        currentSum += node.val;
        if (node.left == null && node.right == null) {
            return currentSum == sum;
        }
        boolean leftResult = helper(node.left, currentSum, sum);
        if (leftResult) {
            return true;
        }
        boolean rightResult = helper(node.right, currentSum, sum);
        return rightResult;
    }
}

1372. Longest ZigZag Path in a Binary Tree

Given a binary tree root, a ZigZag path for a binary tree is defined as follow:

• Choose any node in the binary tree and a direction (right or left).
• If the current direction is right then move to the right child of the current node otherwise move to the left child.
• Change the direction from right to left or right to left.
• Repeat the second and third step until you can't move in the tree.

Zigzag length is defined as the number of nodes visited - 1. (A single node has a length of 0).

Return the longest ZigZag path contained in that tree.

 

Example 1:

Input: root = [1,null,1,1,1,null,null,1,1,null,1,null,null,null,1,null,1]
Output: 3
Explanation: Longest ZigZag path in blue nodes (right -> left -> right).

Example 2:

Input: root = [1,1,1,null,1,null,null,1,1,null,1]
Output: 4
Explanation: Longest ZigZag path in blue nodes (left -> right -> left -> right).

Example 3:

Input: root = [1]
Output: 0

 

Constraints:

• Each tree has at most 50000 nodes..
• Each node's value is between [1, 100].

Answer:

For question involving tree, recursion around its root/left/right child is always good starting point. 

/**
 * 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 {
    /*
    * Recursive return [left, right, result], where:
    * left is the maximum length in direction of root.left
    * right is the maximum length in direction of root.right
    * result is the maximum length in the whole sub tree.
    *
    * Complexity
    * Time O(N)
    * Space O(height)
    */
    // my old answer, not right.
    // Integer result = 0;
    // public int longestZigZag(TreeNode root) {
    //     checkLongestZigZag(root, false);
    //     checkLongestZigZag(root, true);
    //     return result;
    // }
    // private int checkLongestZigZag(TreeNode node, boolean isLeft) {
    //     if (node == null) {
    //         return -1;
    //     }
    //     TreeNode next = isLeft? node.right : node.left;
    //     TreeNode theOther = isLeft? node.left : node.right;
    //     int nextResult = checkLongestZigZag(next, !isLeft);
    //     int theOtherResult = checkLongestZigZag(theOther, isLeft);
    //     result = Math.max(Math.max(nextResult + 1, theOtherResult), result);
    //     return (nextResult + 1);
    // }
    
        public int longestZigZag(TreeNode root) {
        return dfs(root)[2];
    }

    private int[] dfs(TreeNode root) {
        if (root == null) return new int[]{-1, -1, -1};
        int[] left = dfs(root.left), right = dfs(root.right);
        int res = Math.max(Math.max(left[1], right[0]) + 1, Math.max(left[2], right[2]));
        return new int[]{left[1] + 1, right[0] + 1, res};
    }
}

 

1566. Detect Pattern of Length M Repeated K or More Times

Given an array of positive integers arr,  find a pattern of length m that is repeated k or more times.

A pattern is a subarray (consecutive sub-sequence) that consists of one or more values, repeated multiple times consecutively without overlapping. A pattern is defined by its length and the number of repetitions.

Return true if there exists a pattern of length m that is repeated k or more times, otherwise return false.

 

Example 1:

Input: arr = [1,2,4,4,4,4], m = 1, k = 3
Output: true
Explanation: The pattern (4) of length 1 is repeated 4 consecutive times. Notice that pattern can be repeated k or more times but not less.

Example 2:

Input: arr = [1,2,1,2,1,1,1,3], m = 2, k = 2
Output: true
Explanation: The pattern (1,2) of length 2 is repeated 2 consecutive times. Another valid pattern (2,1) is also repeated 2 times.

Example 3:

Input: arr = [1,2,1,2,1,3], m = 2, k = 3
Output: false
Explanation: The pattern (1,2) is of length 2 but is repeated only 2 times. There is no pattern of length 2 that is repeated 3 or more times.

Example 4:

Input: arr = [1,2,3,1,2], m = 2, k = 2
Output: false
Explanation: Notice that the pattern (1,2) exists twice but not consecutively, so it doesn't count.

Example 5:

Input: arr = [2,2,2,2], m = 2, k = 3
Output: false
Explanation: The only pattern of length 2 is (2,2) however it's repeated only twice. Notice that we do not count overlapping repetitions.

 

Constraints:

• 2 <= arr.length <= 100
• 1 <= arr[i] <= 100
• 1 <= m <= 100
• 2 <= k <= 100

 

My answer: basic idea to check pattern in length m, and since it must be consecutive, we just need to check if index and index + m is same with each other. If not, index ++; if yes, check index + 1 and index + 1 + m

class Solution {
    public boolean containsPattern(int[] arr, int m, int k) {
        if (arr == null || arr.length < m || arr.length < m * k) {
            return false;
        }
        int count = 1;
        for (int start = 0; start < arr.length - m ;) {
            boolean patternFound = hasPattern(arr, start, m);
            if (patternFound) {
                count += 1;
                start += m;
                if (count >= k) {
                    return true;
                }
            } else {
                count = 1;
                start ++;
            }
        }
        return false;
    }
    
    private boolean hasPattern(int[] arr, int start, int m) {
        for (int i = 0 ; i < m; i ++) {
            if ((start + i + m) >= arr.length ||
                arr[start + i] != arr[start + i + m]) {
                return false;
            }
        }
        return true;
    }
}

474. Ones and Zeroes

 You are given an array of binary strings strs and two integers m and n.

Return the size of the largest subset of strs such that there are at most m 0's and n 1's in the subset.

A set x is a subset of a set y if all elements of x are also elements of y.

 

Example 1:

Input: strs = ["10","0001","111001","1","0"], m = 5, n = 3
Output: 4
Explanation: The largest subset with at most 5 0's and 3 1's is {"10", "0001", "1", "0"}, so the answer is 4.
Other valid but smaller subsets include {"0001", "1"} and {"10", "1", "0"}.
{"111001"} is an invalid subset because it contains 4 1's, greater than the maximum of 3.

Example 2:

Input: strs = ["10","0","1"], m = 1, n = 1
Output: 2
Explanation: The largest subset is {"0", "1"}, so the answer is 2.

 

Constraints:

• 1 <= strs.length <= 600
• 1 <= strs[i].length <= 100
• strs[i] consists only of digits '0' and '1'.
• 1 <= m, n <= 100

Answer:

class Solution {
    /**
    *To better understand, DP[][] can be rewrite as DP[][][], 
    *e.g. DP[0][i][j] = 0 means when the string array is empty, 
    *we can not form any string. Then we put the first element of strs in our pool,
    *and we can write DP[1][i][j]=Math.max(DP[0][i][j], 1+DP[0][i-c[0]][j-c[1]]);
    *(for each i and j). Actually, we find that each time we add one more string k,
    *DP[k][i][j]=Math.max(DP[k-1][i][j], 1+DP[k-1][i-c[0]][j-c[1]]). 
    *Since each i and j will not be influenced by higher i,j, 
    * and DP[k-1] will not be used in the future, 
    * we can iterate backward and update DP[i][j] in place. 
    * In the end, we return DP[m][n] which is actually DP[strs.length][m][n].
    *
    **/
    public int findMaxForm(String[] strs, int m, int n) {
        if(strs.length==0) return 0;
        int[][] DP=new int[m+1][n+1];
        for(String str:strs){
            int[] c=count(str);
            for(int i=m;i>=c[0];i--){
                for(int j=n;j>=c[1];j--){
                    DP[i][j]=Math.max(DP[i][j], 1+DP[i-c[0]][j-c[1]]);
                }
            }
        }
        return DP[m][n];

    }
    int[] count(String str){
        int[] c=new int[2];
        for(int i=0;i<str.length();i++){
            c[str.charAt(i)-'0']++;
        }
        return c;
    }
}

My Summary: the key points here are: 

1. since there could be multiple combinations as result meeting requirements, the best solution is very likely to be using DP

2. DP solution's key point is to figure out the X/Y Axis, and the relation between DP[X(k)i][X(k)j] and DP[X(k+1)i][X(k+1)j], Xk and X(k+1) is element in original array and its following element.