Trapping Rain Water - Google Interview Question - Leetcode 42

🚀 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

[@NeetCode]

🚀 neetcode.io/ - A better way to prepare for Coding Interviews

[@nishantingle1438]

Why not create something like 350-450 also ? I think that is the minimum number of standard questions required to crack FAANG.

[@fatorangecat21]

@@nishantingle1438 do neetcode 150 and striver sde sheet along with some spicy extra questions you can find while browsing leetcode.

[@sucraloss]

@@fatorangecat21 Didn't know about striver's thanks for the recommendation just added to my list

[@lzosx]

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

[@DarnMyNameDoesntFi]

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?

[@goodgoodduckqi2139]

yes lmfao

[@againnotgood8980]

thanks, apart from grasping leetcode 42, I also learned 3 more words: vocal register, crux, escalate

[@MeridithLee]

​@@againnotgood8980 lmao thank you for this, it made me laugh out loud in the middle of a leetcode grind

[@knowledgedose1956]

@@MeridithLee apparently I am not the only one who reads comments during leetcode video

[@theastuteangler]

@@againnotgood8980 crux is overrused, let this word die already

[@prafulparashar9849]

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 !!

[@symbol767]

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

[@thecap7249]

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.

[@VV-ps8rt]

Lol same

[@fatcat22able]

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!

[@vamshisagargadde1629]

thanks, looking for this

[@nw3052]

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.

[@cagatay2462]

@@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.

[@nw3052]

@@cagatay2462 oh yeah, you're right. I got a bit of a tunnel vision in here.

[@jasonahn8658]

such a genius way to calculate it

[@ThamaraiselvamT]

you nailed it, I just solved my first ever hard problem at leetcode :D

[@AshishKumar-dk5ve]

Your way of explaining the problem and solution is simply AWESOME. Kudos to you !!!

[@MP-ny3ep]

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!

[@karthik829]

Clear explanation !! I'm truly amazed how people can come up with this algorithm during and interview.

[@andrewgordon4774]

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

[@prasad9012]

@@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.

[@ShikaIE]

@@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.

[@theastuteangler]

this algorithm is easy

[@geg_ant]

That is impressive how simple actual solution might be! Thank you!

[@avahome5285]

the explanation is so natural. thank you.

[@theornament]

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.

[@nikhildinesan5259]

Good to see you back after a long time !!!

[@jacktrainer4387]

Brilliant explanation. My loathing of this problem ran deep, until now.

[@sabihabarlaskar8318]

Such a detailed explanation! Thank you!

[@silkyjain5964]

You explained this so well. It was hard for me to understand this problem otherwise. Thank you!!

[@andrewcenteno3462]

The two pointer solution is insane, I would never come up with that 'on the spot' at an interview.

[@idolgin776]

Thanks for a great explanation! I am starting to play with algorithms, and this has been a big help.

[@sarvesh6785]

Your video is fantastic. Each video guarantees a precise and clear explanation.

[@TarunKumar28]

Nicely explained, simple and elegant solutions.

[@TheFatAssCat]

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.

[@TaiChiSWAG]

The way you start explaining makes the problem pretty easy 👍

[@swagatzeher]

So nicely explained ! Great job man

[@karann6010]

U make it look so easy ❤️ thanks a lot ☺️

[@jobprep8136]

You are amazing mate !!!! I cant thankyou enough. Crisp, easy and efficient solutions.

[@tanmoy003]

One of the best explanation that I have seen!

[@christendombaffler]

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.

[@jesuscruz8008]

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

[@mortal_coder4869]

this was amazing, proud of your videos NC, keep up the good work.

[@praneshs8344]

Thanks mate !! I really like your explanation, very understandable

[@linli7049]

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 )

[@twin392]

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.

[@anantprakashsingh8777]

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.

[@runeyman]

Your explanation is so good that I'm able to implement the solution without seeing the code! 😁

[@aashishbathe]

Actual best, most efficient explanation!!

[@tiennguyenthuy7563]

Very helpful. thank you. Keep up the inspiring work

[@aiyifei4732]

Very neat solution! Thanks for the explanation.

[@pinakadhara7650]

This is one crazy problem. Thanks for this great video!

[@David-hs3fu]

Thanks!! This is the best presentation I've ever seen.

[@nguyenbach4710]

the way u make prolems easier drive m crazy thanks a lot plz don't stop

[@crosswalker45]

amazing explantion..what an amazing brainstorming session

[@svran1234]

This was so easy to understand and very neatly explained. Thank you so much!

[@ralucaioan7609]

Thanks a lot, I love to learn from your videos!

[@kirillzlobin7135]

Thank you very much for such a great quakity of the material. You are doing an amazing job

