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?
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!
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.
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
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.
Your O(1) two-pointer solution is so much better than the two-pointer solution provided by Leetcode editorial, which I still don't understand after more than an hour. I understand yours right away! They don't compare the current max_left and max_right. Rather they compare the height at the current left index and right index (whether height[left] < height[right]). I cannot figure out the logic there (only understand it in a fuzzy unexplainable way...)
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.
@@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.
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.
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!
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.
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.
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.
I changed the while loop process on the pointer that is similar to what he has explained with the drawing so its more intuitive: while l < r: if maxL < maxR: if maxL - height[l] > 0: res += maxL - height[l] l += 1 maxL = max(maxL, height[l]) else: if maxR - height[r] > 0: res += maxR - height[r] r -= 1 maxR = max(maxR, height[r])
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
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.
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.
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.
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.
@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?
@@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)
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.
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)
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
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!
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.
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!
HELP PLEASE | 18:30 | maxL - height[i] = 2 - 3 = -1 | Since we cannot store a negative amount of water, we say it is 0. Hence I assumed in the code I would see something like current = maxL - height[i]; if current < 0: current = 0; res += current. However, in the actual code this moment is disregarded, but how does it work?
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?
I was failing to understand how 2 pointers approach is able to solve it even though the array is not sorted. The key part lies in the decision making where if on the right there exists a value greater than on the left, no matter what other elements are on the right, the decision for that position will be determined by the left (which is correct and determined one). I asked chatgpt, searched google, went through lots of youtube videos and couldn't convince myself. You precisely explained that point on how right doesn't matter to us and our solution get be obtained from left OR vice versa .. cheers !
It's really (intuitively) confusing to me after 21:47 that we update the max height AFTER we move the pointer, so we count ourselves!! If the height we're currently calculating *is the max* , we're saying that *the max to the left of it, is itself!*
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
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 ?
there is a mistake in 12:03 because you need to update the actual maxL according to the code in the line of: maxL = max(maxL, height). Update of maxL is first executed then proceed with res, so the calculation of height in 14:03 is 1-1 = 0, because the maxL is updated to 1 not 0 as you put; however that doesn't change the good implementation of the algorithm :)
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.
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
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)
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).
@@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.
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
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.
🚀 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.
@@bruh-moment-21 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
So true
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 !!
The two pointer solution is insane, I would never come up with that 'on the spot' at an interview.
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
I think most hard problems on leetcode are like that
Make it 100%
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.
Your O(1) two-pointer solution is so much better than the two-pointer solution provided by Leetcode editorial, which I still don't understand after more than an hour. I understand yours right away!
They don't compare the current max_left and max_right. Rather they compare the height at the current left index and right index (whether height[left] < height[right]). I cannot figure out the logic there (only understand it in a fuzzy unexplainable way...)
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.
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
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.
That is impressive how simple actual solution might be! Thank you!
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!
‘…and it’s actually pretty simple…’ Excuse me while I throw my laptop across the room.
Your way of explaining the problem and solution is simply AWESOME. Kudos to you !!!
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.
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.
Brilliant explanation. My loathing of this problem ran deep, until now.
you nailed it, I just solved my first ever hard problem at leetcode :D
same here :D
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.
Good to see you back after a long time !!!
I changed the while loop process on the pointer that is similar to what he has explained with the drawing so its more intuitive:
while l < r:
if maxL < maxR:
if maxL - height[l] > 0:
res += maxL - height[l]
l += 1
maxL = max(maxL, height[l])
else:
if maxR - height[r] > 0:
res += maxR - height[r]
r -= 1
maxR = max(maxR, height[r])
the explanation is so natural. thank you.
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
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.
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.
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.
Why?
I noticed this as well
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.
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.
Sameee doubt
@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?
@@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)
@@anjanaouseph4605no because water will be trapped between the 2 on left and 3 on right
Mega Thanks! You are the best
Thank you so much Steven!!
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.
What an amazing explanation! It is supposed to be a HARD problem and you made it look so easy!
You explained this so well. It was hard for me to understand this problem otherwise.
Thank you!!
This was a really really good explanation and breakdown. Don't need to memorize anything after this. Thanks a lot!
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.
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
Your video is fantastic. Each video guarantees a precise and clear explanation.
Thanks for a great explanation! I am starting to play with algorithms, and this has been a big help.
One of the best explanation that I have seen!
The way you start explaining makes the problem pretty easy 👍
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!
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.
Underrated channel in Leetcode solution. Highly recommending this channel for Algo preparation
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!
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
Thanks a ton, pal! Very clear explanation, I've tried to solve it, but I did not figure out alone before watching your video.
the way u make prolems easier drive m crazy thanks a lot plz don't stop
This opened my eyes. I always used to skip hard problems. Now there is HOPE!
It was a very difficult problem to solve until I watched this video. Keep the great work up!
HELP PLEASE | 18:30 | maxL - height[i] = 2 - 3 = -1 | Since we cannot store a negative amount of water, we say it is 0. Hence I assumed in the code I would see something like current = maxL - height[i]; if current < 0: current = 0; res += current. However, in the actual code this moment is disregarded, but how does it work?
Your explanation is so good that I'm able to implement the solution without seeing the code! 😁
I have no words to say about how good your help is
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?
best explanation for this problem on yt. Thank you
just by listening to you explain the solution, I could code it up before you give us the code! Thank you
Nicely explained, simple and elegant solutions.
This was so easy to understand and very neatly explained. Thank you so much!
This guy seriously just made a hard problem look so easy
You are amazing mate !!!! I cant thankyou enough. Crisp, easy and efficient solutions.
Very shocked I solved my first leetcord hard and in one go. Even more shocked at the Two Pointer solution. Keep it up bro!
Actual best, most efficient explanation!!
Great solution explained simply! Now the real question is how to be this clever in the actual interview
I was failing to understand how 2 pointers approach is able to solve it even though the array is not sorted. The key part lies in the decision making where if on the right there exists a value greater than on the left, no matter what other elements are on the right, the decision for that position will be determined by the left (which is correct and determined one).
I asked chatgpt, searched google, went through lots of youtube videos and couldn't convince myself. You precisely explained that point on how right doesn't matter to us and our solution get be obtained from left OR vice versa .. cheers !
Your explaination of concept is so easy to understand!!!!!! keep making videos!!!!!
Why is it l < r over l
When l == r, both pointers are on the highest wall. There is no water in that position
It's really (intuitively) confusing to me after 21:47 that we update the max height AFTER we move the pointer, so we count ourselves!! If the height we're currently calculating *is the max* , we're saying that *the max to the left of it, is itself!*
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
The Best explanation video on UA-cam
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 ?
You are right! we should update the leftmax and rightmax before adding the area.
Such a detailed explanation! Thank you!
This is one crazy problem. Thanks for this great video!
there is a mistake in 12:03 because you need to update the actual maxL according to the code in the line of: maxL = max(maxL, height). Update of maxL is first executed then proceed with res, so the calculation of height in 14:03 is 1-1 = 0, because the maxL is updated to 1 not 0 as you put; however that doesn't change the good implementation of the algorithm :)
I don't think so, we keep track of the max LEFT of a position, so we use the old one to calculate first, after that we change as you said
It helped me realize the solution after 2 min of watching! Thank you!
I think you prob deserve more credit for that then me 🙂
watched atleast 10 videos on the same problem , yours explanation was the best and simplest . Thank you
i double this
@@abhinavkumarr damn another me !
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?
I'm also wondering. Neetcode is a truly genius.
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.
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
Did a few changes and was able to get 0ms runtime in Java :)
Thanks NeetCode ❤
You Are So Good At Explaining! Thanks!
this was amazing, proud of your videos NC, keep up the good work.
Dude that trick to move space complexity from O(n) to O(1)
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)
Thanks!! This is the best presentation I've ever seen.
U make it look so easy ❤️ thanks a lot ☺️
So nicely explained ! Great job man
Very helpful. thank you. Keep up the inspiring work
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 ?
would it be just scan x z axis first then increment one y, reiterate?
@@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.
Damn, the solution makes it look like the question is an LC easy
Thank you very much for such a great quakity of the material. You are doing an amazing job
Really beautifully explained! Thanks for these videos!
this is super intuitive and easy thank you for the solution keep it up sir
after your explaination iactually coded it myseld love you bro
I don't even code in Python but I love your explanations, hence a subscriber.
Great solution! Thank you, brother!
This is my first solved hard leetcode problem.
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]
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.
Thanks for the great explanation. Really helpful
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
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].
you make it so simple, great job
amazing explantion..what an amazing brainstorming session