Container with most water
We'll cover the following
Each number is a wall height. Pick two walls so the container between them holds the most water.
Watch it run
Press Play or Step to walk through the example, or change the input and press Run. Each frame says what the algorithm does and why.
L40
81
62
83
104
65
96
57
78
89
610
411
312
113
114
R1015
Water held is min(4, 10) × width 15 = 60. Move the shorter side (L) inward, because moving the taller one cannot help.
area 60 · best 60
1 / 16
The idea
Complexity
| Time | Space | Why |
|---|---|---|
O(n) | O(1) | The pointers meet after n - 1 moves. |
In Python
def max_area(h):
l, r, best = 0, len(h) - 1, 0
while l < r:
best = max(best, min(h[l], h[r]) * (r - l))
if h[l] <= h[r]: l += 1
else: r -= 1
return bestSummary: say it in the interview
- Start with the widest container. Water is limited by the shorter wall, so the only way to improve is to move the shorter wall inward and hope for a taller one.
- Time O(n), space O(1). The pointers meet after n - 1 moves.