Trapping Rain Water - Google Interview Question - Leetcode 42

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

[@bruh-moment-21]

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

[@sucraloss]

@@bruh-moment-21 Didn't know about striver's thanks for the recommendation just added to my list

[@shaoyvxn]

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

[@rejul008]

So true

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

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

[@andrewcenteno3462]

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

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

[@Thanos-hp1mw]

I think most hard problems on leetcode are like that

[@sky9k-unlimited]

Make it 100%

[@PabitraPadhy]

Don't be disheartened, the O(N) space solution is not that unintuitive. It's difficult to achieve, that's why it's a hard problem. but atleast you know that you need a boundary, and the water that could be there is the min of those two boundary. Now it's difficult to expand immediately, if the boundary is not immediate next to it. But then problems like this are always PITA. Don't bother too much. Also don't bother too much on the LPA's you need to achieve. This is anyway a nonsensical way of interviewing someone, take it from a staff engg. so just play the ball the best you could. I know some people will get triggerred with my statement, defending the time they wasted doing this instead of solving real-world problems, but then I don't consider them developers.

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

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

[@whimsicalkins5585]

The optimized solution was pretty neat.. But, like @NeetCode says, it is very important to understand why two pointers approach work ? ( Anyway, extra memory method is straight forward). What the O(1) memory solution tries to exploit is, we "only" need info about "bottleneck pillar", to compute possible storage. But, this trick does not function alone. At the initial stage, we decide, from which direction we should traverse using min(L_Max,R_Max). What this essential translates to is that, from either corners, I am going to pick up the lowest valued bottleneck pillar, and I am going to consider that are my starting point. Assume (L_Max < R_Max), so we start from left, traverse from left to right and keep on changing the L_Max value on our way to right. Note that, L_max value maybe several magnitudes less than R_Max. But, when L_max value becomes greater than R_Max, the Bottleneck pillar swaps from left side of reference to right side reference, resulting in traversing the array from right to left now. This change in perspective of what we consider as bottleneck is very very important concept to understand this solution.

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

[@Han-ve8uh]

Don't agree with above that it's still correct with 1 less comparison. I say it's wrong. Imagine a simple example of 1,0,2. Your tighter loop will not count the 1 water in middle. The algorithm in video starts at left and right walls, so the 1st move of any of these will add 0 to water because current height is same as wall height. Only after moving one step can water adding be possible. But if l < r-1, and l = 0, r = 2 with 3 elements, the loop can only run once when r = 0 on the wall which adds nothing. After left move, when r = 1, it fails l < r-1 already.

[@geg_ant]

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

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

[@youpremium175]

Why?

[@bigz8155]

I noticed this as well

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

[@Oliver-nt8pw]

I wish I would udnerstand why can we safely assume that the right max doesnt matter in case we moved left pointer due to l < r.

[@tsunghan_yu]

when max_left < max_right, that means the left part is the bottleneck. It doesn't matter what the true max_right is, simply because max_left is smaller. Just like the barrel theory, how much water the barrel can contain is not decided by the longest but the shortest board.

[@anjanaouseph4605]

Sameee doubt

[@anjanaouseph4605]

​@tsunghan_yu but we can have a case where initial max left is 2 max right is 3 but the actual max right is say 1 somewhere in the middle. Then won't this matter?

[@whimsicalkins5585]

@@anjanaouseph4605 @Oliver-nt89w Let me explain you with two simple examples: ex1: [2,0,1,3] , ex2: [2,0,4,1,3]. At Initial stage L_max =2 and r_max = 3. Now, there are two possibility, there exist right pillar with value lesser than L_max (just like you said, we have 1 inbetween 2 and 3) or there exist right pillar greater than l_max. Lets analyze, case one: after 2, the next two values are lesser than L_max, so L_max does not change (still L_max=2,R_max=3) and we keep traversing from left to right. To answer your question, why we disregard 0 or 1 is that, we see the entire array as one big container (the extreme values are the boundary of the container) and from left most side's perspective, the right boundary is 3 units, which is clearly taller than left side boundary 2. This makes, 2 as the bottleneck value even when we iterate through 0 and 1. As we only need bottle neck value to compute the amount of water that can be stored from the formula, it does not matter if in actuality we have 1 in between 2 and 3. But, you have to understand, that ``it does matter`` , if L_Max value becomes greater than R_max value. In case of ex2, L_Max is no longer bottle neck, when L_max becomes 4. R_max is the new bottleneck value, and we need to change our direction of traversal from left->right to right->left. This happens safely until, we encounter a value that makes R_max greater than L_max. When that happens, we again change the perspective. Hope this helped .( You can also see that, whenever perspective changes, the container size also changes (this is not relevant to problem) and progressively shrinks and eventually becomes 0, effectively helping us to come out of loop. This is not relevant to problem, but is very beautify to imagine)

