Container With Most Water is a classic two-pointer problem. It looks like it needs you to test every pair of walls, but a single sweep from both ends solves it in linear time — once you spot which wall to move.
Problem. You are given an array height where each value is the height of a vertical line at that
index. Pick two lines that, together with the x-axis, form a container. Return the most water it
can hold. The water area is min(left, right) × distance between them — the shorter wall caps the height.
Example: height = [1, 8, 6, 2, 5, 4, 8, 3, 7] → answer 49 (the two walls of height 8 at indices 1 and
6 hold min(8, 8) × (6 − 1) = 8 × 5 = 40… but the walls at index 1 and 8 hold min(8, 7) × 7 = 49, which
is larger).
The idea
The brute force is to try every pair of walls and keep the biggest area. That is O(n²) — too slow for a large array.
Instead, put one pointer lo at the far left and one pointer hi at the far right. This is the widest possible container. Its area is min(height[lo], height[hi]) × (hi − lo).
Now the key insight: the water height is limited by the shorter wall. If we move the taller wall inward, the width shrinks and the height is still capped by that same short wall — the area can only get worse. So we always move the shorter wall inward, hoping to find a taller one. Each move throws away exactly one wall that could never have done better.
Walk through it
Step through the animation. The pointers lo and hi start at the two ends. Each step prints the area and the running best underneath. Watch how we always advance the shorter side: when lo reaches the height-8 wall, the right side becomes the short one, so hi does all the moving after that. The best area, 49, is found early and never beaten.
Pseudocode
best = 0
lo = 0, hi = last index
while lo < hi:
area = min(height[lo], height[hi]) * (hi - lo)
best = max(best, area)
if height[lo] < height[hi]:
lo += 1 # left wall is shorter, move it
else:
hi -= 1 # right wall is shorter (or equal), move it
return bestEach turn of the loop moves exactly one pointer inward, so the two pointers meet after n − 1 steps. That is a single linear pass.
The Python solution
def max_area(height):
best = 0
lo, hi = 0, len(height) - 1
while lo < hi:
area = min(height[lo], height[hi]) * (hi - lo)
best = max(best, area)
if height[lo] < height[hi]:
lo += 1
else:
hi -= 1
return bestloandhistart at the two ends — the widest container.areauses the shorter wall as the height and the gap between the pointers as the width.best = max(best, area)keeps the largest area we have seen.- Lines 7–10 are the heart of the algorithm: compare the two walls and move the shorter one inward. Moving the taller one could never beat the current area, so we skip it.
- The loop ends when the pointers meet, and we return
best.
Complexity
| Case | Time | Notes |
|---|---|---|
| Brute force (every pair) | O(n²) (slow) | two nested loops |
| Two pointers (this solution) | O(n) (moderate) | each pointer moves inward once |
O(1) (fast)We use only two index variables and a running best — O(1) extra space — and a single pass. The whole trick is realizing that the shorter wall is always the safe one to discard.
When this pattern shows up
When an array problem asks for the best pair from both ends — max area, a target pair in a sorted array, trapping rain water, the closest pair — reach for two pointers walking inward. The skill is arguing which pointer is safe to move so you never miss the answer.
Always move the shorter wall, not the left one by default. If you move the taller wall, you shrink the width while the short wall still caps the height — you can only lose area, and you might skip the real answer.
Practice
The pointers are at lo (height 8) and hi (height 7), with width 7. The area is 49. Which pointer moves next, and why?
1. Why do we always move the pointer at the shorter wall?
2. What is the water area formula for two walls at indices lo and hi?
3. Why is the two-pointer solution O(n) instead of O(n²)?
4. What is the extra space used by this solution?