p27 — Container With Most Water

Source: LeetCode 11 · Medium · Topics: Array, Two Pointers, Greedy Companies (2024–2025 frequency): Google (very high), Amazon (high), Meta (high), Bloomberg (high), Microsoft (medium), Apple (medium) Loop position: first round — used as a “do you reach for two-pointers” filter. Senior+ also asked to PROVE the move rule.

1. Quick Context

Given n non-negative integers representing heights of vertical lines on the x-axis, find two lines that together with the x-axis form a container holding the maximum amount of water.

Container area between lines i < j is min(height[i], height[j]) * (j - i).

This is the purest form of converging two-pointer. The problem is small, but the proof of the move rule is what separates Mid from Senior+. Mid candidates implement it correctly by intuition; Senior+ explains why moving the shorter pointer is correct (and why moving the taller one is incorrect).

The interviewer’s bait: “why does this work?” If you can’t articulate the invariant, your “correct” code is treated as a lucky guess. Have the proof ready.

2. LeetCode Link + Attempt Gate

🔗 https://leetcode.com/problems/container-with-most-water/

STOP. 20-min timer. Two pointers from opposite ends. Be ready to PROVE the move rule before reading hints.

3. Prerequisite Concepts

• Converging two-pointer template (lo, hi = 0, n-1; while lo < hi).
• The “area = min(h_lo, h_hi) × width” formula.
• phase-02-patterns/labs/lab-01-two-pointers.md

4. How to Approach (FRAMEWORK Steps 1–9)

Step 1 — Restate: “Given non-negative integers height[0..n-1], find indices i < j maximizing min(height[i], height[j]) * (j - i). Return that maximum.”

Step 2 — Clarify:

• “Can heights be zero?” (LC: yes. Zero-height lines hold no water.)
• “Can n be 1?” (LC: n ≥ 2.)
• “Negative heights?” (No — non-negative.)
• “Return the area or the indices?” (LC: the area.)

Step 3 — Constraints: N ≤ 10⁵ for LC. Brute O(N²) = 10¹⁰ — TLE. Need O(N).

Step 4 — Examples:

• [1,8,6,2,5,4,8,3,7] → 49 (lines at index 1 height 8 and index 8 height 7: min=7, width=7).
• [1, 1] → 1.
• [4, 3, 2, 1, 4] → 16 (outermost lines).

Step 5 — Brute Force: All pairs (i, j), compute area, track max. O(N²). State, then pivot.

Step 6 — Complexity (optimal): O(N) time, O(1) space.

Step 7 — Pattern Recognition: “Maximize over (i, j) pairs with a function depending on the WORSE of two endpoints and the distance between them” → converging two-pointer. Start at the widest pair, narrow inward.

Step 8 — Develop:

def maxArea(height):
    lo, hi = 0, len(height) - 1
    best = 0
    while lo < hi:
        h = min(height[lo], height[hi])
        best = max(best, h * (hi - lo))
        # Move the SHORTER pointer (proof: see deeper insight)
        if height[lo] < height[hi]:
            lo += 1
        else:
            hi -= 1
    return best

Step 9 — Test: [1,1] → 1, [4,3,2,1,4] → 16, monotone increasing [1,2,3,4,5], all-equal [5,5,5,5].

5. Progressive Hints

If stuck for 5 min, open hints.md.

6. Deeper Insight — Why moving the SHORTER pointer is correct

The move rule: at state (lo, hi), if height[lo] < height[hi], advance lo. Otherwise retreat hi.

The proof (the part interviewers want to hear):

Let h = min(height[lo], height[hi]). WLOG suppose height[lo] ≤ height[hi], so h = height[lo]. The current area is h * (hi - lo).

