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.
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.
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!
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.
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 :).
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!!!
Goddamn kevin, that copy current list was where I lacked(I was passing the original one). Thanks for the info legend.
This solution is definitely derived after lot of attempts... Amazing solution
Thanks for sharing this solution. Could you also please share the time and space complexity for solutions and talk about trade offs.
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)
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?
Anyone know if the person who made the intro song has another channel or has other online presence? Loved the beat & great video!
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.
Great video :)
What's the time complexity??
wondering the same.
What will be time complexity to make a new arraylist from already present arraylist?
Why do you create a copy of list current in recursive call and what does that list contain?
Why do you pass a copy of the current list and not the same list ?
Nice Explanation. Keep these high quality videos coming. :)
Thanks Deepak and will do :)
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.
Bring some series of graph questions
why you passed new copy of arraylist instead of passing original in recursion ?
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!!!
Hi Kevin, thanks for posting the videos. Can you do a video on Longest Duplicate Substring?
I see path sum i and ii. when's III coming? :)
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.
Is the space complexity is ON² ？
I can't understand why we can't pass the same list. Why does that fail?
Can anybody please help me understand.
Awesome
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.
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!!!
what is the complexity ?
would you be able to implement this iteratively using dfs?
why we need a unique list every recursion
Note: make sure to path new ArrayLIST(current) in recursion
Why
Amazon boy!!
THANK YOU!!!
what's the time complexity for this??
Could you solve LeetCode 523 (Continuous Subarray Sum)?
I'll see what I can do thanks for the suggestion!
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;
}
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
I think u should use a pen to make students understand
What about complexities?
Can this be resolved by Dynamic Programming
I am sorry to say Kevin bro , I am close to exhausting all your medium level problems.. yup its that good.. upload more ....
Pls make a video on path sum 3
Nice video!!
Thanks Spark!!!
Completing 800 problems on Leetcode prints you Facebook/Google offer. Practice 24*7. Don't eat, drink, poop, fart, sleep.
Am I deaf?
Lmao nice thumbnail
haha thanks Atif
@@KevinNaughtonJr np Kevin!
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.
I came here from chatgpt hahaha
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 :).