Leetcode Daily - August 8, 2020

Path Sum III

Link to Leetcode Question

Lately I've been grinding Leetcode and decided to record some of my thoughts on this blog. This is both to help me look back on what I've worked on as well as help others see how one might think about the problems.

However, since many people post their own solutions in the discussions section of Leetcode, I won't necessarily be posting the optimal solution.

Question

(Copy Pasted From Leetcode)

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 Approach(es)

I won't go over all the code for all attempts but I will explain my approach(es) qualitatively.

Attempt 1 - DFS or BFS

(Submission - Accepted)

After looking at the expected answer of the example, I was a little worried. For a given long path, I thought about the complexity of finding all the combination of paths and then their sums. For example, from root to the bottom left is 10 -> 5 -> 3 -> 3. There are 4 + 3 + 2 + 1 = 10 paths, because there is one path of length 4, two of length 3, three of length 2 and four of length 1.

However, I thought about how to record these path sums and realized that recording the whole path then checking the sum of all combinations was a bit cumbersome. If a binary tree has k levels, the path would require storage of O(k), and the time complexity becomes O(k^2) combinations per check.

I decided to store the sums of all paths leading to the current node. Each node would have to do a calculation of adding its own value to this array, but also push its value to the array to represent the path starting and ending at itself. If a binary has k levels, then this array's storage and the adding operation's time complexity should both be O(k).

var pathSum = function(root, sum) {
    // dfs or bfs while storing a sums array 
    // when it reaches a certain node, add val to all in the sums array then push val 
    // finally, if any paths are equal to sum then counter ++ 
    let counter = 0;
    let stack = [{
        ...root,
        sums: []
    }]
    while (stack.length > 0) {
        const currNode = stack.pop();

        // process sums array 
        const newSums = currNode.sums.map(s => s+currNode.val);
        newSums.push(currNode.val);
        newSums.forEach(s => {
            if (s === sum) {
                counter++;
            }   
        })

        if (currNode.left) stack.push({...currNode.left, sums: newSums});
        if (currNode.right) stack.push({...currNode.right, sums: newSums});
    }

    return counter
};

Discussion and Conclusions

I've done a lot of binary tree problems on Leetcode now and was able to complete a majority of them using depth and breadth first search. In this case, I haven't thought of a good idea to map this binary tree into another data structure, but instead how to calculate instances of the path sum while traversing the existing data structure. I will try to explore and keep in mind other ways to approach this problem.