Hello Kevin! I think I have another problem suggestion for you, Could you please solve LeetCode #127 Word Ladder? This one actually appeared in a Mock Interview I did yesterday with a Facebook Engineer. He also asked me to solve #66 but that one is trivial (or is it?). Let me know What do you think, and have a great day.
Hi Kevin. I want to become a patron but I had some doubts regarding the tier I want to choose. Please let me know if I can talk to you about it. Thanks.
hey kevin ,your solution is so clear and nice ,but can you optimize it to be faster ,currently 95 % of other solutions on leetcode are faster.we appreciate your effort and support .and second what are the complexity for your code .you didn't mentioned it .
Thanks for your videos. It really helps to get an idea of the problem solving. I would like to have a request to go over the different approaches so that we can think of different trade offs before coding the actual problem as it is a key aspect for an interview.
Thanks for posting and great video. Small optimization is that you could keep the same list and backtrack when a solution is not correct instead of creating a new list at every iteration. For people wondering it would look something like: if(root == null) return; current.add(root.val); if(sum == root.val && root.left == null && root.right == null) paths.add(new ArrayList(current); findPaths(root.left, sum - root.val, current, paths); findPaths(root.right, sum - root.val, current, paths); current.remove(current.size() - 1); //if we hit null recurse back up through stack and remove elements in current list Thanks for the content and keep the videos coming!
@@studyaccount794 If you have a return in the if statement then you don't properly remove elements from the list. Lets look at a simple example. 1 / \ 2 2 Where the target sum = 3. Also to note here that we are subtracting from sum based on the above code. Iteration 1: list = [1] sum = 3 Iteration 2: list = [1,2] sum = 2 == root.val. Add this list to the results list and return. Now we moved back up the call stack to node 1, but we never recursed back through our list.remove() part so there is an extra 2. Iteration 3: list = [1,2] sum = 3 Iteration 4: list = [1,2,2] sum = 2 == root.val. Add this to the results list and return. End result [[1,2],[1,2,2]]. Which is incorrect. Hope this helps.
Kevin, I just can't tell you how helpful you are to me! You are making every question on leetcode easier with your channel here. Would you please do the same for the hard problems too?
could anyone please explain why we should not remove the nodes from current list after the two recursive calls?, suppose if the root to leaf path sum of left child is not equal to the target in that case we have to remove that left leaf node from the current list and then check for the right leaf node.
Hi Kevin, I have a question regarding backtracking. I've seen other code that have a line like "current.remove(current.length - 1)", and they also passed. I didn't fully understand why that line would be necessary in that case, and how that is different from your method.
As someone who has recently started doing leetcode/hackerrank, what advice do you have to improve my abilities (ie. What are some important data structures, algorithms, process to tackle problem)
Hey Afzal, I think the biggest thing I'd suggest (besides just practicing) is to try and get good at recognizing what ds / algos are useful for what problems...understand when a hash map, stack, heap, etc is useful in certain situations and why! Let me know if you have any other questions or if there's anything I can do to help you!
I'm not sure why output becomes [[5,4,11,2],[5,4,8,4,5]] when I use backtracking and still keep return in if(root.val == target && root.left == null && root.right ==null) this condition. If I remove return statement, the output is correct.
Recursion is easiest way to solve this problem. But resursion is difficult to understand & easy to write (Only after understanding :P). That's why I am here :).
Please use some drawing board, whiteboard etc to explain the solution. u always talk verbally about all of these complex problems, no fresher can understand this.
If there's anything I can do to help you guys be sure to leave me a comment and I'll see what I can do!
Hello Kevin! I think I have another problem suggestion for you, Could you please solve LeetCode #127 Word Ladder? This one actually appeared in a Mock Interview I did yesterday with a Facebook Engineer. He also asked me to solve #66 but that one is trivial (or is it?). Let me know What do you think, and have a great day.
@@jlecampana I'll check them out thanks for the suggestions! I hope you ave a great day too!
Hi Kevin. I want to become a patron but I had some doubts regarding the tier I want to choose. Please let me know if I can talk to you about it.
Thanks.
hey kevin ,your solution is so clear and nice ,but can you optimize it to be faster ,currently 95 % of other solutions on leetcode are faster.we appreciate your effort and support .and second what are the complexity for your code .you didn't mentioned it .
Thanks for your videos. It really helps to get an idea of the problem solving. I would like to have a request to go over the different approaches so that we can think of different trade offs before coding the actual problem as it is a key aspect for an interview.
Thanks for posting and great video. Small optimization is that you could keep the same list and backtrack when a solution is not correct instead of creating a new list at every iteration. For people wondering it would look something like:
if(root == null) return;
current.add(root.val);
if(sum == root.val && root.left == null && root.right == null)
paths.add(new ArrayList(current);
findPaths(root.left, sum - root.val, current, paths);
findPaths(root.right, sum - root.val, current, paths);
current.remove(current.size() - 1); //if we hit null recurse back up through stack and remove elements in current list
Thanks for the content and keep the videos coming!
Anytime Adam! So smart thanks for awesome optimization!!!
but for some reason you need to put return after removing last element from stack or it won't work,not sure why
I wonder why there's no return statement in the if condition.
@@studyaccount794 If you have a return in the if statement then you don't properly remove elements from the list. Lets look at a simple example.
1
/ \
2 2
Where the target sum = 3. Also to note here that we are subtracting from sum based on the above code.
Iteration 1: list = [1] sum = 3
Iteration 2: list = [1,2] sum = 2 == root.val. Add this list to the results list and return.
Now we moved back up the call stack to node 1, but we never recursed back through our list.remove() part so there is an extra 2.
Iteration 3: list = [1,2] sum = 3
Iteration 4: list = [1,2,2] sum = 2 == root.val. Add this to the results list and return.
End result [[1,2],[1,2,2]]. Which is incorrect.
Hope this helps.
I don't know if you're still doing these videos but keep them coming. Concise, precisely explained. Ty.
Hi Kevin, first of all , awesome explanation, can you please explain why we create a new ArrayList for every recursive call ?
Damn you make every problem feel so simple.
Absolutely incredible! Can you please solve some DP and linked lists questions as well? Keep up the good work.
You've got it and thanks Shubham I appreciate it!!!
Nice explanation sir .
I have a doubt i.e during the recursive call what happen if we pass current in parameter instead of new ArrayList(current)
Thanks for sharing this solution. Could you also please share the time and space complexity for solutions and talk about trade offs.
Kevin, I just can't tell you how helpful you are to me! You are making every question on leetcode easier with your channel here. Would you please do the same for the hard problems too?
Goddamn kevin, that copy current list was where I lacked(I was passing the original one). Thanks for the info legend.
Anyone know if the person who made the intro song has another channel or has other online presence? Loved the beat & great video!
Great video :)
What's the time complexity??
wondering the same.
Thanks Kevin... You explain the things in easiest way. Could you please explain non recursive approach as well to this problem?
Why do you create a copy of list current in recursive call and what does that list contain?
What will be time complexity to make a new arraylist from already present arraylist?
could anyone please explain why we should not remove the nodes from current list after the two recursive calls?, suppose if the root to leaf path sum of left child is not equal to the target in that case we have to remove that left leaf node from the current list and then check for the right leaf node.
This solution is definitely derived after lot of attempts... Amazing solution
Nice Explanation. Keep these high quality videos coming. :)
Thanks Deepak and will do :)
Hi Kevin, thanks for posting the videos. Can you do a video on Longest Duplicate Substring?
Hi Kevin, I have a question regarding backtracking. I've seen other code that have a line like "current.remove(current.length - 1)", and they also passed. I didn't fully understand why that line would be necessary in that case, and how that is different from your method.
so its like a take or not take ,so when u perform adding element to current solution your taking ,then u perform not take by removing the element
The code with backtracking runs faster than Kevin's code, cause it only creates a new instance of ArrayList when the list needs to be added to result.
Why do you pass a copy of the current list and not the same list ?
It's cool that you usually do problems I tried recently myself, Here's my solution to this one in C++, it's a basic DFS I think.
void pathSum(TreeNode *root, int currSum, int target, vector path, vector &paths) {
if (root == NULL)
return;
if ((root->val + currSum) == target && (root->left == NULL && root->right == NULL)) {
path.push_back(root->val);
paths.push_back(path);
} else {
path.push_back(root->val);
pathSum(root->left, root->val + currSum, target, path, paths);
pathSum(root->right, root->val + currSum, target, path, paths);
}
}
vector pathSum(TreeNode* root, int sum) {
vector paths;
pathSum(root, 0, sum, vector(), paths);
return paths;
}
Nice!!!
I see path sum i and ii. when's III coming? :)
why you passed new copy of arraylist instead of passing original in recursion ?
Bring some series of graph questions
Is the space complexity is ON² ?
As someone who has recently started doing leetcode/hackerrank, what advice do you have to improve my abilities (ie. What are some important data structures, algorithms, process to tackle problem)
Hey Afzal, I think the biggest thing I'd suggest (besides just practicing) is to try and get good at recognizing what ds / algos are useful for what problems...understand when a hash map, stack, heap, etc is useful in certain situations and why! Let me know if you have any other questions or if there's anything I can do to help you!
thanks so much, and thank you for such great content, really goes a long way to help people out!
@@afzalchishti9092 Anytime Afzal that's all I want to do so I'm happy to hear it's helping!!!
I'm not sure why output becomes [[5,4,11,2],[5,4,8,4,5]] when I use backtracking and still keep return in if(root.val == target && root.left == null && root.right ==null) this condition. If I remove return statement, the output is correct.
Note: make sure to path new ArrayLIST(current) in recursion
Why
What does using the 'new' keyword do when passed as a parameter?
Umm would it still work without current list? If not, could you please explain why we need 'current'?
Thanks!
I was thinking of the same thing. but as we need output in the form of List we need to have an intermediate List.
Hi Kevin ! Can you make one video for solving Path Sum III I tried to understand the O(n) solution but could not get any
Could you solve LeetCode 523 (Continuous Subarray Sum)?
I'll see what I can do thanks for the suggestion!
what is the complexity ?
Amazon boy!!
what's the time complexity for this??
Awesome
I am sorry to say Kevin bro , I am close to exhausting all your medium level problems.. yup its that good.. upload more ....
would you be able to implement this iteratively using dfs?
I can't understand why we can't pass the same list. Why does that fail?
Can anybody please help me understand.
why we need a unique list every recursion
What about complexities?
I think u should use a pen to make students understand
Can this be resolved by Dynamic Programming
Nice video!!
Thanks Spark!!!
THANK YOU!!!
Pls make a video on path sum 3
Lmao nice thumbnail
haha thanks Atif
@@KevinNaughtonJr np Kevin!
I came here from chatgpt hahaha
Completing 800 problems on Leetcode prints you Facebook/Google offer. Practice 24*7. Don't eat, drink, poop, fart, sleep.
WHAT IS WRONG WITH THE FOLLOWING CODE???
void dfs(TreeNode* node,vector&ans,vector&curr,int target)
{
if(node==NULL)
return;
curr.push_back(node->val);
if(node->left==NULL && node->right==NULL && node->val==target)
{
ans.push_back(curr);
return;
}
dfs(node->left,ans,curr,target-node->val);
dfs(node->right,ans,curr,target-node->val);
}
vector pathSum(TreeNode* root, int target)
{
vectorans;
vectorcurr;
dfs(root,ans,curr,target);
return ans;
}
Am I deaf?
thanks as usual.. pls no recursion.
Haha why no recursion?!?!
Recursion is easiest way to solve this problem. But resursion is difficult to understand & easy to write (Only after understanding :P). That's why I am here :).
Please use some drawing board, whiteboard etc to explain the solution. u always talk verbally about all of these complex problems, no fresher can understand this.