Container With Most Water

Problem

You are given an integer array height where height[i] is the height of a vertical line drawn at x-coordinate i. Pick two of these lines; together with the x-axis they form an open-topped container. The water it can hold is limited by the shorter of the two lines:

area = (distance between the lines) * min(height of the two lines)

Return the maximum water any pair of lines can contain. The container must stay upright (lines cannot be tilted) and water above the shorter line spills out.

Examples

• height = [1,8,6,2,5,4,8,3,7] → 49 Lines at indices 1 and 8 (heights 8 and 7): width 8 - 1 = 7, limited by height 7 → 7 * 7 = 49.
• height = [1,1] → 1 Only one pair exists: width 1, height 1.
• height = [4,3,2,1,4] → 16 The two 4s at the ends: 4 * 4 = 16 beats every closer pair.

Constraints

• 2 <= height.length <= 10^5
• 0 <= height[i] <= 10^4
• With n = 10^5, checking all ~5 * 10^9 pairs is too slow — an O(n) or O(n log n) approach is required.

Think about it first

TL;DR

Converging two pointers, always moving the shorter line — O(n) time, O(1) space.

Approach 1 — Brute force: try every pair

Compute the area of all n(n-1)/2 pairs and keep the maximum.

def maxArea(height: list[int]) -> int:
    n = len(height)
    best = 0
    for i in range(n):
        for j in range(i + 1, n):
            area = (j - i) * min(height[i], height[j])
            if area > best:
                best = area
    return best

• Time: O(n^2) — about 5 * 10^9 pairs at n = 10^5.
• Space: O(1).

At n = 10^5 this is billions of evaluations, well past any time limit. A linear approach is required.

Approach 2 — Converging two pointers (greedy elimination)

Start with the widest container: pointers at both ends. Every other pair is narrower, so it can only win by being taller. The area is capped by the shorter line. Pairing that shorter line with any line further inward gives a smaller width and a height still bounded by the shorter line, so its area is ≤ the current pair. Every such pair is no better, so all of them are discarded at once by moving the shorter line’s pointer inward. Each step eliminates one line; after n - 1 steps every potentially-optimal pair has been covered.

This is a greedy algorithm — at each step a locally-justified choice (drop the shorter line) is proven never to discard the global optimum.

def maxArea(height: list[int]) -> int:
    left, right = 0, len(height) - 1
    best = 0
    while left < right:
        width = right - left
        if height[left] <= height[right]:
            best = max(best, width * height[left])
            left += 1
        else:
            best = max(best, width * height[right])
            right -= 1
    return best

flowchart TD
    A[left = 0, right = n - 1, best = 0] --> B{left < right?}
    B -- no --> F[return best]
    B -- yes --> C[width = right - left]
    C --> D{height at left <= height at right?}
    D -- yes --> E[best = max with width * height at left, then left += 1]
    D -- no --> G[best = max with width * height at right, then right -= 1]
    E --> B
    G --> B

Walkthrough on height = [1,8,6,2,5,4,8,3,7]:

Return 49 — found at step 2 and never beaten, exactly the pair (1, 8) from the example.

On a tie (height[left] == height[right], as at indices 1 and 6 above) moving either pointer is safe: the current pair’s area is recorded first, and any strictly better pair must be strictly inside both, which the continued sweep still reaches.

• Time: O(n) — each iteration retires one index for good.
• Space: O(1).

Why not other classics?

There is no meaningful third approach here: sorting destroys the width information the area depends on, and divide-and-conquer or DP add nothing because the greedy exchange argument already yields a one-pass optimum. If an interviewer probes, the expected deliverable is the proof of the greedy move, not an alternative algorithm.

Common pitfalls

• Moving the pointer at the taller line (or the one that “looks promising”) — the exchange argument only justifies discarding the shorter line; moving the taller one can skip the optimal pair.
• Using max(height[i], height[j]) for the area — water is bounded by the shorter wall; height 0 lines make this mistake obvious ([0,5] holds 0, not 5).
• Computing area only when it improves, but before deciding which pointer to move — compute area every step; the optimal pair may appear mid-sweep (step 2 in the walkthrough) and never again.
• Confusing this with Trapping Rain Water — here exactly two lines form the container and the bars between them are ignored; trapping-rain-water sums water over every bar.

Pattern takeaway

Converging two pointers earn O(n) on pair-maximization problems when you can prove an elimination lemma: from the current pair, identify the endpoint that cannot participate in any better pair and retire it permanently. Start from the extreme (widest) configuration so one dimension only degrades, then argue the other dimension is capped by the endpoint you drop. When you can state “every pair involving this element is ≤ the current best,” a linear sweep silently covers all O(n^2) candidates.