Container With Most Water

Medium#11towards each other

You get the heights of walls that stand in a row, one step apart. Pick two of them so that the most water fits between them: the distance between the walls times the lower one. Our example: heights [2, 6, 3, 5, 1, 4, 7, 3] — the answer is 30, the walls 6 and 7.

11 Container With Most WaterWalkthrough · 1×

Example: heights [2, 6, 3, 5, 1, 4, 7, 3]. Blue is the water between the two walls, the dashed frame is the best container so far.

2061325314457637left
the two wallsruled outthe best pair

left starts at the first wall, 2 high

01/47
restart · back · play · step
Speed
1function maxArea(height):
2 left = 0
3 right = len(height) - 1
4 best = 0
5 while left < right:
6 low = min(height[left], height[right])
7 area = (right - left) * low
8 best = max(best, area)
9 if height[left] < height[right]:
10 left = left + 1
11 else:
12 right = right - 1
13 return best
state
left
0
right
–
low
–
area
–
best
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. Start with the widest container: the two end walls. Every later one is narrower, so it can only win by being higher.
  2. Water rises only to the lower wall. Moving the higher wall is pointless: the width drops and the height cannot grow past the lower wall. So the lower wall moves.
  3. Each move drops a wall together with every container it could still make, and none of them beats the one just measured. So the best container is never skipped.

Complexity

Time O(n): each step moves one wall inwards, so there are at most n − 1 steps. Memory O(1): two pointers and the best area.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.