HARD Lab · Two Pointers · 07

11. Container With Most Water

Two walls form a container whose capacity is min(h[l], h[r]) × (r − l). Start pointers at both ends and always move the shorter wall inward — moving the taller one could never improve the area, so you explore every promising pair in a single O(n) pass.

● MediumTwo PointersGreedyTypeScript

PROBLEM What we're solving

Given an array height where each value is a vertical wall, find two walls that, together with the x-axis, hold the most water. The area between walls at indices l and r is min(height[l], height[r]) × (r − l) — the shorter wall is the bottleneck, and the width is the gap. Example: height = [1,8,6,2,5,4,8,3,7] → the pair at indices 1 and 8 (heights 8 and 7) gives area min(8,7) × (8−1) = 7 × 7 = 49.

KEY IDEA Moving the shorter wall is the only move that can help

Insight → Start with pointers at both ends (maximum possible width). At each step, the area is bottlenecked by the shorter wall. Moving the taller wall inward shrinks the width while keeping the same (or smaller) height cap — the area can only stay the same or decrease. So discard the taller-wall moves as provably useless, and move the shorter wall inward. This greedy choice is safe: you miss nothing.

RECIPE Squeeze inward, always drop the shorter bar

  • 0 · Init. l = 0, r = n − 1, best = 0. The widest possible pair starts the search.
  • 1 · Compute area. area = min(h[l], h[r]) × (r − l). Update best if larger.
  • 2 · Move the shorter pointer. If h[l] <= h[r], increment l; otherwise decrement r. Moving the taller bar could never produce a better area — the height cap stays the same or drops while width decreases.
  • 3 · Repeat until l >= r. Every pair that could beat the current best has been visited.
Classic confusion →People often wonder: "what if moving the taller wall finds a much taller wall next?" It doesn't matter — the new area is still capped by the (unchanged) shorter wall, and the width is now smaller. Formally: for any pair (l, r) where h[l] <= h[r], every pair (l, r') with r' < r has area <= h[l] × (r' − l) < h[l] × (r − l). So all those pairs are provably worse — skip them by moving r is unnecessary; we move l instead.

COST Complexity & alternatives

Brute force — try all pairs
O(n²)
Nested loops over every (i, j) pair.
Two pointers
O(n)
Single pass, O(1) extra space.

The two-pointer approach is both time and space optimal. Unlike most two-pointer problems there is no sorting step — the array is used as-is.

Pattern transfer →The same "shrink from both ends, discard the worse side" greedy appears in Trapping Rain Water (LC 42 — sum the trapped water instead of max single container), Two Sum II — sorted array (move based on sum vs target), and 3Sum (fix one element, two-pointer the rest). The invariant is always: one pointer move provably cannot produce a better answer than the other.

RUN IT Two pointers squeeze inward, always drop the shorter bar

step 0 / 19
STARTTwo pointers start at both ends: l=0, r=8. We'll track the best area seen.
1
0
8
1
6
2
2
3
5
4
4
5
8
6
3
7
7
8
area now
—
best area
—
active pointers (l, r)best pair found so far
slowfast

TYPESCRIPT The solution, annotated

maxArea.ts
function maxArea(height: number[]): number {
  let l = 0;
  let r = height.length - 1;
  let best = 0;

  while (l < r) {
    const area = Math.min(height[l], height[r]) * (r - l);
    if (area > best) best = area;

    // Always move the shorter pointer inward.
    // Moving the taller one can never increase area —
    // width shrinks and height is still capped by the shorter bar.
    if (height[l] <= height[r]) {
      l++;
    } else {
      r--;
    }
  }

  return best;
}

Reading it block by block

Lines 2–4 — initialise. l and r start at opposite ends, giving the widest possible container. best accumulates the running maximum.
Lines 7–8 — compute and record. Area = height of the shorter wall × width of the gap. Update best if this pair beats the current record.
Lines 12–16 — the greedy move. If height[l] <= height[r], the left wall is the bottleneck; move l right. Otherwise move r left. Moving the taller wall inward can only decrease (or maintain) the height cap while the width definitely shrinks — a strictly worse or equal area. The comment in the code captures the exact reason.
Line 20 — return. When the pointers meet, every pair that could beat the running best has been evaluated. Return best.
Complexity → O(n) time — each pointer moves inward at most n steps total; O(1) space — only three scalar variables. The inner reasoning looks like it might miss pairs, but the greedy proof shows every skipped pair is provably dominated.

INTERVIEWFollow-ups they'll ask

  • "Why is moving the taller pointer always safe to skip?" When h[l] <= h[r], any pair formed by moving r to r' has area at most h[l] × (r' − l), which is strictly less than h[l] × (r − l) — so we skip it without missing the optimum.
  • "Can you return the actual indices, not just the area?" Track bestL and bestR alongside best and update them whenever a new maximum is found.
  • "What if all heights are equal?" The algorithm still works — the widest pair (indices 0 and n−1) is always evaluated first and happens to be optimal when all heights are equal, since area = h × (n−1).
  • "Trapping Rain Water next?" LC 42 accumulates total trapped water across all bars. The two-pointer idea extends: maintain running max from left and from right, and decide which side to advance.
  • "Brute force first?" O(n²) nested loops over all (i, j) pairs is easy to state and obviously correct. The interview insight is recognising that fixed-endpoint pairs in each row are dominated, letting you prune to a single pass.

MNEMONIC The one-liner

"Widest first, then squeeze — always drop the shorter wall. The taller one can never save you."

TRIGGERS When you see ___ → reach for ___

"most water" / "max container"two pointers from both ends
area = min height × widthmove the shorter pointer inward
O(n) two-pointer on unsorted arraygreedy: discard dominated side
"trapping rain water" variantsame pattern, sum instead of max

SKELETON The reusable shape

skeleton.ts
let l = 0, r = height.length - 1, best = 0;
while (l < r) {
  const area = Math.min(height[l], height[r]) * (r - l);
  if (area > best) best = area;
  if (height[l] <= height[r]) {
    l++;
  } else {
    r--;
  }
}
return best;

FLASHCARDS Tap to flip

What is the area formula between walls at l and r?
min(height[l], height[r]) × (r − l) — the shorter wall is the bottleneck; width is the gap.
tap to flip
1 / 7
Answer to reveal explanations. No penalty for retries.Score: 0 / 7
QUESTION 01
What is the time complexity of the two-pointer solution?
QUESTION 02
For height = [1,8,6,2,5,4,8,3,7], what is the maximum area?
QUESTION 03
When h[l] <= h[r], which pointer do you move and why?
QUESTION 04
What if we moved the taller pointer instead of the shorter one?
QUESTION 05
Space complexity of the two-pointer approach?
QUESTION 06
For height = [4, 4] (two walls of equal height), what is the area?
QUESTION 07
Which sibling problem uses the same "squeeze from both ends" two-pointer pattern?