What is the Container With Most Water Problem?
Learn the two-pointer solution to container with most water, why it works, and how to explain the O(n) approach in interviews.
Expected Interview Answer
The container with most water problem finds two vertical lines from an array of heights that, together with the x-axis, form the container holding the most water, solved optimally in O(n) time with a two-pointer approach starting at both ends of the array.
The container’s area is width times the shorter of the two chosen lines’ heights, since water spills over the shorter side. Start with pointers at the leftmost and rightmost lines, giving the maximum possible width, and record that area. Then always move the pointer at the shorter line inward: keeping the shorter line and only shrinking width can never beat the current area, but moving the shorter line might find a taller line that increases the limiting height, which is the only way to potentially improve the result. Repeat until the pointers meet, tracking the maximum area seen. This greedy elimination is provably correct because moving the taller pointer instead can only ever decrease or keep the same area, so it is always safe to discard that option.
- O(n) time with a single pass, versus O(n^2) checking every pair
- O(1) extra space, just two pointers and a running maximum
- Provably correct greedy elimination of the taller line at each step
- Same two-pointer pattern generalizes to trapping rain water and pair-sum problems
AI Mentor Explanation
Groundstaff are testing which two boundary flags, if connected by a tarp, would hold the most rainwater between them, where the tarp sags to the height of the shorter flag. Starting with the two flags at opposite ends of the ground gives the widest possible tarp, so that area is recorded first. Then the crew always moves in from whichever flag is shorter, because keeping it and shrinking the width can never hold more water, while moving it might find a taller flag that raises the limiting height. This process of always discarding the shorter flag’s position and stepping inward finds the best pair of flags in a single sweep across the ground.
Step-by-Step Explanation
Step 1
Set two pointers at the extremes
Start with left at index 0 and right at the last index, giving the maximum possible width.
Step 2
Compute and record the current area
Area = width * min(height[left], height[right]); update the running maximum.
Step 3
Move the shorter pointer inward
Advance whichever side is shorter, since keeping it and shrinking width cannot improve the area.
Step 4
Repeat until pointers meet
Continue narrowing and recomputing the area until left and right converge.
What Interviewer Expects
- Correctly state that area is bounded by the shorter of the two chosen lines
- Justify why moving the taller pointer instead is never beneficial (the proof of correctness)
- Give O(n) time and O(1) space, compared to O(n^2) brute force over all pairs
- Recognize the two-pointer pattern’s similarity to trapping rain water
Common Mistakes
- Moving the taller pointer instead of the shorter one, breaking correctness
- Using max instead of min of the two heights when computing area
- Forgetting to update the running maximum area on every iteration, not just at the end
- Assuming a brute-force O(n^2) double loop is required without knowing the two-pointer trick
Best Answer (HR Friendly)
“This problem asks which two lines from an array of heights would hold the most water between them, where the water is limited by the shorter of the two lines. I use two pointers starting at both ends and always move the shorter one inward, since keeping the shorter line while narrowing the width can never help, but moving it might find a taller line instead.”
Code Example
def max_area(heights):
left, right = 0, len(heights) - 1
best = 0
while left < right:
width = right - left
shorter = min(heights[left], heights[right])
best = max(best, width * shorter)
if heights[left] < heights[right]:
left += 1
else:
right -= 1
return bestFollow-up Questions
- Why is it always correct to move the shorter pointer, never the taller one?
- How does this problem relate to trapping rain water?
- What is the brute-force time complexity, and why is it worse?
- How would you handle an input array with fewer than two elements?
MCQ Practice
1. What is the area formula used for a given pair of lines in this problem?
Water is capped by the shorter of the two lines, so area is width times the minimum of the two heights.
2. When the two pointers are at unequal heights, which pointer should move?
Moving the shorter line is the only move that could possibly find a taller line and improve the limiting height.
3. What is the time complexity of the two-pointer solution?
The two pointers each move at most n times total, giving a single linear pass over the array.
Flash Cards
How is area computed in container with most water? — width * min(height[left], height[right]).
Which pointer should move at each step? — The pointer at the shorter of the two current lines.
What is the time complexity of the two-pointer approach? — O(n), a single pass with two pointers.
Why is moving the taller pointer never beneficial? — It can only keep the same or a smaller limiting height while the width shrinks, so it cannot improve the area.