Container with Most Water - Leetcode 11 - Python

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.

[hunterlee]

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.

[XShollaj]

Dont go any further guys - This is the best channel for leetcode solutions ; Neetcode - you are the leetcode king

[SahilMishra]

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.

[joeldev]

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!

[TaiNguyen-oqo]

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).

[ReArNiDcOM]

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!!!

[Apurvsankhyadhar]

amazing how you explain almost every code with such ease and such clarity

[kuoyulu]

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!

[branislav]

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?

[ashleyspianoprogress]

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!

[traviszito]

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).

[abhilashreddyvedavally]

This is the point 6:40 I was looking for in the optimal solution on how to move the pointers - Thanks for the explanation

[linli]

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.

[nikhilgoyal]

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).

[ManishJain]

Thank you for starting with brute force approach. This is how all YouTube videos should be. Discuss various approaches, evolution and trade offs.

[karimatef]

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

[RanjuRao]

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

[nishantingle]

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.

[Jsterman]

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.

[cnasir]

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.