Path Sum III | Leetcode 437 | Live coding session 🔥🔥🔥

Here is the solution to "Path Sum III" leetcode question. Hope you have a great time going through it.

1) 0:00 Explaining the problem out loud
2) 1:10 Algorithm walkthrough
3) 5:00 Coding it up

For discussion/feedback

PS : Please increase the speed to 1.25X

[adityasaini]

Just change the "int sum" to "long sum" to pass the new test cases

class Solution {
private int count = 0;

private void dfs(TreeNode root, long sum){
if(root == null) return;

if(sum == root.val) count += 1;

dfs(root.left, sum - root.val);
dfs(root.right, sum - root.val);

}

public int pathSum(TreeNode root, int targetSum) {
if(root == null) return 0;
// preorder
dfs(root, targetSum);
pathSum(root.left, targetSum);
pathSum(root.right, targetSum);

return count;
}
}

[sureshchaudhari]

U r explaining in a very simple way.it does not feel like it's difficult topic.nice explanation and interesting explanation

[jackwalker]

Can be solved in O(n) using unordered map just like we do for two sum problem(hashing approach) .
Btw O(n²) approach is very easy to understand 😀...but interviewer may ask for optimization.

[manjeetyadav]

if (root == null || root.val == Math.pow(10, 9)) return;
if (sum == root.val) ans++;
sum = sum-root.val;
There is a new testcase and the code is failing at that case . This little change in helper method will make it fine

[sanchitbatra]

Why don't we do take it or leave it strategy in here?

[elasingh]

pathSum(root.left, targetSum);
pathSum(root.right, targetSum);

How can we call these methods without any return type?

[veronicadey]

I already thought of the O(N*N) method, searched the YouTube for an optimised method, later found out that N^2 is itself the optimised one 😂

[deveshgupta]

why this function is incoorect.
int helper(TreeNode* root, int targetSum){
if(!root) return 0;
if(root->val == targetSum) return 1;

return helper(root->left, targetSum - root->val) + helper(root->right, targetSum - root->val);
}

[vasanthanv]

Hi, Good explanation, the code in the video is failing for this testcase
0