[@youpremium175]

@@anjanaouseph4605no because water will be trapped between the 2 on left and 3 on right

[@AshishKumar-dk5ve]

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

[@thearturro]

What a great explanation! I actually coded 3/4 of your solution while you were explaining it and I only missed the part of updating the result. Thank you!

[@jacktrainer4387]

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

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

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

[@pun1sher98]

The problem felt like Easy instead of Hard after watching this! This was one of the best explanations that you have presented. I did not even need to see the actual code.

[@avahome5285]

the explanation is so natural. thank you.

[@chefi5357]

Just solved this problem with the O(1) solution and it took me 10 minutes to come up with. All thanks to NeetCode 150. I started Neetcode 150 about 4 days ago and it becomes more and more clear how good the order of this list is. If I didn't solve "Container With Most Water" (the prior problem on the list), coming up with the solution for this problem could easily have taken me 30+ minutes to come up with, if at all. This was my first hard difficulty question, feels so good to have solved it. Thank you so much!

[@sumeetkamat]

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

[@viridianite]

8:42 An alternative way to think about the round up to greater or equal to zero is checking if (min - height[i]) is greater than or equal to zero. If it's, then that means the block of height[i] can hold (min - height[i]) blocks of water above it. Otherwise, it can not and we can simply skip over with the condition.

[@lakewobegonesbest8725]

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

[@ThamaraiselvamT]

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

[@gustavosena7876]

same here :D

[@TheRisingLlama]

Why is it l < r over l

[@Han-ve8uh]

When l == r, both pointers are on the highest wall. There is no water in that position

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

[@CellerCity]

This opened my eyes. I always used to skip hard problems. Now there is HOPE!

[@nikhildinesan5259]

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

[@hbhavsi]

This was a really really good explanation and breakdown. Don't need to memorize anything after this. Thanks a lot!

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

[@shreyaschaudhary-r6d]

just by listening to you explain the solution, I could code it up before you give us the code! Thank you

[@TaiChiSWAG]

The way you start explaining makes the problem pretty easy 👍

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

[@vamsikrishnagannamaneni912]

Dude that trick to move space complexity from O(n) to O(1)

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

[@nguyenbach4710]

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

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

[@shivkrishnajaiswal8394]

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

[@Ruben-ho9jd]

You don't need to check if the heights array is empty because in the constraints it mentions that you will always be given an array of size n where n>= 1.

[@tanmoy003]

One of the best explanation that I have seen!

[@sarvesh6785]

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

[@demaxl732]

This guy seriously just made a hard problem look so easy

[@mingjiesong5042]

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.

[@aravindmeyyappan8368]

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

[@hoangvietng7100]

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

[@wen1799]

