Container With Most Water
Problem statement
Statement
Given an integer array height where height[i] represents the height of a vertical line at index i, find two lines that together with the x-axis form a container holding the most water. Return the maximum amount of water the container can store.
Examples
height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
→ 49 (indices 1 and 8, heights 8 and 7, width 7 → min(8,7) × 7 = 49)
height = [1, 1]
→ 1 (single rectangle of width 1 and height 1)
height = [4, 3, 2, 1, 4]
→ 16 (indices 0 and 4, both height 4, width 4)Constraints
2 ≤ len(height) ≤ 10⁵0 ≤ height[i] ≤ 10⁴- You cannot tilt the container; the water level is bounded by the shorter line.
What this problem is really testing
Whether you can spot a two-pointer optimisation that beats the obvious O(n²) brute force. The trick is that at every step, advancing the shorter side is the only direction that could improve the answer, shrinking the width while keeping the shorter height fixed can only decrease the area. That insight turns a quadratic algorithm into a linear one.
Hints
Hints
- Brute force. Try every pair of indices. For each (i, j), area is
min(height[i], height[j]) × (j - i). Take the max. O(n²), works but doesn't scale to n = 10⁵. - The two-pointer setup. Place
iat index 0,jat index n − 1. The initial width is maximum (n − 1). - Which pointer to move? Compute the current area. To improve it, you must either find a wider container (impossible, the pointers can only converge) or find a taller minimum height. The only way to grow the minimum is to advance the shorter side and hope the new height is larger.
- Why advancing the taller side is wasted. Width decreases by 1. The minimum height stays the same (still bounded by the shorter side, which didn't move). So the new area is strictly smaller. Always advance the shorter side.
- What about ties? When both heights are equal, advancing either side is safe (the symmetric argument holds for both).
- Termination. The loop runs while
i < j. Each step advances exactly one pointer; total iterations bounded by n.
Solution and approaches
Solution, two approaches
Approach 1 · Brute force. O(n²) time, O(1) space
def max_area_brute(height):
n = len(height)
best = 0
for i in range(n):
for j in range(i + 1, n):
best = max(best, min(height[i], height[j]) * (j - i))
return bestEnumerates every pair. Correct but quadratic, for n = 10⁵, this is 5 × 10⁹ operations. Too slow.
Approach 2 · Two pointers. O(n) time, O(1) space
def max_area(height):
i, j = 0, len(height) - 1
best = 0
while i < j:
h = min(height[i], height[j])
best = max(best, h * (j - i))
if height[i] < height[j]:
i += 1 # advance shorter side
else:
j -= 1 # advance shorter side (or tied)
return bestWhy advancing the shorter side is optimal
Claim: at every step, the maximum area among containers using the shorter side as one bound has been computed. So we can safely move past the shorter side.
Proof. Suppose height[i] < height[j] and we advance j instead of i. The new container has width j' - i = (j - 1) - i, smaller by 1. The minimum height is still bounded by height[i] (which didn't change) or possibly height[j'], whichever is smaller. In either case, the minimum height is at most height[i], the same as before. So the new area is bounded by height[i] × (j - 1 - i) < height[i] × (j - i). Strictly worse.
Therefore advancing the taller side never improves the answer. The only direction that could improve it is advancing the shorter side, where the new height might be larger. We do that; correctness preserved; loop runs at most n times.
A worked trace
height = [1, 8, 6, 2, 5, 4, 8, 3, 7]:
i=0, j=8: min(1, 7)=1, w=8, area=8, advance i (height[0]=1 < height[8]=7)
i=1, j=8: min(8, 7)=7, w=7, area=49, advance j (height[1]=8 > height[8]=7)
i=1, j=7: min(8, 3)=3, w=6, area=18, advance j
i=1, j=6: min(8, 8)=8, w=5, area=40, advance j (tied; either works)
i=1, j=5: min(8, 4)=4, w=4, area=16, advance j
i=1, j=4: min(8, 5)=5, w=3, area=15, advance j
i=1, j=3: min(8, 2)=2, w=2, area=4, advance j
i=1, j=2: min(8, 6)=6, w=1, area=6, advance j
i=1, j=1: loop ends
best = 49 ✓Complexity comparison
| Approach | Time | Space | Notes |
|---|---|---|---|
| Brute force | O(n²) | O(1) | TLE on n ≥ 10⁴ |
| Two pointers | O(n) | O(1) | Canonical answer |
Edge cases to verify
- Two-element array: the loop runs once; returns
min(h[0], h[1]) × 1. - All equal heights: answer = h × (n − 1); the initial pair is optimal.
- Strictly increasing: the optimal pair includes the last element. The two-pointer algorithm finds it by repeatedly advancing the left pointer (which is always shorter).
- Strictly decreasing: symmetric, the left pointer is always the taller; we repeatedly advance the right.
- Some zeros: a zero-height line contributes no area, but the algorithm doesn't need to special-case it,
min(0, anything) = 0.
Common mistakes
Where beginners go wrong
- Advancing the taller side. The most common error; produces wrong answers because it discards higher-area candidates without checking them. The proof above shows why this is always wrong; commit it to memory.
- Advancing both pointers per iteration. Skips pairs that might be optimal. Move exactly one per step.
- Mistaking the area formula. It's
min(h[i], h[j]) × (j − i), not the average, not the sum. The shorter side bounds the water level. - Trying to use prefix-max or sliding window. Neither fits, the problem isn't about contiguous subarrays and isn't bounded by a running maximum.
- Off-by-one in width.
j − iis the number of unit intervals between the pillars. If you accidentally usej − i + 1orj − i − 1, every answer is off.
Interview follow-ups to expect
- "What if 3-D, container in a grid?" Trapping Rain Water II. Use a min-heap seeded with the boundary cells; expand inward by lowest current cell. O(m × n × log(m × n)).
- "What if you can pick three pillars (triangular container)?" Harder, no longer a two-pointer problem. Convex-hull-like reasoning required.
- "Trapping Rain Water, total trapped between bars." Same two-pointer pattern with a running max on each side. See the converging-pointers deep-dive.
- "What if heights can change over time?" Stream-friendly: maintain a stack of decreasing heights; pop when a higher bar arrives. O(n) total.
- "Stretch the problem to weighted indices." If the x-axis is irregular (positions instead of 0..n-1), the width becomes
x[j] − x[i]. The two-pointer algorithm still works; only the width computation changes.
Related reading
- Converging Pointers (The Correctness Proof) formal treatment of the two-pointer pattern.
- Two Pointers & Sliding Window, the broader module.