```meta
title: Container With Most Water
subtitle: The two-pointer approach, why it is safe to skip pairs, and what it costs.
tag: ALGORITHM
```

The problem gives an array `h` of `n` wall heights. Any two walls `l < r` hold water up to the shorter one, so the area is `min(h[l], h[r]) * (r - l)`. The task is the largest area over all pairs.

Brute force checks every pair, which is `n * (n - 1) / 2` areas. Two pointers checks at most `n - 1` areas and still finds the maximum. The gain comes from one rule: only the shorter wall can ever improve by moving.

```callout
tone: note
title: Assumptions in this doc
body: Heights are non-negative integers and n is at least 2. On a tie in height, the left pointer moves. Indices are zero-based.
```

## The loop

Start with the widest container, then shrink it from the side that limits it. Each step discards one wall for good, so the loop ends after `n - 1` steps.

```flow
dir: LR
nodes:
  - { id: start, col: 1, row: 1, kind: start, label: Start }
  - { id: init, col: 2, row: 1, kind: process, label: "l = 0, r = n - 1, best = 0" }
  - { id: loop, col: 3, row: 1, kind: decision, label: "l < r?" }
  - { id: done, col: 3, row: 2, kind: end, label: Return best }
  - { id: area, col: 4, row: 1, kind: process, label: "area = min(h[l], h[r]) * (r - l); best = max(best, area)" }
  - { id: which, col: 5, row: 1, kind: decision, label: "h[l] < h[r]?" }
  - { id: movel, col: 6, row: 1, kind: process, label: "l = l + 1" }
  - { id: mover, col: 6, row: 2, kind: process, label: "r = r - 1" }
edges:
  - start -> init
  - init -> loop
  - loop -> area: "yes"
  - loop --> done: "no"
  - area -> which
  - which -> movel: "yes"
  - which -> mover: "no"
  - movel -> loop
  - mover -> loop
```

## Why skipping pairs is safe

The shorter wall caps the area. Every pair that keeps the shorter wall and moves the other wall inward is narrower and no taller, so it is never better. Dropping the shorter wall loses nothing.

```spec
title: Loop invariants
accent: teal
rows:
  - { label: Window, value: "The best pair over all of h lies inside [l, r] or was already recorded in best." }
  - { label: Discard rule, value: "The wall at the pointer with the smaller height is never part of a better pair with any wall still inside the window." }
  - { label: Tie, value: "When h[l] equals h[r], both walls cap every pair inside the window, so either pointer can move." }
  - { label: Progress, value: "Each step moves exactly one pointer inward by one, so the loop runs r - l times at most." }
  - { label: Result, value: "When l meets r the window is empty and best holds the maximum area." }
```

## Worked trace

Input `h = [1, 8, 6, 2, 5, 4, 8, 3, 7]`, `n = 9`. The maximum is 49, found on the second step; the six later steps only confirm that no wider or taller pair remains.

```table
columns: [Step, l, r, "h[l]", "h[r]", Width, Area, Best, Move]
rows:
  - [1, 0, 8, 1, 7, 8, 8, 8, "l (1 < 7)"]
  - [2, 1, 8, 8, 7, 7, { v: 49, tone: pos, highlight: true }, { v: 49, tone: pos }, "r (8 > 7)"]
  - [3, 1, 7, 8, 3, 6, 18, 49, "r (8 > 3)"]
  - [4, 1, 6, 8, 8, 5, 40, 49, "l (tie)"]
  - [5, 2, 6, 6, 8, 4, 24, 49, "l (6 < 8)"]
  - [6, 3, 6, 2, 8, 3, 6, 49, "l (2 < 8)"]
  - [7, 4, 6, 5, 8, 2, 10, 49, "l (5 < 8)"]
  - [8, 5, 6, 4, 8, 1, 4, 49, "l (4 < 8), then l = r and the loop stops"]
note: Brute force checks 36 pairs for this input. The two-pointer loop checks 8.
```

## Cost against brute force

Both approaches use constant extra space. The difference is the number of areas computed, which grows with the square of `n` for brute force and with `n` for two pointers.

```benchmark
title: Brute force vs two pointers
metricLabel: Measure
subjects:
  - { label: Two pointers, featured: true }
  - { label: Brute force, tone: muted }
rows:
  - { label: Time, better: none, cells: [{ value: "O(n)", best: true }, "O(n²)"] }
  - { label: Extra space, better: none, cells: ["O(1)", "O(1)"] }
  - { label: Areas computed, sub: "n = 9", better: low, cells: [8, 36] }
  - { label: Areas computed, sub: "n = 100 000", better: low, cells: ["99 999", "about 5 × 10⁹"] }
  - { label: Passes over h, better: low, cells: [1, "n"] }
note: Areas computed is exact for two pointers (n - 1) and for brute force (n(n - 1) / 2).
```

## Implementation

```code
title: maxArea
blocks:
  - title: maxArea.ts
    lang: TypeScript
    code: |
      export function maxArea(h: number[]): number {
        let l = 0;
        let r = h.length - 1;
        let best = 0;
        while (l < r) {
          const area = Math.min(h[l], h[r]) * (r - l);
          if (area > best) best = area;
          if (h[l] < h[r]) l += 1;
          else r -= 1;
        }
        return best;
      }
```