Algorithm

Container With Most Water

Two Pointer Pattern

Container With Most Water

You are given an integer array height of length n, where height[i] is the height of a vertical line drawn at position i. Pick two of these lines; together with the x-axis they form a container. The water it holds is (distance between the two lines) × (the shorter of the two line heights). Return the maximum amount of water any such container can hold. You return the area only, not which two lines produced it.

CONSTRAINTS
  • n == height.length
  • 2 <= n <= 10⁵
  • 0 <= height[i] <= 10⁴
EXAMPLE 1
Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
The lines at positions 1 and 8 are 7 apart with heights 8 and 7; water = 7 × min(8,7) = 49, the largest possible.
EXAMPLE 2
Input: height = [1,1]
Output: 1
The only container is width 1 with both walls height 1, holding 1 × min(1,1) = 1.
EXAMPLE 3
Input: height = [4,3,2,1,4]
Output: 16
The two outer walls (height 4) are 4 apart: 4 × min(4,4) = 16. Width matters as much as height.
Can heights be zero?
Yes. A wall of height 0 holds no water, so any container using it has area 0.
Do I return the area or the two lines that make it?
Just the maximum area.
Does the water pour over the taller wall?
Yes — the container is limited by the shorter of the two walls, so the height factor is min(height[left], height[right]).
Is the array sorted?
No. Unlike the sorted-sum problems, this works on the raw array because the discard rule comes from the shorter wall, not from order.

We choose two vertical lines and pour water between them. The amount held is width times height, where width is how far apart the lines are and height is the shorter of the two — water spills over the lower wall, so the lower wall sets the level. We want the biggest such amount over all pairs of lines.

The blunt way: try every pair

Check all pairs (i, j), compute (j - i) * min(height[i], height[j]) for each, keep the largest. That is two nested loops, about N²/2 pairs, so O(N²) — too slow when n reaches 100,000.

python
best = 0
for i in range(len(height)):
    for j in range(i + 1, len(height)):
        best = max(best, (j - i) * min(height[i], height[j]))
return best
Start as wide as possible, then give up the weak wall

This is the converging walk again, but the decision rule is new — and it is the interesting part. Put left on the first line and right on the last, the widest container there is. Measure its water. Now we must move one of the two pointers inward, which will shrink the width. Which one should we sacrifice?

Here is the key observation. The water is capped by the shorter wall. Say the left wall is the shorter one. Moving the taller (right) wall inward is pointless: the width drops, and the height is still stuck at the short left wall — the water can only stay the same or get worse, never better. So the right wall can't help while the left wall is the bottleneck. The only move with any hope of a bigger container is to abandon the shorter wall and look for a taller one. So: always step the pointer on the shorter wall inward, and track the best area seen.

python
left, right = 0, len(height) - 1
best = 0
while left < right:
    best = max(best, (right - left) * min(height[left], height[right]))
    if height[left] < height[right]:
        left += 1                      # shorter wall on the left — drop it
    else:
        right -= 1                     # shorter (or tied) wall on the right — drop it
return best
Why abandoning the short wall loses nothing

It is worth proving we don't skip the real answer. Suppose the left wall is the shorter one right now. Consider every container that uses this left wall — it pairs with the current right wall, or some wall further left of right. All of those are narrower than the current one (right has moved in), and none can be taller than this same short left wall. So the widest container this short wall will ever appear in is the one we just measured. We have already recorded its best possible contribution; keeping the wall around can only waste steps. Discarding it is safe. Each step permanently drops one wall, so the two pointers meet after about N steps — one linear pass.

Crucial Notewhen the two walls are equal in height, it does not matter which one you move — moving either gives up a wall whose best (widest) container has already been measured, so both choices are safe.
Worked example:height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
- left=0 (1), right=8 (7). Area = 8 × min(1, 7) = 8. Left wall (1) is shorter — drop it, left→1.
- left=1 (8), right=8 (7). Area = 7 × min(8, 7) = 49. New best. Right wall (7) is shorter — drop it, right→7.
- The walk continues inward; no later container beats 49, because every remaining option is narrower and no taller than its short wall allows. Return 49.
What makes this one converging, and where it would break

Slot it into the template: (a) we read the area from the two ends; (b) we move whichever end holds the shorter wall; (c) we record the running maximum. Notice the enabling property is different from the sorted-sum problems — there is no sorting here. What lets us discard an end is that the objective is bottlenecked by the smaller of the two ends: because the short wall caps the water, we can prove the short wall's best container is the current, widest one. Recognizing that "the answer between two boundaries is limited by the weaker boundary" is the signal to try moving the weaker boundary inward. If the objective did not have that bottleneck shape — if, say, height added instead of capping — this exact discard argument would collapse and you would need a different tool. Same converging skeleton, a problem-specific reason for which end to drop.

Interactive Strategy Visualization

Fluid Intuition

Geometric Optimization Trace

L
R
1
0
8
1
6
2
2
3
5
4
4
5
8
6
3
7
7
8
WIDTH
8
MIN HEIGHT
1
CURRENT AREA
8
MAX AREA
8

Key Insight

Area is strictly limited by the shorter wall. Moving the taller wall only decreases width without any possibility of a taller bottleneck.

Strategy

Always move the pointer pointing to the shorter line. It is the only way to potentially find a taller line to offset the width reduction.

O(N²) Brute Force
O(N) Time · O(1) Space Converging Scan