[@yazeed8240]

Really beautifully explained! Thanks for these videos!

[@chayan_ghosh]

best explanation for this problem on yt. Thank you

[@daniyalkabir6527]

Made it look so easy! Thanks for this.

[@francaniilista]

Thanks a ton, pal! Very clear explanation, I've tried to solve it, but I did not figure out alone before watching your video.

[@daeyangcho9098]

Really nice and cool explanation! Thanks very much!!!

[@NeetCode]

Glad it helped!

[@jackliu6351]

Your explaination of concept is so easy to understand!!!!!! keep making videos!!!!!

[@vipulgoyal2370]

Awesome, Thanks for the intuition.

[@fredtrentini6791]

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.

[@varanasiaditya]

This is just simply brilliant!

[@hoyinli7462]

your explanation is the best!

[@hassankazmi5443]

you make it so simple, great job

[@yuchenzhang1741]

This is really helpful! Thanks!

[@sankeerthsirikonda3565]

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)

[@alexdeathway]

Since there is LeftMax and RightMax, it would cause an IndexError.

[@sumeetkamat]

What an amazing explanation! It is supposed to be a HARD problem and you made it look so easy!

[@avadhpatel111]

Great explanation. Thank you very much for this video.

[@matheusmenezes4702]

Great solution! Thank you, brother!

[@hoangvietng7100]

I have no words to say about how good your help is

[@linli7049]

Great explanation as always!

[@TheRisingLlama]

Why is it l < r over l

[@anujapuranik2000]

Thankyou again for this video.. you make all the videos so easy and your explanation skills are amazing!!! Thanks much:)

[@80kg]

Thank you explained so clear!!

[@kipa_chu]

Thanks, excellent explanation.

[@nanh2015]

very clever solution, thank you

[@aduhaneh1057]

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

[@ivantishchenko4686]

Superb explanation!

[@user-vt2hi6hw9j]

I really love your videos, please keep going on~

[@royd-l]

Great solution explained simply! Now the real question is how to be this clever in the actual interview

[@raviyadav2552]

this is super intuitive and easy thank you for the solution keep it up sir

[@Haseebkhan-yd9ud]

after your explaination iactually coded it myseld love you bro

[@deepanshugupta4901]

The Best explanation video on KZbin

[@AbhinavKumar-ri8zi]

watched atleast 10 videos on the same problem , yours explanation was the best and simplest . Thank you

[@abhinavkumarr]

i double this

[@AbhinavKumar-ri8zi]

@@abhinavkumarr damn another me !

[@lakewobegonesbest8725]

‘…and it’s actually pretty simple…’ Excuse me while I throw my laptop across the room.

[@dorbie]

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).

[@bostonlights2749]

was it samsung ?

[@hoyinli7462]

you are fxxking genius in explaining concepts!! you got 1 new subscriber!

[@mariamozgunova9584]

It helped me realize the solution after 2 min of watching! Thank you!

[@NeetCode]

I think you prob deserve more credit for that then me 🙂

[@1mang0]

thank u so much sir....ur videos are really helpful😄😄

[@prempeacefulchannel]

Amazing explanation 👌

[@Xeoncross]

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]"

[@HarshGupta-sl8ly]

Very well explained !!!

[@samarthtandale9121]

Great Explaination !!!

[@shivkrishnajaiswal8394]

Underrated channel in Leetcode solution. Highly recommending this channel for Algo preparation

[@weibinsun5771]

Excellent! super helpful

[@abhineykumar1773]

u are osm man, this kind of explanation wins my heart

[@zourou228]

Great explanation!

[@neelanshsharma275]

Did a few changes and was able to get 0ms runtime in Java :) Thanks NeetCode ❤

[@user-ko7en6en1j]

beautiful explanation. thanks

[@eidiazcas]

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

[@danielfirebanksquevedo891]

Beautifully explained, thank you!

[@KANISHKSAHUSIME]

Thanks man very helpful

[@user-cb1si7ig6p]

I don't even code in Python but I love your explanations, hence a subscriber.

[@yamaan93]

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.

[@abhishekrbhat8919]

Beautiful explanation

[@symbol767]

Bro you are a king. Thank you.

[@FitnessChaos]

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

[@brandonnoll5527]

Agreed. I'm just not so good at this stuff lmao.

[@MrTacoMan123]

right?? theres no way I could come up with this solution in < 25mins during interview if I havent seen this problem before

[@akashkewar]

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.

[@shubhamjaiswal1325]

i am too dumb to come up with an optimal approach, unless I have sen such trick before

[@sumitbanwakade9750]

Super Explaintion !!

[@jingkaixie7898]

Thank you!