You didn't explain, why you are moving the minimum of the two pointers? What is the basis of this idea? Please do not take this other way, just a feedback from people like me who do not understand so easily. You are putting great effort. I feel there is a lot of logic behind incrementing the minimum pointer. We'll not get max area in any case , even if the next pointer is big, small or equal. This has to be explained I feel. Thank you.
@@bhaskyOld That's a good question, we should move the pointer with the lowest height because we are essentially trying to maximize both height and width. If we always drop the one with the lowest height, the height will only increase, with this intuition we will find the greatest solution as we will definitely encounter the point where both height and width are maximized, which reduces unnecessary checks. Does that make sense Bhasky?
I think a good explanation for why we move pointer with the lower height is because we already have the max area with that height - since it is the lower pointer that means that every other distance that is closer will always be a smaller distance with the same or less height which means smaller area. Therefore we do not need to look at every other combination with that pointer.
@@Billych68 So, let i=0 and j=n-1, say we are considering a pair of vertical lines, h[i] and h[j], we know that the area of the current pair is maximum area for the shorter line (because the width is at maximum). Therefore, we can move the index corresponding to the shorter line inward. This process ensures that the outer lines (the ones to the left of i and to the right of j) has been checked for their possible max area. You can iterate this process on a paper and check the ones that has been maxed out. You will see that at any given i,j the area of the outer lines would be maxed out before we consider i,j. note: the process does not stop at i,j that gives maximum area, rather it iterates until i==j while keeping track of the maximum area.
This was so unintuitive damn. I was trying to sort the array to find optimal solution but got wrecked in edge cases. Anyone else thought this was unintuitive?
Explanation for equal heights edge case: Let's say we are at l, r where H = h[l] = h[r[. The recommendation would be to update both l and r. Why? The current computed area is A = H * (r-l). No other combination of h[i] and H s.t l < i < r can result in an area greater than A as the area would always be bounded by H i.e. H*(i-l) or H*(r-i) both of which are always smaller than A. Note by the time we reach this state of having equal height H, the max area with H as a boundary is either the current area A or already computed in a past iteration.
For hard questions, I always watch Neetcode explanation first (as they tend to be shorter and clearer than others), and then often check how other TH-camrs explain by walking through DP solutions on a whiteboard. Medium ones Neetcode does really well. Hard ones are usually longer and tend to require more than one channel to fully understand the implementation. I've been doing easy and medium for a year now, only recently started doing hard problems. Neetcode will hopefully add more of the harder ones.
Although there are some good explanations already on why we move the pointer with the lower height inward, here is another perspective. The objective of the problem is to maximize min(heights[a], heights[b]) *⋅* (b - a). We start off the problem with the pointers at the edges. If either pointer moves inward, that second term (b - a) is always going to decrease, so that is out of our control. But if we move the higher-height pointer inward, the first term min(heights[a], heights[b]) can only decrease or remain fixed. To see why, note that there are two cases: 1) The higher-height pointer reaches an even higher height-since we are taking the min, the term will remain the same; 2) We reach a lower height-then the term may either stay fixed or decrease if it is lower than the other pointer's height. On the other hand, moving the lower-height pointer inward, there are once again two cases: 1) The lower-height pointer reaches a higher height, then the term will always increase; 2) We reach a lower height, then the term decreases. So in order to maximize the first term, min(heights[a], heights[b]), we must move the lower-height pointer inward, as moving the higher-height pointer inward yields only decreases (or fixed). (note that the second term (b - a) is ensured to be as max as it can as we start the pointers at the edges, and move inward (thereby decreasing the term) to check for potential maximums, while keeping a max variable).
Whenever I always have a problem solving these interview questions, I always look at your videos first. I love the way you draw things out and help us visualize the problem. It's such a great way of understanding it. Thank you very much!
If both heights are equal you can move both pointers because you're already bound to at most that height anyways so that max couldn't be any more than that position anyways since moving either pointer in will yield an area either less than or equal to the area at your current positions.
He mentions flippantly "In this case it doesn't actually matter which pointer that we shift" 8:13 but I want to raise a question: What if the 3rd of the 4 bars between the 8s... is a 9 (instead of a 5)? The 9 would of course be 3 spaces away from the L->8, but only 2 spaces away from the R->8 So then, the "L and R same size edge case" arbitrary choice of always shifting the left does matter, right? Because, imagine we're on 8L and 8R: If we shift left we only ever see 9L to our 8R, right which is 8x2. If we shifted the right however we would see 8L and 9R, which is 8x3. Depending on the direction you shift you never get to one of the computations. I'm having trouble wrapping my head around how it can possibly not matter, or where my logical error is.
*This is an absolutely CRUCIAL comment to this problem that actually makes this video problematic in not having it*. 8:12 It is the KEY, pivotal point in this entire exercise, and illustrates how even an expert like the @NeetCode author can miss a pivotal point and craft and algorithm that demonstrates not understanding the fundamental axiom of the whole question. Moving just one pointer arbitrarily shows a lack of understanding this core concept of the equation, and why you're doing what you're doing, and where you currently stand in the equations execution in which you must author its next choice. Many entire questions boil down to this exact choice. It absolutely does matter which pointer you move, because they ARE NOT equal, as you will cover some paths and not others depending. However, it also DOES NOT matter which you move, and you instead should just move both (if you truly understand), because of the fundamental tenant @ChristopherPerry keenly has considered, grokked, and outlines.
@@ianokay let's say you have a really tall bar between the 8s, but that still be bound by one of the 8s because we compute area by min height. That's why it doesn't matter which pointer to move. However, if you have 2 really tall bars between the 8s, eventually loop will reach to both of them, because if let's say left pointer reached the first tall, from this point only right pointer will move left until it reaches 2nd tall.
Couldn't help but take a moment to leave a comment on this. It has been a long time goal of mine to become a better programmer through practicing leetcode questions but I always felt super defeated when I would try random questions from leetcode and make little to no progress. Neetcode has given me a way to incrementally improve my knowledge and show real progress. For the first time I am solving leetcode questions on my own. Disclaimer it is very rare that I solve them on my own my first try but it is happening more often as I progress. Thank you Neetcode!!!
I have been following your roadmap, and it really help me learn a lot. As your roadmap group the same type of questions together, I know this is a two pointers problem and solve this question by myself. Coming from someone that has no idea whats going on in any leetcode questions, to doing a medium question alone, I feel so good and thanks again for the roadmap!
This is the first problem I was able to solve with 0 help, and 0 bugs first try. The runtime was faster than 94%+ and Space better than 97%+. All of this was because of the explanation videos you provide for all of these problems :). Thank you for these.
I've been following your roadmap and this was the first medium problem i was able to come to the same solution as you did on my own. I'm super happy to see myself progressing! Thanks for the videos!
Great solution! There is an optimization. When height[left] < height[right], we can use a while loop to find the next index of left which satisfies height[left+step] > height[left] to avoid unwanted calculations.
This is a great optimization, I wonder if the additional check usually ends up being worth it however, as there are some cases where this may not reduce any calculations.
cant we do the same for height[right] < height[left]? moving the right pointer backwards until we find the new valid right index? isnt' a simple arithmetic calculation very negligible in terms of cost?
Your leetcode videos are my favorite because you don't jump straight into code. You start with the most basic solution and show us how to refine our thought process to find the optimal solution. Thanks for all you do!
@@hadeeltantawy3244 @Nikola Huang I'm not 100%, but I think it has something to do with the fact that the smaller of the two heights limits the total area. I'd love to have a full explanation though too. Even if I had come up with this idea on my own upon first encounter, I think I would quickly dismiss it because I'd think it might miss the global optimum.
Hi, I think the reason why this approach works is that for every width, we're trying to maximize the area and then find the maximum of all those areas. For the l=0 & r=arr.size()-1 we only have one solution possible, but after this for every width we have multiple solutions possible and so we greedily try to pick the maximum minimum pointer as that will be the limiting factor for any given width.
Thank you so much for creating this channel! My method in the past to studying algorithms was to just try to figure it out myself, sometimes getting stuck for a day. I've been watching your videos and I find it very helpful listening to you break down a problem with easy to understand pseudo code and then trying to implement the solution in code myself (without looking at your coded solution).
I have more gratitude now for seeing this video finally! Thanks a lot NeetCode for such great explanation. This question was asked in Microsoft interview and I had hard time understanding the problem (histogram) and coming up with solution back then in 2019. I had searched n-videos which had poor explanation and complex solution. You made my day ! I cannot thank more
On the edge case where the array values of the two pointers are equal, why does it not matter whether you increment the left pointer or decrement the right one? Here's why: Because whichever one you choose, the other "side" of the container is going to be that previous height. So the new area is always less than or equal to the old area (since if you increment L to a larger value of decrement R to a larger value, it's mitigated by the fact that we can't overflow the container!) Thus it doesn't matter.
hello! what if at the 8:30 mark the tallest column is left to 8 (say 20) ? the max product would be 6 * 20. but we move to the right of 6 - and lets say everything to right of 6 is much smaller. so we never computed the max ? I think the movement to left and right should not be dictated by the lower of the two heights (rather by the delta of the two new possibilities compared to current area). because even shifting to the left of the greater height can yield the max (if this delta is quite positive).
it wouldn't be 6 * 20, rather min(6,20) * distance. So it doesn't matter if we shift to the left or right. If the value is smaller, 10 would be the optimal choice, if it's bigger we shift on the other side next which gets us 20 example 1: [1,10,6,2,5,20,10,3,7] we start by shifting right: 6 and 10 and so on still smaller, we start by shifting left: 20 and 10 => still 10 and 10 bigger. example 2: [1,10,30,2,5,20,10,3,7] we start by shifting right: 30 and 10 => still smaller. we shift left since 30 > 10, 30 and 20 new max. we start by shifting left: 20 and 10 => still smaller. we shift right since 20 > 10, 30 and 20 new max. tldr: shifting right or left in case equal doesn't change the result.
In case both heights are equal and after calculating the area, shouldn't we move both sides ? as there is no other area would exceed that area with one of them as a side (even if the new side is taller) and smaller length in between
Great explanation. This is a type of problem which don't have any complicated edge cases and is very easy to understand at first read (perfect for interviews) but the optimal solution is quite subtle.
I love you man. I have been trying to learn how to solve leetcode problems for 3 years and I came up dry. Then I came across your videos and they helped me more than anything else. You inspired me to share my knowledge. That is why I started my channel. Thank you very much again. If I ever come to seattle (I think you live there) I will take you to lunch.
I'm so excited that I solved this problem just now. And my idea is the same as yours. The only difference is the variable names. Lol Anyway, thank you for providing so many good videos. I've learned a lot.😀
I attempted to solve it on my own and was soooo close to the solution but off by a misplaced if-else statement. Solved it in a second after you mentioned to move the pointer from the minimum height. Thank you for all you do!! Today is a day I feel smart while coding lol.
I don't full understand how this works. How are we able to skip all the combinations and be certain that the omitted combinations won't work? For example 9:32 the combination of 7 and 6, and many others, were never examined. So what's the "magic" where this algorithm will work by skipping iterations of all combinations?
Thanks for great explanation. I can follow along once we decide l=start and r=end. I was stuck with l=start and l=start+1. How to decide where to place the 2 pointers initially?
He literally did, you calculate the max length and width from left to right and keep updating the max value. What I tried was starting with the max value and the second max value then calculating the width lmao I am trash
It's sad I couldn't figure it out on my own. The brute force solution is obvious, but the O(n) one seemed COMPLETELY impossible to me. I don't even know what my problem was. I thought I had to: 1. Pick any of the r and l pointers 2. Find the best next pole for the current situation and move a pointer to it. The first step is already wrong. There's absolutely no reason to pick ANY pointer. You should pick the one that's at smaller height. The second step is also wrong. I shouldn't have been so concerned with the best for current situation, 'cause at some point there could be no better poles to move to for my current situation even if there are two 999999 height poles in the middle. But I still don't know how to find optimal algorithm. I don't know how to "see" it. It's not tangible for me YET. But I'm only getting started!
My five cents: Since the width is always decreasing when you move the pointer, you can simply look for the next height which is taller than the current height, only that case gets a potential area increase. 🤓
For these types of problems, is there any pattern we could learn other than just using two pointers? This problems just seems like you either can figure out what you need to do or you don't figure it out and fail. Is there any recommendation, on how I could approach these types of two pointer problems and get better at them?
You don't need to check the area after moving the pointer every time, if you move the pointer for the lower height, and the height it moves to is even lower, you can keep moving it, as there's no way the area could be smaller, so you keep moving it until you find a height greater than the height you used for your previous area. You also can use the mathematical ratio that defines whether the area will be larger with different heights, without directly computing the area, and only compute the area at the end.
Notice if the new height is smaller than the previous height, then we can skip that height. def maxArea(self, height: List[int]) -> int: res = 0 l, r = 0, len(height) - 1 preL, preR = 0, 0 while l < r: if preL > height[l]: l += 1 continue if preR > height[r]: r -= 1 continue area = (r - l) * min(height[l], height[r]) res = max(res, area) if height[l] < height[r]: preL = height[l] l += 1 else: preR = height[r] r -= 1 return res
We could further optimize it by keeping track of the current left max and right max, dont do any calculation if new left or new right is smaller than the cur left or right max
This is incredible youtube channel with such incredible videos. I have been thinking on this problem for a week, I actually knew your video but I wanted to get right point myself. My only mistake was I have been moving pointers when new maximum result is bigger than previous one but now I saw your technique and I say myself why I didn't watch video earlier. Your channel helps me lot, thank you very much!! Keep up this good work!
One extra step we can take is instead of moving a pointer just one step, we can keep moving it until it finds a height greater than the one it left (or reaches the end condition, in which case there is no greater volume). The only way a volume can be greater than the current volume is if the height of the container is taller. If it's shorter or even the same height, the volume will be less since the width has shrunk. In practice, this allows us to check the volume at only three points, the (0,8) pair (first and last lines), the (1,8) pair (the actual solution, whose volume is 49), and the (1,6) pair (whose volume is 40). This solution passes all of LeetCode's test cases.
I have managed to learn how you approach problems and tried my hands on this problem and was able to solve the first try. Thank you so much for these videos, mean a lot!
What if the 3rd of the 4 bars between the 8s... is a 9? Then, the "L and R same size edge case" arbitrary choice of always shifting the left does matter, right? Because, imagine we're on 8L and 8R: If we shift left we only ever see 9L to 8R, right which is 8x2. If we shifted the right however we would see 8L and 9R, which is 8x3
I could not figure it out, but after watching this video solution. It turns out that the solution was actually pretty simple and easy to understand, I makes me wonder why I could not think of it.
Actually it doesn't matter. If you think about it, you will not get a container bigger than the one with equal heights unless there exist two or more bigger heights WITHIN those positions. If you had an array of [8, 1, 5000, 2, 8], your biggest container is the one containing 8 and 8. Say you had an array of [8, 5, 50, 100, 2, 8]. The code will always end up checking the bigger heights so it will calculate and compare the area of the 50 and 100 position whether you move the left or right pointer first. You can always try it out, when the pointers have equal heights, write code to move the left pointer and then write code to move the right pointer. You will see you get the same results.
Great video! Could u explain a bit more why when it comes to the result that left and right have the same value, why it doesn’t matter to move either left or right?
Turns out you can actually move the left *and* the right pointer at the same time when the heights are equal, which is why it doesn't matter which one you pick. The reason why you can move both is because the goal of moving the left or right pointer is to increase min(height[l], height[r])* and if height[l] == height[r], then both height[l] and height[r] are equal to the minimum (let's call it m). Since min(something_else, m) can't be greater than m, we have to change both values if we want min(min(height[new_l], height[new_r])) to increase. *technically, we're trying to increase the volume of the container, which is width*m, but since width is always decreasing when we move our pointers inward we need m to increase.
@@nilsh5027 I'm not convinced by your explanation. We can check whether right of left and left of right is greater or smaller. For example, here there is 6 and 4. We must choose 6 as an left and decrease from right. So area will get increased. If condition again ties we can use recursion.
Good question : Simple answer would be try to run this code for x in range (3,2): print(True) The loop will not run at all because as defined above loop will run until the value is less than 2 but our initial value is 3 there
I guess instead of comparing heights of left and right, you could compare the height of left to min(height[l], height[r]). If the height of left is equal to min(height[l], height[r]), you would increment the left pointer because it is the bottleneck. Else, decrement the right pointer because that is the bottleneck. Otherwise, I did the same thing.
Area is L x W. To maximize it you need to maximize both L and W. Since our left and right pointers begin at the leftmost and rightmost, W is always maximized. Now we have to maximize L. Our max L will always be the larger of the two pointers so we move the smaller of the two to keep L maximized.
This is my 45th question which i solved and am comfortable with medium array question now still struggling with hard but the point is if your channel didn't exist learning wouldn't have been so easy for me really thanks man keep going.
Ive watched all your videos for all your neetcode150 and really amazing stuff. I didn't know where to post this but I just have one thing I needed to point out. the solutions coded in python are great, but who ever was in charge of posting the solutions in javascript did a beyond awful job. im talking like truly truly horrible, to the point it would get me extremely frustrated as an interviewer to see a candidate write code that way. The person rights drastically more than needed, and while sometimes thats good if it makes the code more readable, the opposite actually is true. a 7 line solution in python for some reason has several different functions in javascript that are a mess and confusing to follow. Im honestly happy to redo the javascript solutions for you, but wanted to at least call it your attention. whoever did it, did a really awful job. anyways your explanations are top notch. thank you.
As the list of bars are not sorted we can not be sure that about moving left or right pointer will be give us optimal answer by just looking at left and right . Correct me if am wrong.
i think after several arrays problem, one has picked up the two pointers technique. but for this particular problem, all the signs like big array input that requires faster running time that O(n^2) and the max product is based on multiplication of two numbers in the array requires retrieval of two numbers in an array hints at using the two pointers technique even more
I am quite annoyed by the fact that I was able to come up with the optimal solution for this problem, but still couldn't quite explain if this would be correct for all cases, and after watching your video I still can't explain why this works for all valid cases Can someone help me with this?
I just wasted two hours doing the brute force solution. I always do it first as it gives me a clearer idea on what is going on. The problem is that I didn't understand why 8 * 8 wasn't the answer... I had to reread the problem like a thousand times.
Instead of going through every possible combination, the two pointer approach tries to maximize some aspect of the problem... In this case, we must maximize the width between two columns, moving right or left the column with smallest height, and keeping track of the container's max area along the way.
When left and right are equal we can check whether right of left and left of right is greater or smaller. For example, here there is 6 and 4. We must choose 6 as an left and decrease from right. So area will get increased. If condition again ties we can use recursion.
Small Optimization - If both the bars have same height do l++ and r-- . Reason - suppose array contains all the bars or some bars of same size so by doing l++ and r-- will take half iterations.
actually, when we move pointers we don't need to check for max water numbers, that a lower then current. it will not be possible to bigger square is next number is same or lower.
By seeing the problem statement, i taught solution will be very difficult , but the way you explained now i can feel problem was very simple and easier to solve Thanks for explanining in simpler way
Everytime, we are moving our pointer i ahead if height of line at ith index is smaller or j pointer if height of line at jth index is smaller. This means whichever line is smaller, we won’t consider it again, because, this line could be the answer only if the other line is larger than it and at maximum width and to be noticed that this is the time when other line is larger as well as max distance apart. So, not considering it makes sense.
What is the thinking pattern to come up with such solutions? I figured two pointer technique but couldn't figure out what condition to set to move the pointers. I have been bugging my mind whole day :(
@@tonynguyen6124 i thought about it and figured that it won't matter as if left/right pointer moves and reaches a higher point, its current volume would be less than the global max volume of water. And upon reaching a higher point, the opposite pointer will be the next to traverse, so it really doesn't matter. Let me know if my explanation is sound haha
ok but i have a question. I wrote the same code but with a for look in the range(len(heights)) and it ran much faster than your code. why does the while loop make it much slower? [for context, for loop runs faster than 96% of all pythons solutions, where as the while loop one runs faster than just 10%)
Thanks for awesome work, man! I was initially slicing the target array by left and right pointers to get its' length, but when I saw your method of getting the area I realized how dumb my way was :)
I tried this approach whereby I moved the pointers such as to maximise the area at each step, but I got wrong answer. I don't understand why Neetcode's solution is mathematically guaranteed to work. The problem looks to be a greedy one, but maximising the area locally gave me wrong answer. Why does NeetCode's solution work? My solution for reference: class Solution { public: int getArea(int left_idx, int left_val, int right_idx, int right_val){ return min(left_val, right_val) * (right_idx - left_idx); } int maxArea(vector& height) { int left_idx = 0; int right_idx = height.size()-1; int max_area = -1; while(left_idx max_area){ max_area = curr_area; } if (left_idx == right_idx){ break; } // let us try to decide which pointer to move int left_move_area = getArea(left_idx+1, height[left_idx+1], right_idx, height[right_idx]); int right_move_area = getArea(left_idx, height[left_idx], right_idx-1, height[right_idx-1]); if(left_move_area >= right_move_area){ left_idx++; } else{ right_idx--; } } return max_area; } }; EDIT: I saw a reply by @hunterlee1249. It makes sense now.
Is this an edge case that doesnt work? The most left height is lets say 9, the second index is 100, everything else is 8. How would you get the output to be 100 and the most right 8
The output wouldn't be 100, since the minimum height of either side of the container is the bottleneck. In this case the output should be 8 * n where n is the size of the array
![[TH] 2024 PMSL SEA W2D2 | Fall | เครื่องร้อน พร้อมลุย](http://i.ytimg.com/vi/JO2_bLow_1Y/mqdefault.jpg)
🚀 neetcode.io/ - I created a FREE site to make interview prep a lot easier, hope it helps! ❤
You didn't explain, why you are moving the minimum of the two pointers? What is the basis of this idea? Please do not take this other way, just a feedback from people like me who do not understand so easily. You are putting great effort. I feel there is a lot of logic behind incrementing the minimum pointer. We'll not get max area in any case , even if the next pointer is big, small or equal. This has to be explained I feel. Thank you.
Nick white is better
@@bricksnbuttons2000 then what are you doing here?
Why can't this be solved using monotonous stack ? Isn't this question same as 'Largest Rectangle in Histogram' problem in leetcode ?
@@bhaskyOld That's a good question, we should move the pointer with the lowest height because we are essentially trying to maximize both height and width. If we always drop the one with the lowest height, the height will only increase, with this intuition we will find the greatest solution as we will definitely encounter the point where both height and width are maximized, which reduces unnecessary checks. Does that make sense Bhasky?
I think a good explanation for why we move pointer with the lower height is because we already have the max area with that height - since it is the lower pointer that means that every other distance that is closer will always be a smaller distance with the same or less height which means smaller area.
Therefore we do not need to look at every other combination with that pointer.
Thanks, I was missing that part of the explanation
@@Billych68 So, let i=0 and j=n-1, say we are considering a pair of vertical lines, h[i] and h[j], we know that the area of the current pair is maximum area for the shorter line (because the width is at maximum). Therefore, we can move the index corresponding to the shorter line inward. This process ensures that the outer lines (the ones to the left of i and to the right of j) has been checked for their possible max area. You can iterate this process on a paper and check the ones that has been maxed out. You will see that at any given i,j the area of the outer lines would be maxed out before we consider i,j.
note: the process does not stop at i,j that gives maximum area, rather it iterates until i==j while keeping track of the maximum area.
This was so unintuitive damn. I was trying to sort the array to find optimal solution but got wrecked in edge cases. Anyone else thought this was unintuitive?
yes when height[l] == height[r], no matter if r += 1 or l -=1, the area is always gonna be smaller in the next step . that's y we can do either .
Great Explanation!
Explanation for equal heights edge case:
Let's say we are at l, r where H = h[l] = h[r[. The recommendation would be to update both l and r. Why? The current computed area is A = H * (r-l).
No other combination of h[i] and H s.t l < i < r can result in an area greater than A as the area would always be bounded by H i.e. H*(i-l) or H*(r-i) both of which are always smaller than A. Note by the time we reach this state of having equal height H, the max area with H as a boundary is either the current area A or already computed in a past iteration.
Thanks for the explanation, this is the only part of the solution which I was a bit perplexed about
Dont go any further guys - This is the best channel for leetcode solutions ; Neetcode - you are the leetcode king
For hard questions, I always watch Neetcode explanation first (as they tend to be shorter and clearer than others), and then often check how other TH-camrs explain by walking through DP solutions on a whiteboard. Medium ones Neetcode does really well. Hard ones are usually longer and tend to require more than one channel to fully understand the implementation. I've been doing easy and medium for a year now, only recently started doing hard problems. Neetcode will hopefully add more of the harder ones.
I agree. Hard questions made easy.
Although there are some good explanations already on why we move the pointer with the lower height inward, here is another perspective.
The objective of the problem is to maximize min(heights[a], heights[b]) *⋅* (b - a). We start off the problem with the pointers at the edges. If either pointer moves inward, that second term (b - a) is always going to decrease, so that is out of our control.
But if we move the higher-height pointer inward, the first term min(heights[a], heights[b]) can only decrease or remain fixed. To see why, note that there are two cases: 1) The higher-height pointer reaches an even higher height-since we are taking the min, the term will remain the same; 2) We reach a lower height-then the term may either stay fixed or decrease if it is lower than the other pointer's height.
On the other hand, moving the lower-height pointer inward, there are once again two cases: 1) The lower-height pointer reaches a higher height, then the term will always increase; 2) We reach a lower height, then the term decreases.
So in order to maximize the first term, min(heights[a], heights[b]), we must move the lower-height pointer inward, as moving the higher-height pointer inward yields only decreases (or fixed).
(note that the second term (b - a) is ensured to be as max as it can as we start the pointers at the edges, and move inward (thereby decreasing the term) to check for potential maximums, while keeping a max variable).
This explanation helped me finally understanding it completely, thank you!
Excellent!!! Thanks a lot.
Good explanation! Thanks!
Thanks
Thank you! Your explanation helped me to finally understand this question!!
Whenever I always have a problem solving these interview questions, I always look at your videos first. I love the way you draw things out and help us visualize the problem. It's such a great way of understanding it. Thank you very much!
Thanks, happy it's helpful! 🙂
If both heights are equal you can move both pointers because you're already bound to at most that height anyways so that max couldn't be any more than that position anyways since moving either pointer in will yield an area either less than or equal to the area at your current positions.
Was looking for this! Thank you.
He mentions flippantly "In this case it doesn't actually matter which pointer that we shift" 8:13 but I want to raise a question:
What if the 3rd of the 4 bars between the 8s... is a 9 (instead of a 5)?
The 9 would of course be 3 spaces away from the L->8, but only 2 spaces away from the R->8
So then, the "L and R same size edge case" arbitrary choice of always shifting the left does matter, right?
Because, imagine we're on 8L and 8R: If we shift left we only ever see 9L to our 8R, right which is 8x2. If we shifted the right however we would see 8L and 9R, which is 8x3.
Depending on the direction you shift you never get to one of the computations. I'm having trouble wrapping my head around how it can possibly not matter, or where my logical error is.
*This is an absolutely CRUCIAL comment to this problem that actually makes this video problematic in not having it*. 8:12 It is the KEY, pivotal point in this entire exercise, and illustrates how even an expert like the @NeetCode author can miss a pivotal point and craft and algorithm that demonstrates not understanding the fundamental axiom of the whole question. Moving just one pointer arbitrarily shows a lack of understanding this core concept of the equation, and why you're doing what you're doing, and where you currently stand in the equations execution in which you must author its next choice. Many entire questions boil down to this exact choice. It absolutely does matter which pointer you move, because they ARE NOT equal, as you will cover some paths and not others depending. However, it also DOES NOT matter which you move, and you instead should just move both (if you truly understand), because of the fundamental tenant @ChristopherPerry keenly has considered, grokked, and outlines.
@@ianokay let's say you have a really tall bar between the 8s, but that still be bound by one of the 8s because we compute area by min height. That's why it doesn't matter which pointer to move. However, if you have 2 really tall bars between the 8s, eventually loop will reach to both of them, because if let's say left pointer reached the first tall, from this point only right pointer will move left until it reaches 2nd tall.
@@rootr00t Amazing explanation, thanks!
Couldn't help but take a moment to leave a comment on this. It has been a long time goal of mine to become a better programmer through practicing leetcode questions but I always felt super defeated when I would try random questions from leetcode and make little to no progress. Neetcode has given me a way to incrementally improve my knowledge and show real progress. For the first time I am solving leetcode questions on my own. Disclaimer it is very rare that I solve them on my own my first try but it is happening more often as I progress. Thank you Neetcode!!!
amazing how you explain almost every code with such ease and such clarity
I have been following your roadmap, and it really help me learn a lot. As your roadmap group the same type of questions together, I know this is a two pointers problem and solve this question by myself. Coming from someone that has no idea whats going on in any leetcode questions, to doing a medium question alone, I feel so good and thanks again for the roadmap!
This is the first problem I was able to solve with 0 help, and 0 bugs first try. The runtime was faster than 94%+ and Space better than 97%+. All of this was because of the explanation videos you provide for all of these problems :). Thank you for these.
I've been following your roadmap and this was the first medium problem i was able to come to the same solution as you did on my own. I'm super happy to see myself progressing! Thanks for the videos!
Great solution! There is an optimization. When height[left] < height[right], we can use a while loop to find the next index of left which satisfies height[left+step] > height[left] to avoid unwanted calculations.
This is a great optimization, I wonder if the additional check usually ends up being worth it however, as there are some cases where this may not reduce any calculations.
cant we do the same for height[right] < height[left]? moving the right pointer backwards until we find the new valid right index?
isnt' a simple arithmetic calculation very negligible in terms of cost?
Your leetcode videos are my favorite because you don't jump straight into code. You start with the most basic solution and show us how to refine our thought process to find the optimal solution. Thanks for all you do!
I can see the algorithm gives us a local optimum because it is greedy. But why the local optimum is guaranteed to be the global optimum?
Adding to your question, how did you figure out that a greedy approach was to be used?
I have the same question, what guarantees that a greedy solution will give global optimal?
@@hadeeltantawy3244 @Nikola Huang I'm not 100%, but I think it has something to do with the fact that the smaller of the two heights limits the total area. I'd love to have a full explanation though too.
Even if I had come up with this idea on my own upon first encounter, I think I would quickly dismiss it because I'd think it might miss the global optimum.
Hi, I think the reason why this approach works is that for every width, we're trying to maximize the area and then find the maximum of all those areas. For the l=0 & r=arr.size()-1 we only have one solution possible, but after this for every width we have multiple solutions possible and so we greedily try to pick the maximum minimum pointer as that will be the limiting factor for any given width.
I see, by "greedy", you mean that res is always increasing. Good questions !
Thank you so much for creating this channel! My method in the past to studying algorithms was to just try to figure it out myself, sometimes getting stuck for a day. I've been watching your videos and I find it very helpful listening to you break down a problem with easy to understand pseudo code and then trying to implement the solution in code myself (without looking at your coded solution).
Thank you for starting with brute force approach. This is how all TH-cam videos should be. Discuss various approaches, evolution and trade offs.
I have more gratitude now for seeing this video finally! Thanks a lot NeetCode for such great explanation. This question was asked in Microsoft interview and I had hard time understanding the problem (histogram) and coming up with solution back then in 2019. I had searched n-videos which had poor explanation and complex solution. You made my day ! I cannot thank more
Thanks! I'm Really happy it was helpful 😃
On the edge case where the array values of the two pointers are equal, why does it not matter whether you increment the left pointer or decrement the right one?
Here's why:
Because whichever one you choose, the other "side" of the container is going to be that previous height. So the new area is always less than or equal to the old area (since if you increment L to a larger value of decrement R to a larger value, it's mitigated by the fact that we can't overflow the container!) Thus it doesn't matter.
hello! what if at the 8:30 mark the tallest column is left to 8 (say 20) ? the max product would be 6 * 20. but we move to the right of 6 - and lets say everything to right of 6 is much smaller. so we never computed the max ? I think the movement to left and right should not be dictated by the lower of the two heights (rather by the delta of the two new possibilities compared to current area). because even shifting to the left of the greater height can yield the max (if this delta is quite positive).
it wouldn't be 6 * 20, rather min(6,20) * distance. So it doesn't matter if we shift to the left or right. If the value is smaller, 10 would be the optimal choice, if it's bigger we shift on the other side next which gets us 20
example 1:
[1,10,6,2,5,20,10,3,7]
we start by shifting right: 6 and 10 and so on still smaller,
we start by shifting left: 20 and 10 => still 10 and 10 bigger.
example 2:
[1,10,30,2,5,20,10,3,7]
we start by shifting right: 30 and 10 => still smaller. we shift left since 30 > 10, 30 and 20 new max.
we start by shifting left: 20 and 10 => still smaller. we shift right since 20 > 10, 30 and 20 new max.
tldr:
shifting right or left in case equal doesn't change the result.
Ugh, I hate that I need to look up some of these solutions, feels like I've been defeated :( Thanks though lol.
Same here
In case both heights are equal and after calculating the area, shouldn't we move both sides ? as there is no other area would exceed that area with one of them as a side (even if the new side is taller) and smaller length in between
Great explanation. This is a type of problem which don't have any complicated edge cases and is very easy to understand at first read (perfect for interviews) but the optimal solution is quite subtle.
This is the point 6:40 I was looking for in the optimal solution on how to move the pointers - Thanks for the explanation
Exactly !. Same point i got struck hehe. Happy to see Many of them here are in same page 😇
I love you man. I have been trying to learn how to solve leetcode problems for 3 years and I came up dry. Then I came across your videos and they helped me more than anything else. You inspired me to share my knowledge. That is why I started my channel. Thank you very much again. If I ever come to seattle (I think you live there) I will take you to lunch.
I'm so excited that I solved this problem just now.
And my idea is the same as yours. The only difference is the variable names. Lol
Anyway, thank you for providing so many good videos. I've learned a lot.😀
I attempted to solve it on my own and was soooo close to the solution but off by a misplaced if-else statement. Solved it in a second after you mentioned to move the pointer from the minimum height. Thank you for all you do!! Today is a day I feel smart while coding lol.
Very clear and intuitive. Thanks for the work!
Thanks!
I don't full understand how this works. How are we able to skip all the combinations and be certain that the omitted combinations won't work? For example 9:32 the combination of 7 and 6, and many others, were never examined. So what's the "magic" where this algorithm will work by skipping iterations of all combinations?
I hope to get better at solving problems like you do! keep up! I love your content and explanations
Thanks for great explanation. I can follow along once we decide l=start and r=end. I was stuck with l=start and l=start+1. How to decide where to place the 2 pointers initially?
Is there anyone who can prove why this works? Not sure how I’ll come with such solutions in interview settings. :)
^
He literally did, you calculate the max length and width from left to right and keep updating the max value. What I tried was starting with the max value and the second max value then calculating the width lmao I am trash
I don't think the interviewer expect a perfect solution for the question he wants to see how the candidate thinks and approaches the problem
Brute Force:
------------------------
class Solution:
def maxArea(self, height: List[int]) -> int:
maxVol = 0
n = len(height)
for i in range(n):
for j in range(i + 1, n):
currVol = min(height[i], height[j]) * (j - i)
maxVol = max(maxVol, currVol)
return maxVol
Optimised (Two Pointer):
----------------------------------------
class Solution:
def maxArea(self, height: List[int]) -> int:
maxVol = 0
n = len(height)
i = 0
j = n - 1
while i < j:
currVol = (j - i) * min(height[i], height[j])
maxVol = max(maxVol, currVol)
if height[i] == height[j]:
i += 1
j -= 1
elif height[i] < height[j]:
i += 1
else:
j -= 1
return maxVol
It's sad I couldn't figure it out on my own.
The brute force solution is obvious, but the O(n) one seemed COMPLETELY impossible to me.
I don't even know what my problem was.
I thought I had to:
1. Pick any of the r and l pointers
2. Find the best next pole for the current situation and move a pointer to it.
The first step is already wrong. There's absolutely no reason to pick ANY pointer. You should pick the one that's at smaller height.
The second step is also wrong. I shouldn't have been so concerned with the best for current situation, 'cause at some point there could be no better poles to move to for my current situation even if there are two 999999 height poles in the middle.
But I still don't know how to find optimal algorithm. I don't know how to "see" it. It's not tangible for me YET.
But I'm only getting started!
My five cents: Since the width is always decreasing when you move the pointer, you can simply look for the next height which is taller than the current height, only that case gets a potential area increase. 🤓
For these types of problems, is there any pattern we could learn other than just using two pointers? This problems just seems like you either can figure out what you need to do or you don't figure it out and fail. Is there any recommendation, on how I could approach these types of two pointer problems and get better at them?
You don't need to check the area after moving the pointer every time, if you move the pointer for the lower height, and the height it moves to is even lower, you can keep moving it, as there's no way the area could be smaller, so you keep moving it until you find a height greater than the height you used for your previous area.
You also can use the mathematical ratio that defines whether the area will be larger with different heights, without directly computing the area, and only compute the area at the end.
That’s brilliant
Notice if the new height is smaller than the previous height, then we can skip that height.
def maxArea(self, height: List[int]) -> int:
res = 0
l, r = 0, len(height) - 1
preL, preR = 0, 0
while l < r:
if preL > height[l]:
l += 1
continue
if preR > height[r]:
r -= 1
continue
area = (r - l) * min(height[l], height[r])
res = max(res, area)
if height[l] < height[r]:
preL = height[l]
l += 1
else:
preR = height[r]
r -= 1
return res
Super proud of myself for solving this one on my own! This was really tough
You are changing my mind I start think on your way
We could further optimize it by keeping track of the current left max and right max, dont do any calculation if new left or new right is smaller than the cur left or right max
This is incredible youtube channel with such incredible videos. I have been thinking on this problem for a week, I actually knew your video but I wanted to get right point myself. My only mistake was I have been moving pointers when new maximum result is bigger than previous one but now I saw your technique and I say myself why I didn't watch video earlier. Your channel helps me lot, thank you very much!! Keep up this good work!
One extra step we can take is instead of moving a pointer just one step, we can keep moving it until it finds a height greater than the one it left (or reaches the end condition, in which case there is no greater volume). The only way a volume can be greater than the current volume is if the height of the container is taller. If it's shorter or even the same height, the volume will be less since the width has shrunk. In practice, this allows us to check the volume at only three points, the (0,8) pair (first and last lines), the (1,8) pair (the actual solution, whose volume is 49), and the (1,6) pair (whose volume is 40). This solution passes all of LeetCode's test cases.
Thanks for your kind video. :) now I can solve the problem.
I have managed to learn how you approach problems and tried my hands on this problem and was able to solve the first try. Thank you so much for these videos, mean a lot!
What if the 3rd of the 4 bars between the 8s... is a 9? Then, the "L and R same size edge case" arbitrary choice of always shifting the left does matter, right? Because, imagine we're on 8L and 8R: If we shift left we only ever see 9L to 8R, right which is 8x2. If we shifted the right however we would see 8L and 9R, which is 8x3
I could not figure it out, but after watching this video solution. It turns out that the solution was actually pretty simple and easy to understand, I makes me wonder why I could not think of it.
When the left and right pointer have equal heights, it is important to check the neighbors of each and move to the largest number.
Actually it doesn't matter. If you think about it, you will not get a container bigger than the one with equal heights unless there exist two or more bigger heights WITHIN those positions. If you had an array of [8, 1, 5000, 2, 8], your biggest container is the one containing 8 and 8. Say you had an array of [8, 5, 50, 100, 2, 8]. The code will always end up checking the bigger heights so it will calculate and compare the area of the 50 and 100 position whether you move the left or right pointer first. You can always try it out, when the pointers have equal heights, write code to move the left pointer and then write code to move the right pointer. You will see you get the same results.
@@gregoryvan9474 thank you so much!
@@gregoryvan9474 This makes a lot of sense thanks
at last this concept actually made sense xd!@@gregoryvan9474
My first medium problem that i think i was able to solve by myself
Perfectly explained. Only had to watch once to completely understand what is going on which never happens lol
i couldn't even understand the question itself cuz it was so unnecessarily unclear but I do now, Thank you neetcode
Great video! Could u explain a bit more why when it comes to the result that left and right have the same value, why it doesn’t matter to move either left or right?
Turns out you can actually move the left *and* the right pointer at the same time when the heights are equal, which is why it doesn't matter which one you pick.
The reason why you can move both is because the goal of moving the left or right pointer is to increase min(height[l], height[r])* and if height[l] == height[r], then both height[l] and height[r] are equal to the minimum (let's call it m). Since min(something_else, m) can't be greater than m, we have to change both values if we want min(min(height[new_l], height[new_r])) to increase.
*technically, we're trying to increase the volume of the container, which is width*m, but since width is always decreasing when we move our pointers inward we need m to increase.
@@nilsh5027 I'm not convinced by your explanation. We can check whether right of left and left of right is greater or smaller. For example, here there is 6 and 4. We must choose 6 as an left and decrease from right. So area will get increased. If condition again ties we can use recursion.
Thank you. I understood the algorithm at 6:55
Wouldnt your brute force solution get an error because the last value of r will be l + 1 and l is the last index of the list?
Good question :
Simple answer would be try to run this code
for x in range (3,2):
print(True)
The loop will not run at all because as defined above loop will run until the value is less than 2 but our initial value is 3 there
I guess instead of comparing heights of left and right, you could compare the height of left to min(height[l], height[r]). If the height of left is equal to min(height[l], height[r]), you would increment the left pointer because it is the bottleneck. Else, decrement the right pointer because that is the bottleneck. Otherwise, I did the same thing.
Area is L x W. To maximize it you need to maximize both L and W. Since our left and right pointers begin at the leftmost and rightmost, W is always maximized. Now we have to maximize L. Our max L will always be the larger of the two pointers so we move the smaller of the two to keep L maximized.
im starting to get the same exact solution before even watching the video. neetcode is the goat
I don't understand how can he be sooo good in solving leetcode questions
This is my 45th question which i solved and am comfortable with medium array question now still struggling with hard but the point is if your channel didn't exist learning wouldn't have been so easy for me really thanks man keep going.
Did you solve just by seeing question or after watching approach
Ive watched all your videos for all your neetcode150 and really amazing stuff. I didn't know where to post this but I just have one thing I needed to point out. the solutions coded in python are great, but who ever was in charge of posting the solutions in javascript did a beyond awful job. im talking like truly truly horrible, to the point it would get me extremely frustrated as an interviewer to see a candidate write code that way. The person rights drastically more than needed, and while sometimes thats good if it makes the code more readable, the opposite actually is true. a 7 line solution in python for some reason has several different functions in javascript that are a mess and confusing to follow.
Im honestly happy to redo the javascript solutions for you, but wanted to at least call it your attention. whoever did it, did a really awful job.
anyways your explanations are top notch. thank you.
As the list of bars are not sorted we can not be sure that about moving left or right pointer will be give us optimal answer by just looking at left and right . Correct me if am wrong.
bump. I still don't understand how current height informs future potential.
Did you figure it out?
@@PippyPappyPatterson also not sure why we decide based on the current min of the pair, rather than the values they would have if we moved either one
i think after several arrays problem, one has picked up the two pointers technique. but for this particular problem, all the signs like big array input that requires faster running time that O(n^2) and the max product is based on multiplication of two numbers in the array requires retrieval of two numbers in an array hints at using the two pointers technique even more
Truly the OG in LeetCode problems
Is it worth keep updating the pointer until we get the height that is larger than current one? left = height[l] right = height[r] if left
I am quite annoyed by the fact that I was able to come up with the optimal solution for this problem, but still couldn't quite explain if this would be correct for all cases, and after watching your video I still can't explain why this works for all valid cases
Can someone help me with this?
class Solution {
public:
int maxArea(vector& height) {
int ptr1 = 0 ;
int ptr2 = height.size() -1;
int best = 0 ;
while(ptr1< ptr2)
{
best = max(best , (ptr2-ptr1)*min(height[ptr1],height[ptr2]));
if(height[ptr2] > height[ptr1])ptr1++;
else ptr2--;
}
return best;
}
};
I just wasted two hours doing the brute force solution. I always do it first as it gives me a clearer idea on what is going on. The problem is that I didn't understand why 8 * 8 wasn't the answer... I had to reread the problem like a thousand times.
I still don't understand how with the pointer solution, you are guaranteed to pass through the maximum area case?
Instead of going through every possible combination, the two pointer approach tries to maximize some aspect of the problem... In this case, we must maximize the width between two columns, moving right or left the column with smallest height, and keeping track of the container's max area along the way.
Yes, you are guaranteed. But it's far from obvious IMO.
I always felt daunted by the problem, but its actually quite easy
My good,, i was literally suffering from the solution of other youtubers,now understood crystal clearly.❤❤
Thanks for always making us better at algorithm thinking! The linear algorithm is similar to the Valid palindrome Two pointer solution we used, right?
I solved this problem on my own after you explanation. Thank you so much.
how can he so smoothly explain :0
When left and right are equal we can check whether right of left and left of right is greater or smaller. For example, here there is 6 and 4. We must choose 6 as an left and decrease from right. So area will get increased. If condition again ties we can use recursion.
Thank you for a clear explanation and also showing brute force and an optimized version.
Small Optimization - If both the bars have same height do l++ and r-- .
Reason - suppose array contains all the bars or some bars of same size so by doing l++ and r-- will take half iterations.
actually, when we move pointers we don't need to check for max water numbers, that a lower then current. it will not be possible to bigger square
is next number is same or lower.
thank you for the great and clear explaination!
Thanks, happy it was helpful
By seeing the problem statement, i taught solution will be very difficult , but the way you explained now i can feel problem was very simple and easier to solve
Thanks for explanining in simpler way
One day, after I’ve gotten into FAANG, I’ll come back to all of this
i wish i could give you a hug for making these videos
Everytime, we are moving our pointer i ahead if height of line at ith index is smaller or j pointer if height of line at jth index is smaller. This means whichever line is smaller, we won’t consider it again, because, this line could be the answer only if the other line is larger than it and at maximum width and to be noticed that this is the time when other line is larger as well as max distance apart. So, not considering it makes sense.
Dude I totally over thought about this one and wrote a mountain of code going from middle to left and right then jimmyfitted the last test case
What is the thinking pattern to come up with such solutions? I figured two pointer technique but couldn't figure out what condition to set to move the pointers. I have been bugging my mind whole day :(
Amazing explanations in all of your videos. This particular problem was so much clear with your video. Keep up the good work. That is awesome!!
Thanks 😊
Hi, regarding the edge case where height[left]==height[right], why does it not matter which pointer is being moved?
I'm also having a bit of trouble understanding this
@@tonynguyen6124 i thought about it and figured that it won't matter as if left/right pointer moves and reaches a higher point, its current volume would be less than the global max volume of water. And upon reaching a higher point, the opposite pointer will be the next to traverse, so it really doesn't matter.
Let me know if my explanation is sound haha
ok but i have a question. I wrote the same code but with a for look in the range(len(heights)) and it ran much faster than your code. why does the while loop make it much slower? [for context, for loop runs faster than 96% of all pythons solutions, where as the while loop one runs faster than just 10%)
I love you neetcode, you're the best!
Th first thing tha5 came to mind is a left and right pointer and go in the direction with a variable for maximum determined by a max function
Thank you! Amazing explanation
thank you man, hope for you all the good. please keep helping us
I was going crazy trying to figure out where I was going wrong... until I realized I was computing the volume of a rectangular prism! Lol
I'm actually curious what program or accessory you use to get those nice see-through brush drawings on the screen. Care to share? Peace.
Great explanation, I was able to code it in Java both Brute Force and Two Pointer solution because of the easy to understand explanation.
Thanks for awesome work, man! I was initially slicing the target array by left and right pointers to get its' length, but when I saw your method of getting the area I realized how dumb my way was :)
top tier solution thanks!
Great video, I am trying to understand the difference between this problem and the 42.tapping rain water problem.
I tried this approach whereby I moved the pointers such as to maximise the area at each step, but I got wrong answer.
I don't understand why Neetcode's solution is mathematically guaranteed to work. The problem looks to be a greedy one, but maximising the area locally gave me wrong answer. Why does NeetCode's solution work?
My solution for reference:
class Solution {
public:
int getArea(int left_idx, int left_val, int right_idx, int right_val){
return min(left_val, right_val) * (right_idx - left_idx);
}
int maxArea(vector& height) {
int left_idx = 0;
int right_idx = height.size()-1;
int max_area = -1;
while(left_idx max_area){
max_area = curr_area;
}
if (left_idx == right_idx){
break;
}
// let us try to decide which pointer to move
int left_move_area = getArea(left_idx+1, height[left_idx+1], right_idx, height[right_idx]);
int right_move_area = getArea(left_idx, height[left_idx], right_idx-1, height[right_idx-1]);
if(left_move_area >= right_move_area){
left_idx++;
}
else{
right_idx--;
}
}
return max_area;
}
};
EDIT: I saw a reply by @hunterlee1249. It makes sense now.
really helpfull and the explanation is too good thank you ....
Is this an edge case that doesnt work? The most left height is lets say 9, the second index is 100, everything else is 8. How would you get the output to be 100 and the most right 8
The output wouldn't be 100, since the minimum height of either side of the container is the bottleneck. In this case the output should be 8 * n where n is the size of the array