If you liked this, you'll also like my other LeetCode videos. There are just a few now but I'm planning to add more: ruclips.net/p/PLViRFZPCqDBekVh0L_cyg6DLl2fPYbAJM.
I am a visual learner and have been a software engineer for over 10 years. This is by far the most clear (and beautiful) explanation of any algorithm I've ever seen. I will be anticipating with excitement your next videos. Please keep this format!
This was really excellent. The animation for the brute force solution was such a useful and concrete way of holding the solution in my head. It made it much easier to follow each of your questions, and the systematic way you approached improving on your initial solution, all while being assured of correctness. The take-aways for me: - look for insights to solve the problem by diagramming - use prompts to improve your solution e.g. perfect information - don't code until you're certain of your approach - use simple examples to test out ideas
Amazing video! I love that you begin with the simplest brute force approach and improve on it incrementally. The questions you ask yourself during the problem solving process are really useful. They give me a clue on how I could come up with the solutions on my own. Other Two Sum videos I watched skipped straight from brute force to the one pass approach. I like that you provided the two pass solution and also explained that it's arguably the better approach in comparison to the one pass.
Thanks Anthony! Yeah prompting yourself with these types of questions is the absolute key to coming up with the solutions on your own. Glad you noticed this. I tried as hard as I could to emphasize this message. It's like using the socratic method with yourself.
Thank you so much for the detailed analysis. I just started LeetCode and struggled with it, but now I think I can make it! Thank you for your guidance❤
This is the most clear explanation of an algorithm I have ever seen. Awesome, subscribing now. Hoping to see more. Thank you for this beautiful explanation it helps a lot.
You're welcome and thank you! I have a full playlist with more videos like this and am working to add more: ruclips.net/p/PLViRFZPCqDBekVh0L_cyg6DLl2fPYbAJM
Incredible ! I need to get my algorithmic logic together in order to pass interview tests. It's my main weakness. I very good with html and css but not abstract thinking. And you are right when you say that if you observe and focus on the questions/hints, it takes you to the solution.
Thanks Allan! I'm glad you noticed how important the line of reasoning is (represented by the question path). Most people don't understand the significance and think it's just a visual flourish.
Wonder if they make sense; 1) numberToIndex[num[i]] = i has to go last: Avoid returning the same index when num[i] is exactly half the target. 2) numberToIndex[numberNeeded] !== i is not needed anymore: When numberToIndex[num[i]] = i goes last, the current index i will not be in the map YET. So in the case of two elements(different indexes) having the same value(exactly half the target), index i and the index stored at numberToIndex[numberNeeded] will always be different and correct. Production value is great Gordon! Love the simple yet very functional animations in terms of visualizing the thought process.
It's great that you thought more about this!(I'm assuming you're talking about the two prompts I mentioned around 9:21.) For your first point, assume that the target pair is two of the same number (e.g. [5, 5], target = 10). If you put `numberToIndex[numberNeeded] !== i` at the top of the loop, when you examine the second 5, you'll wipe out information about the first 5, making it impossible to ever return the correct pair. Your reasoning implies that there may be a selection issue that you could somehow fix it if you avoided reusing the same index. I think this is a subtle but important distinction. So what you're saying is true, but obfuscates the key issue.
@@GordonZhu About the first point: Would we ever reach the second 5 though? If we are at the first 5, add it to the map & then run the check, it should return the index twice (once as variable i, once as value of key 5). Or did your question assume that we first only move the mapping of the number/index to the end but still keep the 2nd condition in the if clause? Because then what you described (overwriting first occurence) would happen. It looks like Kenny & I both assumed that we make both changes at once.
@@Lauchmeister Sure, that's what would happen in the situation you described, but that's not what I was describing. Note the specific sequence I followed in the video. 1) First, why do you need to write to the map at the bottom and not at the top? At that time, the index check was present. 2) Second, now that you're writing to the map at the bottom (because you know you have to), why is the index check no longer necessary?
Thank you @Timeus80 :). Check out my full playlist of similar videos here (I just added a new one today): ruclips.net/p/PLViRFZPCqDBekVh0L_cyg6DLl2fPYbAJM. Also very cool to see that you're a professional musician. My students that are also professional musicians have said that my approach to programming reminds them a lot of music (importance of fundamentals, attention to nuances in method/technique, ability to find weaknesses objectively and correct them, importance of quality feedback, etc).
Holy crap! Best visuals for thinking about algorithms wrt ds+a, really helps me visualize the solution. I don’t know how I didn’t find your channel sooner but please continue putting out bangers like this! Funny pat is I had already solved this problem before and I actually solved it using the last solution because that was the first thing I thought of. I never thought of the one pass solution but the part I think I need to practice and learned the most from was the questions you asked to come up to the solutions. I never thought or the idea of “perfect information”, was that something you came up with yourself or a concept formalized somewhere where I can learn more?
I like the explanation! But also, I'm confused a little. Can you explain why you take the average for the inner loop (n/2) but not the (n-1)? Thank you🙏
One question, from a non CS graduate, why this solution doesn’t also jump to the next element if bigger or equal to the target sum? Thus reducing the map size and evaluation of previous elements, considering no negative numbers. Second the one pass solution also has a different effect, might not guarantee that you have chosen the bigger index for the value, as you might not have encountered it before finding the solution. Also the two pass might have an issue if you need two identical values for the target, with two different indexes.
1. You can't assume no negative numbers. The question says "integers". 2. I exhaustively explain why the 1-pass is guaranteed to work at 9:58 - 11:30. 3. I directly answer your last question at 6:18.
![Felix "Unfair" | [Stray Kids : SKZ-PLAYER]](http://i.ytimg.com/vi/Oswujxm2Ag0/mqdefault.jpg)
The best breakdown I have ever came across! EVER. Thank you for the intense amount of work that went into this video.
Thanks so much! Haha yeah it was a sh**load of work.
If you liked this, you'll also like my other LeetCode videos. There are just a few now but I'm planning to add more: ruclips.net/p/PLViRFZPCqDBekVh0L_cyg6DLl2fPYbAJM.
Very underrated channel. Very creative way to teach! You're going to go big in future for sure!
Thanks Shantanu. Appreciate the support :)
I am a visual learner and have been a software engineer for over 10 years. This is by far the most clear (and beautiful) explanation of any algorithm I've ever seen. I will be anticipating with excitement your next videos. Please keep this format!
Thank you Germain! I really like how this turned out and I'm excited for what's next too!
you expressed the thought so well, i m even pleased
To teach this way requires not only meticulous technique, but also a high dose empathy. Great work as always
Thank you Jim! Yeah I'm always trying to get inside the mind of my students. Makes all the difference.
Wow! I love how you explain how the one pass solution is actually not great (for clarity and mental overhead). Excellent video!
Glad you liked that part specifically :) It had to be said!
I loved this... subscribed and liked!!!!
Thanks Antonio!
Love your video mate, wish you luck with your future videos
This was really excellent. The animation for the brute force solution was such a useful and concrete way of holding the solution in my head. It made it much easier to follow each of your questions, and the systematic way you approached improving on your initial solution, all while being assured of correctness.
The take-aways for me:
- look for insights to solve the problem by diagramming
- use prompts to improve your solution e.g. perfect information
- don't code until you're certain of your approach
- use simple examples to test out ideas
Dude, this is very good. I hope your channel grows
Thank you!
Amazing video! I love that you begin with the simplest brute force approach and improve on it incrementally. The questions you ask yourself during the problem solving process are really useful. They give me a clue on how I could come up with the solutions on my own.
Other Two Sum videos I watched skipped straight from brute force to the one pass approach. I like that you provided the two pass solution and also explained that it's arguably the better approach in comparison to the one pass.
Thanks Anthony! Yeah prompting yourself with these types of questions is the absolute key to coming up with the solutions on your own. Glad you noticed this. I tried as hard as I could to emphasize this message. It's like using the socratic method with yourself.
Thank you so much for the detailed analysis. I just started LeetCode and struggled with it, but now I think I can make it! Thank you for your guidance❤
You're welcome Grace! Keep working at it!
this channel is so underrated, today i discovered Two Sum problem and decided to know more about it, thanks for this video
Appreciate this a lot and you're welcome!
This is the most clear explanation of an algorithm I have ever seen. Awesome, subscribing now. Hoping to see more. Thank you for this beautiful explanation it helps a lot.
You're welcome and thank you! I have a full playlist with more videos like this and am working to add more:
ruclips.net/p/PLViRFZPCqDBekVh0L_cyg6DLl2fPYbAJM
Incredible !
I need to get my algorithmic logic together in order to pass interview tests. It's my main weakness. I very good with html and css but not abstract thinking. And you are right when you say that if you observe and focus on the questions/hints, it takes you to the solution.
Thanks Allan! I'm glad you noticed how important the line of reasoning is (represented by the question path). Most people don't understand the significance and think it's just a visual flourish.
Wonder if they make sense;
1) numberToIndex[num[i]] = i has to go last:
Avoid returning the same index when num[i] is exactly half the target.
2) numberToIndex[numberNeeded] !== i is not needed anymore:
When numberToIndex[num[i]] = i goes last, the current index i will not be in the map YET. So in the case of two elements(different indexes) having the same value(exactly half the target), index i and the index stored at numberToIndex[numberNeeded] will always be different and correct.
Production value is great Gordon! Love the simple yet very functional animations in terms of visualizing the thought process.
It's great that you thought more about this!(I'm assuming you're talking about the two prompts I mentioned around 9:21.)
For your first point, assume that the target pair is two of the same number (e.g. [5, 5], target = 10). If you put `numberToIndex[numberNeeded] !== i` at the top of the loop, when you examine the second 5, you'll wipe out information about the first 5, making it impossible to ever return the correct pair.
Your reasoning implies that there may be a selection issue that you could somehow fix it if you avoided reusing the same index. I think this is a subtle but important distinction. So what you're saying is true, but obfuscates the key issue.
@@GordonZhu About the first point: Would we ever reach the second 5 though? If we are at the first 5, add it to the map & then run the check, it should return the index twice (once as variable i, once as value of key 5).
Or did your question assume that we first only move the mapping of the number/index to the end but still keep the 2nd condition in the if clause? Because then what you described (overwriting first occurence) would happen. It looks like Kenny & I both assumed that we make both changes at once.
@@Lauchmeister Sure, that's what would happen in the situation you described, but that's not what I was describing. Note the specific sequence I followed in the video. 1) First, why do you need to write to the map at the bottom and not at the top? At that time, the index check was present. 2) Second, now that you're writing to the map at the bottom (because you know you have to), why is the index check no longer necessary?
awesome visual representation!!
Thank you Mica!
Great job! Thank you so much! Love the mindset and the realization of the video. Subscribed right away :)
Thank you @Timeus80 :). Check out my full playlist of similar videos here (I just added a new one today): ruclips.net/p/PLViRFZPCqDBekVh0L_cyg6DLl2fPYbAJM.
Also very cool to see that you're a professional musician. My students that are also professional musicians have said that my approach to programming reminds them a lot of music (importance of fundamentals, attention to nuances in method/technique, ability to find weaknesses objectively and correct them, importance of quality feedback, etc).
Best explanation on the internet 🎉
Thank you Pranav!
Holy crap! Best visuals for thinking about algorithms wrt ds+a, really helps me visualize the solution. I don’t know how I didn’t find your channel sooner but please continue putting out bangers like this!
Funny pat is I had already solved this problem before and I actually solved it using the last solution because that was the first thing I thought of. I never thought of the one pass solution but the part I think I need to practice and learned the most from was the questions you asked to come up to the solutions. I never thought or the idea of “perfect information”, was that something you came up with yourself or a concept formalized somewhere where I can learn more?
Thanks Anthony! That means a lot.
Awesome video bro! 😎
Thank you!
Thank you for the visual learning!
Glad you enjoyed it!
Woo that so much clear
Great work! 👏
Thanks Linda!
thanks
I like the explanation! But also, I'm confused a little. Can you explain why you take the average for the inner loop (n/2) but not the (n-1)? Thank you🙏
It doesn’t matter in big O notation. As long as there isn’t a growing multiplicative discrepancy between two algorithms, their complexity is the same.
subscribed
Thank you!
One question, from a non CS graduate, why this solution doesn’t also jump to the next element if bigger or equal to the target sum? Thus reducing the map size and evaluation of previous elements, considering no negative numbers. Second the one pass solution also has a different effect, might not guarantee that you have chosen the bigger index for the value, as you might not have encountered it before finding the solution. Also the two pass might have an issue if you need two identical values for the target, with two different indexes.
1. You can't assume no negative numbers. The question says "integers".
2. I exhaustively explain why the 1-pass is guaranteed to work at 9:58 - 11:30.
3. I directly answer your last question at 6:18.