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?
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.
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 !!
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.
@@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.
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.
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.
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.
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.
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!
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)
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.
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)
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.
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.
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!
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.
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!
You take min of maxes, if you have 1 as maxL and 2 as maxR instead of 5, min(1,2)=min(1,5)=1 And you always shift the min pointer, so there won’t be maxL>1 in this case
@@rostyslavmochulskyi159i didn't understand by how can you ignore the max right. What if there exists a smaller value somewhere say 0 instead of 2 or 5 in the middle?
@@anjanaouseph4605 It's kinda confusing but it makes total sense once you think it through. Remember, first of all, we only care about the max value. There *obviously* can't be a "max-value" on the right that is smaller than current right. Otherwise, it wouldn't be the max-value. So, the real max-right must be >= current right.
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 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.
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!!
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 ```
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!! 😁
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.
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
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.
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
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
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
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)
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 ?
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.
So are people actually able to recognize by intuition that the smaller max between the two pointers is always the bottleneck regardless of what's in the rest of the array? I feel like you'd have to be a genius to logically prove that on the spot, unless you've seen the problem before.
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.
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 :)
My suboptimal o(n) memory solution using the explanation if anyone interested class Solution: def trap(self, height: List[int]) -> int: maxleft = [0] * len(height) maxright = [0] * len(height) res = 0 maxleft[0] = height[0] for i in range(1, len(height)): maxleft[i] = max(height[i], maxleft[i-1]) maxright[-1] = height[-1] for i in range(len(height) - 2, -1, -1): maxright[i] = max(height[i], maxright[i+1]) for i in range(len(height)): water = min(maxleft[i], maxright[i]) res += water - height[i] return res
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]"
Hi NeetCode, thanks for your awesome explanation! I just have a question about the tools you've been using for creating these kinds of content. Do you mind sharing about it?
I don't know why I feel like line 14 should have been before line 13 according to his explanation, his solution still works. Because in that case we could be updating leftMax with height[l] without knowing if righMax is greater than height[l] or not. I am confused. Update (I think I got it): According to the way I am suggesting, we will have to check for negative values which his solution cleverly eliminates.
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!
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]
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.
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
I don't know if I'm being dumb, but I feel like the code is slightly different from the explanation. I thought the code below might align more with the explanation, and easier to understand for my monkey brain 😂 if not height: return 0 left, right = 0, len(height) - 1 left_max, right_max = height[left], height[right] res = 0 while left < right: if left_max < right_max: left += 1 amount = left_max - height[left] if amount > 0: res += amount left_max = max(left_max, height[left]) else: right -= 1 amount = right_max - height[right] if amount > 0: res += amount right_max = max(right_max, height[right]) return res
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!*
🚀 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
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
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.
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.
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
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.
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.
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.
That is impressive how simple actual solution might be! Thank you!
Your way of explaining the problem and solution is simply AWESOME. Kudos to you !!!
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
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 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
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
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.
‘…and it’s actually pretty simple…’ Excuse me while I throw my laptop across the room.
What an amazing explanation! It is supposed to be a HARD problem and you made it look so easy!
the explanation is so natural. thank you.
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.
Good to see you back after a long time !!!
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.
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.
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.
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!
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.
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!
The way you start explaining makes the problem pretty easy 👍
This guy seriously just made a hard problem look so easy
This was a really really good explanation and breakdown. Don't need to memorize anything after this. Thanks a lot!
There's no explanation for this: "We don't need to calculate right max for this instance", and then generalizing, i.e. we don't need it ever.
You take min of maxes, if you have 1 as maxL and 2 as maxR instead of 5, min(1,2)=min(1,5)=1
And you always shift the min pointer, so there won’t be maxL>1 in this case
@@rostyslavmochulskyi159i didn't understand by how can you ignore the max right. What if there exists a smaller value somewhere say 0 instead of 2 or 5 in the middle?
@@anjanaouseph4605 It's kinda confusing but it makes total sense once you think it through.
Remember, first of all, we only care about the max value.
There *obviously* can't be a "max-value" on the right that is smaller than current right. Otherwise, it wouldn't be the max-value. So, the real max-right must be >= current right.
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.
Your video is fantastic. Each video guarantees a precise and clear explanation.
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.
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
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!!
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
```
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]
You explained this so well. It was hard for me to understand this problem otherwise.
Thank you!!
Very shocked I solved my first leetcord hard and in one go. Even more shocked at the Two Pointer solution. Keep it up bro!
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!! 😁
Time complexity is O(n)
we are only running one loop
what is 26
@@Terracraft321 That's for the number of alphabets or buckets for each letter in the english alphabet. (:
This opened my eyes. I always used to skip hard problems. Now there is HOPE!
just by listening to you explain the solution, I could code it up before you give us the code! Thank you
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].
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
Great solution explained simply! Now the real question is how to be this clever in the actual interview
One of the best explanation that I have seen!
Why is it l < r over l
When l == r, both pointers are on the highest wall. There is no water in that position
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.
can you post your code and explanation
I'd also like to see your solution.
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
Your explanation is so good that I'm able to implement the solution without seeing the code! 😁
Dude that trick to move space complexity from O(n) to O(1)
I have no words to say about how good your help is
Damn, the solution makes it look like the question is an LC easy
It was a very difficult problem to solve until I watched this video. Keep the great work up!
Underrated channel in Leetcode solution. Highly recommending this channel for Algo preparation
Thanks for a great explanation! I am starting to play with algorithms, and this has been a big help.
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
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
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
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)
Did a few changes and was able to get 0ms runtime in Java :)
Thanks NeetCode ❤
watched atleast 10 videos on the same problem , yours explanation was the best and simplest . Thank you
i double this
@@abhinavkumarr damn another me !
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.
i am too dumb to come up with an optimal approach, unless I have sen such trick before
The Best explanation video on UA-cam
Nicely explained, simple and elegant solutions.
This was so easy to understand and very neatly explained. Thank you so much!
I don't even code in Python but I love your explanations, hence a subscriber.
This is the first hard problem I have ever solved! Although I only got the O(n)/O(n) solution (I used linear extra space for the "left" side), not O(1) space. I knew it must be possible with two pointers since I did Container With Most Water, I just couldn't quite get the logic correct.
Such a detailed explanation! Thank you!
So are people actually able to recognize by intuition that the smaller max between the two pointers is always the bottleneck regardless of what's in the rest of the array? I feel like you'd have to be a genius to logically prove that on the spot, unless you've seen the problem before.
Actual best, most efficient explanation!!
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.
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
best explanation for this problem on yt. Thank you
My suboptimal o(n) memory solution using the explanation if anyone interested
class Solution:
def trap(self, height: List[int]) -> int:
maxleft = [0] * len(height)
maxright = [0] * len(height)
res = 0
maxleft[0] = height[0]
for i in range(1, len(height)):
maxleft[i] = max(height[i], maxleft[i-1])
maxright[-1] = height[-1]
for i in range(len(height) - 2, -1, -1):
maxright[i] = max(height[i], maxright[i+1])
for i in range(len(height)):
water = min(maxleft[i], maxright[i])
res += water - height[i]
return res
This is one crazy problem. Thanks for this great video!
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]"
Whyyyy
Your explaination of concept is so easy to understand!!!!!! keep making videos!!!!!
You are amazing mate !!!! I cant thankyou enough. Crisp, easy and efficient solutions.
This is my first solved hard leetcode problem.
Hi NeetCode, thanks for your awesome explanation! I just have a question about the tools you've been using for creating these kinds of content. Do you mind sharing about it?
Business band karayegi tu bro
Paint 3D and a computer mouse
I don't know why I feel like line 14 should have been before line 13 according to his explanation, his solution still works. Because in that case we could be updating leftMax with height[l] without knowing if righMax is greater than height[l] or not. I am confused.
Update (I think I got it):
According to the way I am suggesting, we will have to check for negative values which his solution cleverly eliminates.
U make it look so easy ❤️ thanks a lot ☺️
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!
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]
Same doubt 🙋♀️
It helped me realize the solution after 2 min of watching! Thank you!
I think you prob deserve more credit for that then 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.
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.
this is super intuitive and easy thank you for the solution keep it up sir
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
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 !
I don't know if I'm being dumb, but I feel like the code is slightly different from the explanation.
I thought the code below might align more with the explanation, and easier to understand for my monkey brain 😂
if not height:
return 0
left, right = 0, len(height) - 1
left_max, right_max = height[left], height[right]
res = 0
while left < right:
if left_max < right_max:
left += 1
amount = left_max - height[left]
if amount > 0:
res += amount
left_max = max(left_max, height[left])
else:
right -= 1
amount = right_max - height[right]
if amount > 0:
res += amount
right_max = max(right_max, height[right])
return res
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!*
You Are So Good At Explaining! Thanks!
this was amazing, proud of your videos NC, keep up the good work.