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.
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
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 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 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 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.
@@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 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 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)
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.
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!
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)
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.
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.
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]"
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).
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.
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.
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.
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
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!! 😁
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
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 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 ```
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!
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.
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
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 ?
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.
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]
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 :)
Thanks, this is a great algorithm. I came up with an alternate solution myself which I was pretty proud of - using a Stack of a little struct to keep track of each 'active' layer of water (including how deep it is, where it began from, and how far offset from the ground it is), then closing them off and updating the total when they encounter a wall, and then any which never hit a wall never get counted. It passed all the cases on Leetcode but was much less elegant than this. However, does anyone know if the Runtime/Memory info on Leetcode is accurate? Because I implemented this algorithm afterwards, and got almost identical results in speed/memory usage, which can't be right
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 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.
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
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.
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?
Refer to the immediately above line of leftMax - height[l]. leftMax will be initialized as 0, which means that it will be 0 (leftMax) - 0 (height[l]) = 0, not any other negative value.
This is definitely helpful, but the amount of times you say "right" (in the context of "we are doing , right?!", not the variable right) makes this confusing, given that we have variables that refer to right and left.
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!*
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.
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
