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?
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 RU-vidrs 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.
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.
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!
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).
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!!!
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.
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 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!
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?
For those that would like to see __why__ this algorithm works, here's a condensed mathematical explanation. - For i < j, let area(i, j) = (j - i) * min(h[i], h[j]). Note that h[i] is shorthand for height[i]. - For i < j, let OPT(i, j) be the maximum area that can be achieved by choosing any 2 lines inside the set {i, i+1, ..., j-1, j}. Note that the problem essentially asks us to calculate OPT(0, n-1). Also note that OPT(i, i) = 0 (base case for container of 0 width). Our goal is to prove the following formula for i < j: OPT(i, j) = { max( area(i, j), OPT(i+1, j) ), if h[i]
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 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?
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
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.
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.
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
I've started to develop intuition, thanks First used to try solving stuff, then come back to see better approaches Kept doing this for like 50-60 days, now I can do these easylevel mediums on my own, thanks !
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.
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.
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.😀
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
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?
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!
@@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 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!
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?
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
15 дней назад
the key "a-ha" moment here on why the two pointer approach works is: there's two variables at play, the width and the height. You can maximize the width easily by doing left=0, right=len(arr)-1. Then you maximize the height by always replacing the smallest wall.
I think there's a more intuitive way (at least for me) to explain the move of two pointers: we wanna see if we can get a larger capacity by sacrifying the width and getting the container higher. So we keep moving the pointer of lower sides.
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.
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.
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.
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. 🤓
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
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
The way I thought about it was that width will decrease on every iteration so the main focus should be maximizing the height, so you should always move the pointer from smaller height between the two.
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!
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.
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
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.
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 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.
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.
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.
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
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 :)
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 :(
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.
The width always decreases as the pointers move inward, which cannot be controlled. To maximize the area, the focus should be on increasing the shorter height. If the taller pointer is moved, the area cannot improve because the shorter height either remains the same or decreases. If the shorter pointer is moved, there is a chance of finding a taller line, resulting in a larger area.
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.
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.
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.
Thank you for the explanation! But how can you prove that moving the lower verticle line pointer is GUARANTEED to find the max area? The rationale, "the limitation is the lower line", is intuitive and appealing, but how do we know the algorithm does not miss the max area?
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%)
Hey I have been trying to practice these for sometime now, wanted to check do we get these kind of solutions on one go? Like how much time do we spend on questions till we get a solution like this? The solution seems so elegant, but how do you even come up with this in first go?
