Container With Most Water — InterviewPrepKit

Solving tips

Start pointers at both ends (widest container) and always move the pointer at the SHORTER line inward; that greedy elimination gives O(n).
Exchange-argument justification: area is capped by the shorter wall, so any pair keeping it and narrowing is provably no better, letting you discard it.
Compute area = width * min(heights) every step before moving, since the optimum can appear mid-sweep and never recur.
O(n) time, O(1) space; on a tie moving either pointer is safe. Don't confuse with Trapping Rain Water (only two lines form this container).

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

Hint 1

Area is width times the smaller height. Starting from the widest possible container (first and last lines), any other pair is *narrower* — so a better pair must make up for the lost width with more height.

Hint 2

With pointers at both ends, moving either one shrinks the width by 1. Moving the pointer at the **taller** line can never help — the area is capped by the shorter line, which is still there (or worse), and the width just shrank.

Hint 3

So the shorter line's pointer is the only one worth moving: every pairing that included it has been implicitly considered and beaten. Track the best area while the pointers converge — `O(n)` total.

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.

class Solution:
    def maxArea(self, 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).

The constraints kill it: billions of pair evaluations blow far past any time limit; the problem is engineered to force a linear insight.

Approach 2 — Converging two pointers (greedy elimination)

The insight: start with the widest container — pointers at both ends. Every other pair is narrower, so it can only win by being taller. Now the key exchange argument: the area is capped by the shorter line. Keeping the shorter line and pairing it with any line further inward gives smaller width * height ≤ current area — every such pair is provably no better, so all of them can be discarded at once by moving the shorter line’s pointer inward. Each step eliminates one line from consideration; 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.

class Solution:
    def maxArea(self, 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

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

left	right	heights	width	area	best	move
0	8	1 / 7	8	8	8	left (1 ≤ 7)
1	8	8 / 7	7	49	49	right (7 < 8)
1	7	8 / 3	6	18	49	right
1	6	8 / 8	5	40	49	left (tie)
2	6	6 / 8	4	24	49	left
3	6	2 / 8	3	6	49	left
4	6	5 / 8	2	10	49	left
5	6	4 / 8	1	4	49	left → pointers meet

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.