Claim: every pair (lo, hi') with hi' < hi has area ≤ h * (hi - lo).

Proof:

• The width of (lo, hi') is hi' - lo < hi - lo.
• The container height is min(height[lo], height[hi']) ≤ height[lo] = h.
• So area (lo, hi') = min(h, height[hi']) * (hi' - lo) ≤ h * (hi' - lo) < h * (hi - lo).

So no pair (lo, *) to the LEFT of hi can beat the current best — we can safely eliminate the entire column at lo by moving lo forward. The candidate set shrinks by N−hi+lo−1 pairs in one move; over the run, we examine N pairs total, achieving O(N).

The symmetric argument applies when height[hi] < height[lo].

Why moving the TALLER pointer is incorrect: if we move hi when height[hi] > height[lo], we keep lo fixed. But the new hi-1 could have a larger min(height[lo], height[hi-1]) only if height[hi-1] > height[hi] — but the container height is still capped by height[lo] (which didn’t change). So min(h_lo, h_new_hi) ≤ h_lo = h, but width shrank — strict loss. We’d miss real opportunities at (lo+1, hi).

Tie case (height[lo] == height[hi]): moving EITHER is correct — the proof above goes through with ≤ rather than <. Convention: move lo.

Invariant statement: “At every iteration, the optimal pair lies within the slice [lo, hi].” This is the loop invariant. It’s preserved by the move rule.

7. Anti-Pattern Analysis

1. O(N²) brute and shipping it. Works on small inputs, TLE on big.
2. Moving both pointers each iteration. Misses the move-rule subtlety. Wrong answer.
3. Moving the TALLER pointer. Provably wrong (see proof). Common rookie error.
4. Computing area as max(h_lo, h_hi) * width. Container fills to MIN, not MAX.
5. Off-by-one width: hi - lo + 1 instead of hi - lo. Width = index distance, not inclusive count.
6. while lo <= hi. At lo == hi, width = 0, area = 0. Wastes an iteration but harmless. < is cleaner.
7. Forgetting tie case. Code if height[lo] < height[hi] then else covers ties correctly; if <= would be wrong only stylistically.
8. “Greedy doesn’t work; let me DP.” DP gives the same O(N²) brute. Two pointers IS the optimal here; recognize it.

8. Skills & Takeaways

• Converging two-pointer as a “candidate elimination” pattern (each move eliminates a row/column of the pair-grid).
• The shorter-pointer move rule with proof.
• Loop invariant articulation — “optimal pair is in [lo, hi].”
• Recognizing greedy is provably optimal in monotone-elimination problems.
• Distinguishing this from Trapping Rain Water — that uses two pointers too, but with different state (running max from each side).

9. When to Move On

Move on when:

• You can write maxArea in under 5 minutes from a blank file.
• You can prove the move rule out loud without referencing notes.
• You can articulate the invariant: “the optimal pair is in [lo, hi].”
• You can explain why this problem is DIFFERENT from Trapping Rain Water (different state, different invariant).
• Your stress test compares to O(N²) brute on 200 random arrays.

10. Company Context

Google:

• Asked at every level. Senior+ MUST prove the move rule. “Why does this work?” is the killer follow-up.
• Often paired with LC 42 (Trapping Rain Water) in same round — the contrast is the lesson.
• Scorecard phrase: “Algorithm — clean 2-pointer, MOVE-RULE PROVED rigorously.”

Amazon:

• Bar Raiser sometimes asks “why not move both?” — testing whether you’ve memorized vs understood.
• Scorecard phrase: “Strong — recognized 2-pointer, articulated correctness.”

Meta:

• Often in same round as LC 15 (3Sum). Both test 2-pointer fluency.
• Scorecard phrase: “Algorithm — fluent 2-pointer.”

Bloomberg:

• Frames as “two trading days bracketing a position” or “bandwidth between two routers.” Same algorithm.
• Scorecard phrase: “Strong — pragmatic 2-pointer with proof.”

Microsoft / Apple:

• Standard variant. Watches for correct width formula and tie handling.
• Scorecard phrase: “Solid.”

11. Interviewer’s Lens

12. Level Delta

Mid (L4):

• Two-pointer, correct move rule by intuition.
• Correct width formula.
• O(N), O(1) stated.

Senior (L5):

• Articulates the move rule’s correctness in plain English.
• States the loop invariant.
• Distinguishes this from Trapping Rain Water.
• Handles tie case correctly.

Staff (L6):

• Formal proof (the “(lo, hi’) has area ≤” argument).
• Notes this generalizes to “maximize over pairs where the objective is monotone in one endpoint” — name it candidate elimination.
• Discusses what changes if widths are weighted unevenly (e.g., x-coordinates are not 0..n-1).
• Discusses the 3D analog (cuboid container).

Principal (L7+):

• Frames as a special case of monotone matrix searching (or SMAWK adjacent territory).
• Discusses generalization: “maximize f(h_i, h_j, j - i) where f is monotone in min(h) and in width” — same algorithm works.
• Discusses streaming variant: heights arrive online; harder, requires segment tree or fancy data structure.
• Discusses parallelization: not embarrassingly parallel (the move depends on previous state), but can be done with divide-and-conquer in O(N log N).

13. Follow-up Q&A

Q1: Heights arrive online (streaming). What now? A: Two pointers no longer apply (need to retract the right pointer, but new data only comes from the right). Maintain a monotone-decreasing stack of “still in contention” indices on the left (only indices with strictly increasing heights from left can possibly be optimal lo for any future hi). For each new index, binary-search the stack for the best lo to pair with it. O(N log N) overall.

Q2: 3D analog — heights are now a 2D grid, container holds a 3D volume. A: This is essentially Trapping Rain Water II (LC 407). Algorithm: min-heap from the boundary inward (Dijkstra-like). O(MN log MN).

Q3: Widths are weighted — x-coordinate of column i is x[i], not i. A: Two-pointer still works. Width = x[hi] - x[lo]. Move rule unchanged: still move the shorter height. Proof unchanged (only width factor differs, monotone-decreasing as we move inward).

Q4: Return the indices, not the area. A: Trivial wrap — track best_pair = (lo, hi) alongside best.

Q5: Top-K largest containers (no two share a side). A: Much harder — combinatorial. Likely DP or greedy with bookkeeping. Discuss complexity tradeoffs.

14. Solution Walkthrough

See solution.py:

• max_area(height) — canonical converging two-pointer.
• max_area_brute(height) — O(N²) oracle.
• max_area_streaming(heights) — streaming variant with monotone stack + binary search (O(N log N)).
• stress_test() — 500 random arrays N≤30, all variants agree.
• edge_cases() — n=2, all-equal, monotone, LC canonical, all-zero.

Run: python3 solution.py → “ALL TESTS PASSED”.

15. Beyond the Problem

Principal-engineer code review comment:

“The 2-pointer code is fine. What I want to see in the PR description, every time, is the move-rule proof as a one-line comment: # inv: optimal pair lies in [lo, hi]; moving the shorter side preserves this. Without that comment, the next engineer who tries to ‘optimize’ this code by moving both pointers each step (which I’ve seen TWICE in our codebase) breaks it without realizing. The streaming variant you mention is the actual production case for our network-monitoring tool — please factor it into a separate function with its own tests, don’t bury it as a ‘bonus.’”

Connections forward:

• p28 — Trapping Rain Water uses the same outer skeleton (two pointers) but maintains different state (running max from each side). The contrast is the lesson.
• Phase 02 — lab-01-two-pointers; lab-05-monotonic-stack (the streaming variant).
• Phase 06 — Greedy; this problem is a textbook “greedy proven optimal by candidate-elimination.”
• Production: rate-limit window selection (find two timestamps that bound the largest allowed throughput window), audio sample peak-pair detection, image cropping (find two vertical lines containing the widest valid region).