Is the implementation different from the approach explained? Seems like the approach(two pointer) computes the height first before updating the height. The implementation on the other hand computes the height first to prevent the negative case (It's such a brilliant idea). Was a little confused while reading the code and wondering where the negative water retained case is handled. On the other hand, this is the best video I have seen so far explaining the solution. Thank you

[@svran1234]

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

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

[@karanvirsagar1998]

why do we are not directly take the difference between both arrays, instead of applying formulae "Min(L,R)-h[i]" for example: right = 3,3,3,4,4,4,4,4 left = 4,4,4,4,3,3,3,2 diff = 1,1,1,0,1,1,1,2 = 8 (answer)

[@allocator7520]

The O(1) solution is easiest understood if you imagine you only see what you have scanned from the pointers and building an image of the scenery progressively, imagine you are the computer and you are scanning the image from both left and right sides you know that the height of left is 1 and the height of right is 0 that means that you are looking at a slope starting from left to right and you cannot tell if there is any water in the next tile so what you do you shift right pointer you detect a height of 1 now the image that you see is sort of a long "lake" with height 1 and as the algorithm progresses you start drawing the image and the altitudes

[@neelanshsharma275]

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

[@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 ?

[@ehm-wg8pd]

would it be just scan x z axis first then increment one y, reiterate?

[@dorbie]

@@ehm-wg8pd brute force is a simple iterative scan but of course you need to check adjacent height from filled squares as you scan, and terminate when you exceed the height at a boundary.

[@idolgin776]

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

[@jackliu6351]

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

[@zetagundam20x]

Very shocked I solved my first leetcord hard and in one go. Even more shocked at the Two Pointer solution. Keep it up bro!

[@royd-l]

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

[@tttrrrrr1841]

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.

[@TarunKumar28]

Nicely explained, simple and elegant solutions.

[@TheAlvaryn]

Time complexity: (O)26 + n + n*logn = (O)n + n*logn Memory complexity: (O)26 = (O)1 constant time Please correct me if I am wrong, thanks very much!! 😁

[@Ayush-lj6pq]

Time complexity is O(n) we are only running one loop

[@Terracraft321]

what is 26

[@TheAlvaryn]

@@Terracraft321 That's for the number of alphabets or buckets for each letter in the english alphabet. (:

[@yashpokar]

It was a very difficult problem to solve until I watched this video. Keep the great work up!

[@aashishbathe]

Actual best, most efficient explanation!!

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

[@ygwg6145]

Another way, which might be a little bit easier is to find the maximum first, then calculate the area under the envelope O(n) time O(1) in space. After that, substracting the area occupied by the bars will give us the total amount of water.

[@rijhwanifamily8172]

can you post your code and explanation

[@PippyPappyPatterson]

I'd also like to see your solution.

[@silkyjain5964]

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

[@AnkitaNallana]

Frankly, the two pointer optimization would never strike me. In an interview, I would jump straight to the 2D array and if they ask me to optimize on top of that, I'll go for 2 pointer. They shouldn't expect an interviewee to jump straight to 2 pointers!!

[@shivrajnag12]

Hi NeetCode I have one doubt while explaining you were computing the res and then computing maxL and maxR with height[l] and height[r] respectively but in code you are finding the maxL or maxR first and then computing the res. If we check maxL or maxR and height[l] and height[r] respectively then we will not get negative res but doing it afterwards yield wrong result. We need to compute maxL and maxR before finding the height of water that can be stored at a particular index. Am I right ?

[@siqiliu3200]

You are right! we should update the leftmax and rightmax before adding the area.

[@evergreen7781]

Excellent explanation !!! But I feel the O(1) Memory solution is not very intuitive and hardly possible to come-up with in a 45 minutes interview if you haven't seen that.

[@shalsteven]

How can you have an idea that we need to find the maximum of the left side and the maximum of the right in each point?

[@goldfishbrainjohn2462]

I'm also wondering. Neetcode is a truly genius.

[@chayan_ghosh]

best explanation for this problem on yt. Thank you

[@youreyesarebleeding1368]

I see that this video is old, but here is my solution with python3 which beat 99.2% in terms of speed, and 92.89% in terms of memory. No stack, no dynamic programming, and unusual two pointer solution that uses two separate loops, but also skips a bunch of elements in the middle this way if there are more than 1 global max in the input array 1. find the max element in the array 2. sum every element in the array and store that as the volume 3. start from the left, and store the max value we've seen so far. Iterate until we hit the max element in the array. If a value is less than the max we've seen so far, set that value to the max 4. do the same from the right, until we hit the max element in the array 5. finally, calculate the volume of the "outline" of all the blocks -- so, sum up all the values to the left of the max element, and to the right of the max element. If the ending position of left/right were different, add (right - left) * max_element_in_array 6. subtract the volume of the outline from the original volume we found in the beginning Here's the code: ``` def trap(self, height: List[int]) -> int: mh = max(height) block_vol = sum(height) left = 0 max_left = 0 while height[left] < mh: if height[left] > max_left: max_left = height[left] height[left] = max_left left += 1 right = len(height)-1 max_right = 0 while height[right] < mh: if height[right] > max_right: max_right = height[right] height[right] = max_right right -= 1 filled_vol = sum(height[0:left]+height[right:]) + (right-left)*mh return filled_vol - block_vol ```

[@kirillkriachenko7705]

Hello, Thank you for your videos, they really helps in understanding how to solve the problem. Can you please make a video of how you coming up with the decision of which algorithm and or data structure to use for the problem? I mean what is the logic between the task being read and the approach is chosen? Like... is there any thoughts that should be applied to determine that between all amount of knowledge (heap, stack, queue, devide&concure, linked-list, etc.) I need to choose 2 pointers.

[@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 🙂

[@Siebener]

This is my first solved hard leetcode problem.

[@pinakadhara7650]

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

[@Ahmad_Al-Deeb]

You Are So Good At Explaining! Thanks!

[@sciencetube1531]

why we need to shift pointers before calculation? why does it matter it's gonna result 0 anyway? test cases not passing if pointer shifted after.

[@deepanshugupta4901]

The Best explanation video on KZbin

[@tttrrrrr1841]

I don't think `if not height: return 0` is *needed* unless `height` could be `None`? (not allowed on the LC version)

[@MinnoqWV]

Thanks, this is a great algorithm. I came up with an alternate solution myself which I was pretty proud of - using a Stack of a little struct to keep track of each 'active' layer of water (including how deep it is, where it began from, and how far offset from the ground it is), then closing them off and updating the total when they encounter a wall, and then any which never hit a wall never get counted. It passed all the cases on Leetcode but was much less elegant than this. However, does anyone know if the Runtime/Memory info on Leetcode is accurate? Because I implemented this algorithm afterwards, and got almost identical results in speed/memory usage, which can't be right

[@DarrenMunoz-s5b]

In your two pointer approach, are you sure it is correct to say that you do not need the true max_right value since we want the min(max_left, max_right)? For example, imagine we are at index one of some height array. On the left (at index 0) is the value 4, so the max_left at index 1 is 4. At the far right (index len(height) - 1) is the value 1. You would have it that the max_right is 1. But let's say at some position in between, but not including, index 1 and index Len(height) - 1 that there is a value 2. This would mean the true max_right is 2. The true min(max_left, max_right) calculation should yield 2. But yours would yield 1. Let's say the height at index 1 is 0. Then your water calculation at index 1 would be 1, when the actual water calculation should be 2. Does the reason that your two pointer approach works have to do with how you move the pointers? Does this somehow avoid this incorrect calculation? I can almost feel intuitively that this is so, but cannot explicitly reason it out at this point. Thanks for your time and great job on your videos!

[@kljajevicluka]

This was confusing to me as well. The truth is, we are taking into consideration both leftMax and rightMax, but it's kinda hidden in plain sight. Inside the if statement, we not only check which pointer to move, but we also get the confirmation which of the two maxes (leftMax or rightMax) is the bottleneck. That's why we can certainly know that the leftMax will always be the bottleneck when moving the left pointer. The same also goes for the right pointer while l < r: if leftMax < rightMax: # this does 2 things: 1. decides which pointer to move, 2. tells us that leftMax < rightMax, so we know that leftMax is the bottleneck l += 1 # we can move the pointer first because we know that water cannot be stored at the end leftMax = max(leftMax, height[l]) # we first calculate the left max to make sure that leftMax - height[l] is not < 0 res += leftMax - height[l] else: r -= 1 rightMax = max(rightMax, height[r]) res += rightMax - height[r]

[@anjanaouseph4605]

Same doubt 🙋‍♀️

[@Sachin-x4m7c]

I was able to solve this by myself, we need to find the reverse peak, then min - all the el in the peak and if at the end we dont have reverse peak, reverse the array from that point and repeat

[@sabihabarlaskar8318]

Such a detailed explanation! Thank you!

[@raviyadav2552]

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

[@jobprep8136]

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

[@nagendrabommireddi8437]

in video you explained to shift left pointer when leftmax=rightmax but in code showed it reversly

[@arkamukherjee457]

Damn, the solution makes it look like the question is an LC easy

[@runeyman]

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

[@hishampaloli8227]

Easy readable solution var trap = function(height) { let collected = 0 let [l,r,lMax, rMax] = [0, height.length, 0, 0] while(l < r){ (height[l] < lMax) ? collected+=lMax-height[l] : lMax=height[l]; (height[r] < rMax) ? collected+=rMax-height[r] : rMax=height[r]; (height[l]

[@cccccbgkv]

Really beautifully explained! Thanks for these videos!

[@OwenWu-f9t]

I thought you said we subtract the minimum of max left and max right by the current number in the array, so at 18:45, wouldn't that not be 2 since max left is 2 and max right is 0?

[@matheusmenezes4702]

Great solution! Thank you, brother!

[@Haseebkhan-yd9ud]

after your explaination iactually coded it myseld love you bro

[@sunilkumarsamji8871]

One Word - Amazing....

[@cakecup-r6g]

i didnt get one thing , 11:35 , shouldnt't the max right be initially zero because on the right hand side there is nothing meaning the water cant be contained

[@David-hs3fu]

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

[@karann6010]

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

[@goldfishbrainjohn2462]

You're so intelligent ! How could you come up with so many incredible solutions? How long did it take your time to come up those solutions? So Smart !

[@avadhpatel111]

Great explanation. Thank you very much for this video.