Container with Most Water - Leetcode 11 - Python
VloĆŸit
- Äas pĆidĂĄn 26. 07. 2024
- đ neetcode.io/ - A better way to prepare for Coding Interviews
đŠ Twitter: / neetcode1
đ„· Discord: / discord
đź Support the channel: / neetcode
Coding Solutions: âą Coding Interview Solut...
Problem Link: neetcode.io/problems/max-wate...
0:00 - Brute Force
5:25 - Optimal Solution
9:30 - Coding Optimal Solution
Leetcode 11
#CodingInterview #leetcode #neetcode
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission. - VÄda a technologie
![The moment we stopped understanding AI [AlexNet]](/img/n.gif)
đ 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!
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 CZcamsrs 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.
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
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!!!
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!
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!
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!
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 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 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.
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?
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 hope to get better at solving problems like you do! keep up! I love your content and explanations
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.
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!
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.
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 đ
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!!
Thank you for starting with brute force approach. This is how all CZcams videos should be. Discuss various approaches, evolution and trade offs.
Very clear and intuitive. Thanks for the work!
Thanks!
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 :)
Great explanation, I was able to code it in Java both Brute Force and Two Pointer solution because of the easy to understand explanation.
thank you man, hope for you all the good. please keep helping us
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
Thank you for the clear explanation. Great Job!
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.đ
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 đ
Brilliant as usual ) Thanks for suck an amazing explanations!
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 !
Thanks for your kind video. :) now I can solve the problem.
Thank you for a clear explanation and also showing brute force and an optimized version.
Awesome explanation. Very clear
Super proud of myself for solving this one on my own! This was really tough
Thanks for always making us better at algorithm thinking! The linear algorithm is similar to the Valid palindrome Two pointer solution we used, right?
Great video, I am trying to understand the difference between this problem and the 42.tapping rain water problem.
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?
Best explanation out there. Thank you!
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.
thank you for the great and clear explaination!
Thanks, happy it was helpful
top tier solution thanks!
Awesomely explained !! Please keep making videos like these.
Thanks, for sure!
Truly the OG in LeetCode problems
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
My good,, i was literally suffering from the solution of other youtubers,now understood crystal clearly.â€â€
I solved this problem on my own after you explanation. Thank you so much.
ÂĄExcelente explicaciĂłn!
Perfectly explained. Only had to watch once to completely understand what is going on which never happens lol
Hi NeetCode, thank you for the video, please don't stop :)
Thanks!
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.
Great video and explanation! Subscribed!
Thanks, appreciated =)
Thank you. I understood the algorithm at 6:55
im starting to get the same exact solution before even watching the video. neetcode is the goat
Thank you! Amazing explanation
This was so good , thank you.
Thanks! Glad it was helpful!
Ugh, I hate that I need to look up some of these solutions, feels like I've been defeated :( Thanks though lol.
Same here
Dude you are amazing! Thank you so much đ„°
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 love you neetcode, you're the best!
awesome stuff man!
You are changing my mind I start think on your way
Yo this was soo good! Thank you !!
Lol but the bruteforce method was accepted on my leetcode. I guess i should learn both though just incase.
I always felt daunted by the problem, but its actually quite easy
i couldn't even understand the question itself cuz it was so unnecessarily unclear but I do now, Thank you neetcode
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.
great explanation!!!!
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
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
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?
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 don't understand how can he be sooo good in solving leetcode questions
really helpfull and the explanation is too good thank you ....
great explanation
Thank you so much dude...
i wish i could give you a hug for making these videos
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!
Good job bro!
best explained!
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.
Thank you for your video! May I know the space complexity for the optimal solution?
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
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.
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 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?
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
Thank you!
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
Thanks a lot!
Thanks bro, liked
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
Amazing, easy!
Awesome man
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.
Thanks my guy!
Damn this took me some effort to understand!