Trapping Rain Water - Google Interview Question - Leetcode 42
Vložit
- čas přidán 8. 07. 2024
- 🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🐦 Twitter: / neetcode1
🥷 Discord: / discord
🐮 Support the channel: / neetcode
Coding Solutions: • Coding Interview Solut...
Dynamic Programming Playlist: • House Robber - Leetco...
Tree Playlist: • Invert Binary Tree - D...
Linked List Playlist: • Reverse Linked List - ...
Problem Link: neetcode.io/problems/trapping...
0:00 - Read the problem
5:40 - O(n) Memory Solution
11:00 - O(1) Memory Solution
20:05 - Coding Explanation
leetcode 42
This question was identified as an interview question from here: github.com/xizhengszhang/Leet...
#pointer #array #python - Věda a technologie
🚀 neetcode.io/ - A better way to prepare for Coding Interviews
Why not create something like 350-450 also ? I think that is the minimum number of standard questions required to crack FAANG.
@@nishantingle1438 do neetcode 150 and striver sde sheet along with some spicy extra questions you can find while browsing leetcode.
@@fatorangecat21 Didn't know about striver's thanks for the recommendation just added to my list
honestly, it's not even the solution that make your videos so valuable; it's the fact that i get to take a look at your thought process which infinitely more assists in the structure of solving a problem
My favorite part about all of your videos is that you start out in a pretty chill vocal register and the moment you get to the crux of the problem you escalate and get super intense. I've been watching and trying to note when that always happens... it's pretty much the moment you start drawing out the problem. Anyone else notice this?
yes lmfao
thanks, apart from grasping leetcode 42, I also learned 3 more words: vocal register, crux, escalate
@@againnotgood8980 lmao thank you for this, it made me laugh out loud in the middle of a leetcode grind
@@MeridithLee apparently I am not the only one who reads comments during leetcode video
@@againnotgood8980 crux is overrused, let this word die already
This explanation is so spot on that i actually coded everything myself before even looking into the code part of the video.
You are doing great work !!
Congrats on the new job and thanks a lot !!
For anyone confused about the res += leftMax - height[l] line like I was, look at the line above it.
> leftMax = max(leftMax, height[l])
If leftMax is less than (or equal to) height[l], we set leftMax equal to height[l] and then subtract height[l] from it, which would equal zero.
On the other hand, if leftMax is greater than height[l], we keep leftMax as is and subtract height[l] from it, which would be a positive value.
In either case, the result will always be greater than or equal to zero, which means you don't have to check for negatives.
Hope this helps!
thanks, looking for this
And if leftMax becomes greater than rightMax? That means we would add more water than the two pillars could hold since the minimum is the bottleneck. Honestly didn't quite get how his code worked.
@@nw3052 if leftMax is greater, we start adding water from only right side. In other words, if leftMax is greater, we run else statement till while loop ends.
@@cagatay2462 oh yeah, you're right. I got a bit of a tunnel vision in here.
such a genius way to calculate it
I've come back to this problem so many times, I feel this is a horrid interview question, its beyond unintuitive.
I guarantee 99% of the entry level dev's at least would not be able to figure out the solution to this problem if they've never seen the solution before. Even if they did 400 other leetcode problems
It's kind of relaxing for me after reading this comment, I knew what needs to be done but was unable to put it in code.
Lol same
This was a phenomenal explanation! You made it soooo easy. Thank you so much. You channel is gold. And , congrats for getting placed! I wish you all the success in the world!
Your way of explaining the problem and solution is simply AWESOME. Kudos to you !!!
Clear explanation !! I'm truly amazed how people can come up with this algorithm during and interview.
I’d say 95% of people don’t, you either get lucky and don’t get this question or have seen it before and know the technique
@@andrewgordon4774 Agreed. We just have to practice as many problems as we can to increase the probability of getting asked something we've already seen before.
@@prasad9012 agree. I think given the problem in day2day work, people might be able to work it out without the time limit and stress. It’s a bit ridiculous to think of it being the norm in the technical interview. But the good thing about it is that people who did this are at least aware and care about important of algorithms. Interviewers might consider those who came out with o(n) memory at least rather than the brute force.
this algorithm is easy
That is impressive how simple actual solution might be! Thank you!
I was able to solve this by calculating the index of the greatest value and creating two loops where each one is designated for left and right pointers, and loop them until we reach the index where we found the greatest element. I basically calculated that we need to find the next greatest element in each loop (remembering that the next greatest value is current greatest value + 1) where, until it gets to that point, increase/decrease our pointers and sum the actual greatest value - the current value. The only difference for the right pointer loop is that we need to calculate if we already reached a point where we got to the greatest value (as it can be repeated).
It's a bit more inefficient than this solution, but it's still O(n) so I'm proud of coming up with it myself.
you nailed it, I just solved my first ever hard problem at leetcode :D
Good to see you back after a long time !!!
the explanation is so natural. thank you.
Brilliant explanation. My loathing of this problem ran deep, until now.
You explained this so well. It was hard for me to understand this problem otherwise.
Thank you!!
Such a detailed explanation! Thank you!
Your video is fantastic. Each video guarantees a precise and clear explanation.
The way you start explaining makes the problem pretty easy 👍
Thanks for a great explanation! I am starting to play with algorithms, and this has been a big help.
Nicely explained, simple and elegant solutions.
Goodness, this problem was hell for me to visualise. I gave up on it when doing it on my own after a couple of hours because I couldn't come up with anything and I couldn't understand any of the solutions and their explanations. In particular I really didn't understand how you didn't need O(n) to figure out the required filling in a given space even if we ignored one side or the other. I had to go through your position-by-position explanation twice and I needed to make an array for all 5 calculations just to understand how to process the idea correctly, but at least it's how I got my breakthrough, and figuring out the two pointer solution after that was trivial.
Thank you for the video. Looking up what people thought were the hardest problems on leetcode and seeing this very problem get the most mentions made me feel a lot better about myself.
So nicely explained ! Great job man
The two pointer solution is insane, I would never come up with that 'on the spot' at an interview.
U make it look so easy ❤️ thanks a lot ☺️
Man some of these solutions seem so obvious after you see them.
I brute forced this problem and while it took a while and worked, it was stupidly inefficient. And thus didn't pass Leetcode.
Thank you for the excellent breakdown.
this was amazing, proud of your videos NC, keep up the good work.
I think we should use "while ( l < r - 1 )" instead of "while( l < r )" because we don't want to compute the water in the same position twice. So if l and r are adjacent, we should stop shifting l or r pointer. However, while ( l < r ) still works in leetcode. I am not sure if it is guaranteed to be correct if we use while ( l < r )
When L and R overlap, the leftMax and rightMax are going to be the true max, so doing rightMax or leftMax - height[l or r] always produces 0 and doesn't add to res. It's unnecessary but doesn't change the answer.
Well, when Left and Right pointer end up at the same position, they have also arrived at the highest value in the array. This would mean that no water can be trapped at that location, hence the answer would be correct regardless. Introducing your condition to the algorithm would result in one less comparison, that would result in a faster algorithm, but not by a significant margin. You can introduce your condition into the algorithm, the answer would still be correct.
You are amazing mate !!!! I cant thankyou enough. Crisp, easy and efficient solutions.
One of the best explanation that I have seen!
Why is it l < r over l
great explanation like always! i wrote a long function to get this to work but your way was way better than mine glad i always watch your videos after im done to see a better way of doing the question
Instead of updating the maxLeft after you compare it, you can update it first so the subtraction will always be greater than or equal to 0. So you can always append the answer of "sum += leftMax - height[L]"
Your explanation is so good that I'm able to implement the solution without seeing the code! 😁
Very helpful. thank you. Keep up the inspiring work
Thanks mate !! I really like your explanation, very understandable
Actual best, most efficient explanation!!
Spent a bit more than 2 hours doing this one and some O(N ** 2) solution I came with ended up getting accepted. The whole time I was so worried about knowing where each of those gaps of water started and ended, until I looked for the best solution and noticed there was no need to know that, all I had to know was the maximum amount water that could be trapped in the current position. Great explanation.
i am too dumb to come up with an optimal approach, unless I have sen such trick before
Thanks a lot, I love to learn from your videos!
This was so easy to understand and very neatly explained. Thank you so much!
Very neat solution! Thanks for the explanation.
Thanks!! This is the best presentation I've ever seen.
best explanation for this problem on yt. Thank you
This is one crazy problem. Thanks for this great video!
the way u make prolems easier drive m crazy thanks a lot plz don't stop
Really beautifully explained! Thanks for these videos!
Thank you very much for such a great quakity of the material. You are doing an amazing job
Made it look so easy! Thanks for this.
Awesome explanation, BTW i think there is no need for if condition at the starting instead of returning 0, we will return res as 0 if there are no elements(while loop will not be executed)
Since there is LeftMax and RightMax, it would cause an IndexError.
This is really helpful! Thanks!
Awesome, Thanks for the intuition.
i tried doing this question before going through the vid but couldn't figure it out. u r super smart man, thx for the thorough explanation
Your explaination of concept is so easy to understand!!!!!! keep making videos!!!!!
This is just simply brilliant!
you make it so simple, great job
Thanks a ton, pal! Very clear explanation, I've tried to solve it, but I did not figure out alone before watching your video.
Seems simple when you explain it but how do you come up with a solution when its all on the line? thats the frustrating part
Agreed. I'm just not so good at this stuff lmao.
right?? theres no way I could come up with this solution in < 25mins during interview if I havent seen this problem before
well, this is what it is all about. You solve problems that give you intuition and the same intuition can be used to solve multiple problems. The solution provided in the video is not the only solution, you can approach this problem in multiple ways from brute force to linear time and this is what would come to you automatically by solving problems.
Great solution! Thank you, brother!
amazing explantion..what an amazing brainstorming session
I was once asked to code this but in 2D (really 3D considering it's a height field). It's an interesting challenge adding that extra dimension. I forget which company asked this (wasn't Google).
was it samsung ?
Great solution explained simply! Now the real question is how to be this clever in the actual interview
Great explanation as always!
I really love your videos, please keep going on~
your explanation is the best!
Thank you explained so clear!!
after your explaination iactually coded it myseld love you bro
I have no words to say about how good your help is
Great explanation. Thank you very much for this video.
Thankyou again for this video.. you make all the videos so easy and your explanation skills are amazing!!! Thanks much:)
Underrated channel in Leetcode solution. Highly recommending this channel for Algo preparation
Thanks, excellent explanation.
this is super intuitive and easy thank you for the solution keep it up sir
very clever solution, thank you
Very well explained !!!
Beautifully explained, thank you!
The Best explanation video on CZcams
you are fxxking genius in explaining concepts!! you got 1 new subscriber!
This guy seriously just made a hard problem look so easy
Really nice and cool explanation! Thanks very much!!!
Glad it helped!
Great Explaination !!!
I know it doesn't end up mattering but a piece of feedback I thought I'd give on the video, the order in which you explain in the drawing is:
1. Move the pointer
2. Calculate Volume
3. Update the leftMax
but in the actual code, you:
1. Move the pointer
2. update the max
3. Calculate the volume
I understand that this doesn't end up mattering in the end, however it can make it really confusing if you can't figure out why that's fine.
Excellent! super helpful
Superb explanation!
I solved this using a stack for the heights on the left and calculating new volume while iterating the array, also O(N) solution, but I'd have never thought of the solutions you proposed here, very clever
Bro you are a king. Thank you.
Thanks man very helpful
Great explanation!
I don't even code in Python but I love your explanations, hence a subscriber.
This is the first hard problem I have ever solved! Although I only got the O(n)/O(n) solution (I used linear extra space for the "left" side), not O(1) space. I knew it must be possible with two pointers since I did Container With Most Water, I just couldn't quite get the logic correct.
Super Explaintion !!
Did a few changes and was able to get 0ms runtime in Java :)
Thanks NeetCode ❤
u are osm man, this kind of explanation wins my heart
beautiful explanation. thanks
Thanks man!
Bro you are a life saver.
well explained, thanks :)
Amazing explanation 👌
Beautiful explanation
Great explanation! One bug in the code: the l increment and r decrement should be after finishing recalculating the leftMax and rightMax instead of before.
No, at the start both maximumLeft and height[l] are same. So as the name maximumLeft suggests, it should hav value left of height[l].