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.
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!
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!!!
" It has been a long time goal of mine to become a better programmer through practicing leetcode questions" I understand your emotion, but those things are not related. You just understand patterns through DSA. You'll hardly come across anything of leetcode useful in your work. Except you learn the DS usage of your language API's better. Most people who excel at leetcode sucks when they face actual company work, and they are not able to make peace with it. It doesn't let them sleep well, because all of this they learnt for nothing useful for career progression, while constantly getting hammered with problems they have no idea how to solve for which they are being hired. Most oldies and seasoned programmer who know very little of leetcode, are top performers of the companies. Don't want to discourage, even I'm learning, but just for cracking those damn interviews. I cracked the system design round of FB with flying colours, because I'm seasoned, but couldn't on 1 leetcode round. The recruiters told me, mostly they see people with opposite, they crack the leetcode stuff but suck at system design. But then once you are hired, you won't solve leetcode, so beware.
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 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!
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!
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).
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?
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.
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 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'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 !
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!
I have been doing Leet and NeetCode for quite some time now, and have been using the spaced repetition technique NeetCode talked about. This is the first good medium level leetcode problem I could solve completely on my own, I just knew I had to use left and right pointer because its in that section on the website, and damn it got me pumped. Leetcode has devasted me so many times, but this one problem solving on my own gave me a huge dopamine boost.
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.
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
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 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!
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.
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?
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
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
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.
Super proud of myself for solving this one on my own! This was really tough
3 หลายเดือนก่อน
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.
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.
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.
@@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.
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?
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.
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 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.
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. 🤓
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.
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.
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
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.
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.
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.
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
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.
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.
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.
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.
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.
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 :)
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!
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.
🚀 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.
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! 🙂
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!!!
" It has been a long time goal of mine to become a better programmer through practicing leetcode questions"
I understand your emotion, but those things are not related.
You just understand patterns through DSA.
You'll hardly come across anything of leetcode useful in your work.
Except you learn the DS usage of your language API's better.
Most people who excel at leetcode sucks when they face actual company work, and they are not able to make peace with it. It doesn't let them sleep well, because all of this they learnt for nothing useful for career progression, while constantly getting hammered with problems they have no idea how to solve for which they are being hired.
Most oldies and seasoned programmer who know very little of leetcode, are top performers of the companies.
Don't want to discourage, even I'm learning, but just for cracking those damn interviews.
I cracked the system design round of FB with flying colours, because I'm seasoned, but couldn't on 1 leetcode round. The recruiters told me, mostly they see people with opposite, they crack the leetcode stuff but suck at system design. But then once you are hired, you won't solve leetcode, so beware.
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!!
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.
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!
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!
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.
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?
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 😃
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.
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 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 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'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 hope to get better at solving problems like you do! keep up! I love your content and explanations
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!
I have been doing Leet and NeetCode for quite some time now, and have been using the spaced repetition technique NeetCode talked about. This is the first good medium level leetcode problem I could solve completely on my own, I just knew I had to use left and right pointer because its in that section on the website, and damn it got me pumped. Leetcode has devasted me so many times, but this one problem solving on my own gave me a huge dopamine boost.
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.
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
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 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!
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.
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?
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
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
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.
Super proud of myself for solving this one on my own! This was really tough
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.
Thanks for your kind video. :) now I can solve the problem.
This is more optimized moving of pointers:
h is min of values at left and right
while (left < right && height[left]
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
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.
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
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 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 !
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 are changing my mind I start think on your way
i couldn't even understand the question itself cuz it was so unnecessarily unclear but I do now, Thank you neetcode
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.
Truly the OG in LeetCode problems
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 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.
My good,, i was literally suffering from the solution of other youtubers,now understood crystal clearly.❤❤
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. 🤓
Thank you. I understood the algorithm at 6:55
Perfectly explained. Only had to watch once to completely understand what is going on which never happens lol
Thank you for a clear explanation and also showing brute force and an optimized version.
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
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
I’m so happy that I got to the same result without googling the answer or using hints! Practicing is giving me results woohoooo
I solved this problem on my own after you explanation. Thank you so much.
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.
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
im starting to get the same exact solution before even watching the video. neetcode is the goat
thank you for the great and clear explaination!
Thanks, happy it was helpful
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.
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.
Thanks for always making us better at algorithm thinking! The linear algorithm is similar to the Valid palindrome Two pointer solution we used, right?
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
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 always felt daunted by the problem, but its actually quite easy
Great explanation, I was able to code it in Java both Brute Force and Two Pointer solution because of the easy to understand explanation.
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 😊
My first medium problem that i think i was able to solve by myself
Ugh, I hate that I need to look up some of these solutions, feels like I've been defeated :( Thanks though lol.
Same here
Thank you for the clear explanation. Great Job!
Best explanation out there. Thank you!
I don't understand how can he be sooo good in solving leetcode questions
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.
Great video, I am trying to understand the difference between this problem and the 42.tapping rain water problem.
Thank you! Amazing explanation
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.
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.
i wish i could give you a hug for making these videos
really helpfull and the explanation is too good thank you ....
thank you man, hope for you all the good. please keep helping us
Awesomely explained !! Please keep making videos like these.
Thanks, for sure!
I love you neetcode, you're the 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.
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.
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 :)
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!
Great video and explanation! Subscribed!
Thanks, appreciated =)
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;
}
};
Hi NeetCode, thank you for the video, please don't stop :)
Thanks!
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
Awesome explanation. Very clear
top tier solution thanks!
This was so good , thank you.
Thanks! Glad it was helpful!
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
Brilliant as usual ) Thanks for suck an amazing explanations!
how can he so smoothly explain :0