Container With Most Water - move the shorter wall

Day 40 squeezed for a target sum. Day 46 fixed one index and squeezed. Today the same converging geometry maximizes area: width × min(heights). The greedy rule is the whole lesson — always advance the shorter side.

LeetCode #11: you are given n vertical lines. Pick two indices i < j. The container holds min(height[i], height[j]) × (j − i) units of water. Return the maximum possible area.

The problem

maxArea([1,8,6,2,5,4,8,3,7]) → 49
// lines at index 1 (h=8) and 8 (h=7): min(8,7)×(8-1) = 49

maxArea([1,1]) → 1

Brute force tries every pair — O(n²). At n=2K that is millions of multiplies. Two pointers start at the ends (maximum width) and shrink intelligently.

Approach 1: Brute force every pair

function maxAreaBrute(height) {
  let best = 0;
  const n = height.length;
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      const area = Math.min(height[i], height[j]) * (j - i);
      if (area > best) best = area;
    }
  }
  return best;
}

Correct. Lab n=2K: 14,702 μs median.

Approach 2: Two pointers — move the shorter side

function maxArea(height) {
  let l = 0, r = height.length - 1, best = 0;
  while (l < r) {
    const h = Math.min(height[l], height[r]);
    const area = h * (r - l);
    if (area > best) best = area;
    if (height[l] <= height[r]) l++; // shorter (or equal) moves
    else r--;
  }
  return best;
}

Why moving the shorter side is safe

Area is limited by the shorter height. Suppose height[l] ≤ height[r].

• Every pair that keeps this short l with some r’ < r has smaller width and height ≤ height[l], so area ≤ current. Those pairs are dominated — discard l.
• Moving the taller side only shrinks width while the min cannot exceed the current short height.
• Moving the short side is the only move that might raise the limiting height enough to offset lost width.

Ties: either side works; the code advances l when equal. Still O(n).

One-pass invariant

After each step, every discarded index is proven not to participate in a better pair with any remaining opposite-side index. The search space is a shrinking interval [L, R]; the global max is the max of areas evaluated on the boundary of that interval as it shrinks. That is why you never need a second pass or a stack for this problem.

Contrast Day 46: 3Sum needs an outer loop because three indices create a family of targets. Here two indices and a max objective collapse to one greedy pass.

Worked walk

height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
L=0 (1), R=8 (7) → area = 1×8 = 8 · short is L → L++
L=1 (8), R=8 (7) → area = 7×7 = 49 · short is R → R--
L=1 (8), R=7 (3) → area = 3×6 = 18 · short is R → R--
… continue until L meets R
best stays 49

Day 40 vs Day 47 — same hands, different goal

Dimension	Day 40 Two Sum II	Day 47 Container
Geometry	Converge L/R	Converge L/R
Input order	Must be sorted	Any order (heights as given)
Move rule	sum too small → L++; too big → R—	always move the shorter height
Goal	Hit target sum	Maximize area

Complexity honesty

Two pointers: O(n) time, O(1) extra space. Each index is visited at most once as L or R advances. Brute: O(n²) pairs. The asymptotic gap is the whole story at n=10K.

Plateaus and equal heights

When height[l] === height[r], moving either side is fine for correctness. Some solutions advance both on a tie; still O(n). Do not special-case plateaus beyond the tie branch.

// all equal H → best is H * (n - 1)  (outermost walls)
maxArea([5,5,5,5]) → 5 * 3 = 15

Interview soundbite

“I start at maximum width. Area is limited by the shorter line, so every pair that keeps that short line with a closer partner is dominated. I discard the short index and continue. One pass, O(n), O(1) space.”

Micro-example — why not move the tall wall

heights:  L=2 ........ R=5    width=10
area now = min(2,5)*10 = 20

If we move R (taller): width=9, min(2, ?) ≤ 2 → area ≤ 18 < 20
Any move of the tall side alone cannot help while L stays 2.

If we move L (shorter): maybe next is 9 → min(9,5)*9 = 45 wins.

Not Trapping Rain Water

This problem is two walls only — water between the chosen pair, flat top at the min height. Trapping Rain Water (next roadmap) sums water above each index using left/right max bounds. Same family of “heights and water,” different aggregation.

Lab — Node, 30-run median

Seeded heights 1..10000. The benchmark script and standalone write-up are not included in this repository.

Approach	n=500 (μs)	n=2K (μs)	n=10K (μs)
Brute O(n²)	647.5	14,702.2	skip
Two pointers O(n)	11.7	45.3	80.3

Headline (n=2K): two-ptr is 324.6× faster than brute (14,702 → 45.3 μs). At n=10K two-ptr stays ~80 μs; brute is skipped.

What breaks? — Anti-patterns

1. Always moving the taller side. You shrink width without a chance to raise the min height. Fix: move the shorter (or either on tie).

2. Sorting the array first. Destroys index distances (width). This is not Two Sum II. Fix: pointers on the original index order.

3. Using area = height[l] × height[r]. Water spills over the shorter wall. Fix: min(height[l], height[r]) × width.

4. Off-by-one width. Width is r - l, not r - l + 1 (lines sit on indices). Fix: multiply by (r − l).

How it connects

• Day 40 (Two Sum II): same converge skeleton; sum comparison vs area greedy.
• Day 46 (3Sum): also reduces search with two pointers; today one pass, no outer fix loop.
• Day 39 (Valid Palindrome): converge geometry for equality; here for capacity.

Transfer questions

1. Why does sorting heights break this problem but help Two Sum II?
2. If all heights are equal to H, what is the max area in terms of n and H?
3. How does Trapping Rain Water (next on the roadmap) differ from “two walls only”?

Quiz

Your teach step

Close this lesson. Write the “Explain like I’m 10” and the “60-second LinkedIn version” from memory. Focus on: area = min × width; move the shorter wall; 324.6× at n=2K; do not sort. Post it, and paste the link.

Questions? Ask the agent — Trapping Rain Water setup, or proof edge cases with plateaus.