This is Yizhe's Blog: Solved

Friday, January 29, 2021

272. Closest Binary Search Tree Value II

Given a non-empty binary search tree and a target value, find k values in the BST that are closest to the target.

Note:

Given target value is a floating point.
You may assume k is always valid, that is: k ≤ total nodes.
You are guaranteed to have only one unique set of k values in the BST that are closest to the target.

Example:

Input: root = [4,2,5,1,3], target = 3.714286, and k = 2

    4
   / \
  2   5
 / \
1   3

Output: [4,3]

Follow up:

Assume that the BST is balanced, could you solve it in less than O(n) runtime (where n = total nodes)?

My answer: get sorted array from BST, and then find the smallest element bigger than or equal to target, and then find closet k element starting from that element.

Other solutions are put at the end.

/**
 * 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<Integer> closestKValues(TreeNode root, double target, int k) {
        List<Integer> values = new ArrayList<Integer>();
        inorder(root, values);
        Integer[] vs = values.toArray(new Integer[0]);
        int l = 0;
        int r = vs.length - 1;
        int ceil = (int) Math.ceil(target);
        int floor = (int) Math.floor(target);
        
        // find the last element bigger than or equal to ceil,
        // and l stores the index of it
        while(l < r ) {
            int m = (l + r) / 2;
            if (vs[m] > ceil) {
                r = m;
            } else {
                l = m + 1;
            }
        }
        l --;
        r = l + 1;
        List<Integer> result = new ArrayList<Integer>();
        while (k > 0) {
            if (l == -1) {
                result.add(vs[r]);
                r++;
                k--;
                continue;
            }
            if (r == vs.length) {
                result.add(vs[l]);
                l --;
                k--;
                continue;
            }
            if (Math.abs(target - (double) vs[l]) < Math.abs(target - (double) vs[r])) {
                result.add(vs[l]);
                l --;
            } else {
                result.add(vs[r]);
                r ++;
            }
            k --;
        }
        return result;
        
    }
    
    private void inorder(TreeNode node, List<Integer> values) {
        if (node == null) {
            return;
        }
        inorder(node.left, values);
        values.add(node.val);
        inorder(node.right, values);
    }
}

Leetcode's solution: all the answers are based on array containing distance to the target.

There are three ways to solve the problem:

Approach 1. Sort, $\mathcal{O}(N \log N)$ time. The idea is to convert BST into an array, sort it by the distance to the target, and return the k closest elements.
Approach 2. Facebook-friendly, heap, $\mathcal{O}(N \log k)$ time. We could use the heap of capacity k, sorted by the distance to the target. It's not an optimal but very straightforward solution - traverse the tree, push the elements into the heap, and then return this heap. Facebook interviewer would insist on implementing this solution because the interviews are a bit shorter than Google ones, and it's important to get problem solved end-to-end.
Approach 3. Google-friendly, quickselect, $\mathcal{O}(N)$ time. Here you could find a very detailed explanation of quickselect algorithm. In this article, we're going to provide a relatively brief implementation. Google guys usually prefer the best-time solutions, well-structured clean skeleton, even if you have no time to implement everything in time end-to-end

Tuesday, December 22, 2020

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.

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

Labels

Friday, January 29, 2021

272. Closest Binary Search Tree Value II

Tuesday, December 22, 2020

437. Path Sum III