# Path Sum III | Solution Explained

LeetCode 437. Path Sum III. I explain the brute-force solution and the optimized solutions in detail for reducing O(N^2) to O(N) time. Problem Link.

## 0. Setup

## 1. Path Sum III: Brute-force

### 1.0. Core Logic

Focusing on the line, “*The path does not need to start or end at the root or a leaf, …*“, we can conclude that we can start from *any* point.

In other words, we can ** restart** our counting of the path sum from anywhere we like. We can either:

- start the sum counting from 0 – restarting
- continue the sum from what the parent gave us

### 1.1. Formalized Logic

Let’s formalize this. Since we want to search for a path in a tree, we are going to use depth first search (DFS). It takes in the input as `dfs(node, curr, reset)`

where:

`node`

: the current node in consideration`curr`

: the current path sum`reset`

: whether a request for resetting the curr was sent or not. NOTE we can’t directly check for`curr == 0`

to know if the sum has resetted – there can be cases like`x+y = 0`

where`x = 2, y = -2`

. In this case, no reset request is sent.

We generate 4 dfs-es from this point:

`dfs(node.left, curr, 0)`

`dfs(node.right, curr, 0)`

`dfs(node.left, 0, 1)`

`dfs(node.right, curr, 0)`

Finally, we have to consider cases of repetition. Consider:

In this case, say we start from x. We go to y with score x. From y we go to z with curr as x+y (due to cumulative effect).

At the point z, one of the cases I’ll consider is the case of ** resetting**. This is fine and perfectly allowed.

Let’s take another case. Instead of starting from x, let’s say this time y sends a ** reset request**.

Now the curr becomes 0. At the point x, we receive curr = y. What if … we again decide to ** reset **at point z?

This essentially means we are considering the same node again and again. To prevent that, we have additional logic for handling ** resetted **nodes.

### 1.2. Code

# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int: def dfs(node, curr, reset): if not node: return 0 if node in resetted and reset: return 0 if curr == 0 and reset: resetted.add(node) count = 0 curr += node.val if curr == targetSum: count += 1 count += dfs(node.left, curr, 0) count += dfs(node.right, curr, 0) count += dfs(node.left, 0, 1) count += dfs(node.right, 0, 1) return count resetted = set() return dfs(root, 0, 1)

### 1.3. Complexity

- Time:
`O(N^2)`

since for each node, we have to explore 4 more cases for the rest of the nodes. Basically,`O(N*4N)`

. - Space:
`O(N)`

.`O(N)`

for storing resetted and`O(N)`

for the height of the recursion call stack height.

## 2. Path Sum III: Optimization

The idea of cumulative sums is interesting. Perhaps we can exploit that.

Consider a 1D case, of an array. We just take the left branch of the tree: `[10, 5, 3, 3]`

Let’s say we have the goal of querying the array for sum, as `sum(i:j)`

. This operation can take `O(N)`

worst case time. But, how can we reduce it to `O(1)`

?

We can find out the cumulative sums.

In this way, we can query in `O(1)`

time:

Coming back to the Path Sum III question, we can replace the logic for the ** resetting **thing with cumulative sum logic. We are anyways computing the cumulative sum as

`curr += node.val`

. Now, we have one big issue.In arrays it is rather easy to calculate the difference *because* we have access to the elements in O(1) time in the `cumu`

array.

For this case, we have to create a data structure that can store all of the values it has accessed. We can create a `count = defaultdict(int)`

in Python3.

`count`

is a dictionary as `key = node.val : value = count/frequency`

.

*Before* calling `dfs(node.left/right, curr)`

, we are going to set `count[curr+targetSum] += 1`

, since we want to ** bait **a future dfs call with

`curr(future) == curr(now) + targetSum`

. If that happens, we happily do `ans += count[curr]`

saying that the frequency stored before is **since we have reached an end point where the diff of**

*valid*`curr(future)`

and `curr(now)`

is the same as `targetSum`

. Perhaps the visualization & code makes things clear :sweat_smile:### 2.1. Code

class Solution: def pathSum(self, root, targetSum): def dfs(node, curr): if not node: return nonlocal ans, count curr += node.val ans += count[curr] # if you need help understanding the solution # print(f"node: {node.val}:: curr: {curr}, count: {count[curr]}\ncount={count}\n\n") count[curr+targetSum] += 1 dfs(node.left, curr) dfs(node.right, curr) count[curr+targetSum] -= 1 ans = 0 count = defaultdict(int) count[targetSum] = 1 dfs(root, 0) return ans

### 2.2. Complexity Analysis

- Time:
`O(N)`

since we go over all the nodes only once. - Space:
`O(N)`

since we store the`count`

dictionary &`O(N)`

more for the height of the recursion call stack.

*Thanks for reading!*

### Recommended Posts

##### Gas Station | InterviewBit | Solution Explained

June 13, 2022

##### Majority Element | InterviewBit | Solution Explained

June 13, 2022

##### Seats | InterviewBit | Solution Explained

June 13, 2022