Container With Most Water (LeetCode 11)
You're given an integer array height of length n. Imagine n vertical lines, where the i^th line runs from (i, 0) up to (i, height[i]).
Pick any two of these lines: together with the x-axis, they mark out a container. Find the pair that holds the most water.
Return the largest amount of water any such container can hold.
Notice the container's sides can't be slanted — you're choosing two of the existing vertical lines as-is.
8 | | | 7 | | | | 6 | | | | | 5 | | | | | | 4 | | | | | | | 3 | | | | | | | | 2 | | | | | | | | | 1 | | | | | | | | | | 0 +-+--+---+---+---+---+---+---+---+---+ 0 1 2 3 4 5 6 7 8 (index) ^~~~~~~~~~~~~~~~~~~~~~~~~~~~^ L=1 (h=8) R=8 (h=7) <-------- Width = 7 --------> Water Level = min(8, 7) = 7 Max Area = 7 × 7 = 49 (Optimal Reservoir) Worked Examples
height = [1,8,6,2,5,4,8,3,7]49Area = width × min(h[L], h[R])
Here: 7 × 7 = 49
Water level is capped at 7 by the shorter line (right wall [idx 8]). Water filled higher will spill over!
Always advance the shorter wall inward. Moving the taller wall only decreases width while keeping the same cap. Only moving the shorter wall can raise the bottleneck!
height = [1,1]1Area = width × min(h[L], h[R])
Here: 1 × 1 = 1
Water level is capped at 1 by the shorter line (both walls tied). Water filled higher will spill over!
Always advance the shorter wall inward. Moving the taller wall only decreases width while keeping the same cap. Only moving the shorter wall can raise the bottleneck!
⚖️Formal Constraints & Bounds
n == height.length2 <= n <= 1050 <= height[i] <= 104
Core Insight
The shorter line strictly bounds height and cannot produce a larger area with any narrower width, proving greedy elimination correctness.
Real-World Scenario & Production Applications
Fluid dynamics capacity calculation, structural engineering truss bounding, and stock market volatility channel containment.
Subproblems & Recurrence Decomposition3 Phases
Place pointers at extreme boundaries left = 0, right = len(height) - 1 to capture the widest possible container width right - left.
left = 0
right = len(height) - 1
max_area = 0Step-by-Step Execution Trace Table
| Step | left (h) | right (h) | width | min_h | area | Action |
|---|---|---|---|---|---|---|
| 1 | 0 (1) | 8 (7) | 8 | 1 | 8 | h[0]=1 < h[8]=7 → left++ |
| 2 | 1 (8) | 8 (7) | 7 | 7 | 49 | h[1]=8 > h[8]=7 → right-- |
| 3 | 1 (8) | 7 (3) | 6 | 3 | 18 | h[1]=8 > h[7]=3 → right-- |
| 1 | left, right = 0, len(height) - 1 |
| 2 | max_area = 0 |
| 3 | while left < right: |
| 4 | h = min(height[left], height[right]) |
| 5 | max_area = max(max_area, (right - left) * h) |
| 6 | if height[left] < height[right]: |
| 7 | left += 1 |
| 8 | else: |
| 9 | right -= 1 |
| 10 | return max_area |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Discarding the shorter wall on purpose, when it feels like the taller one is "winning," is the single hardest leap in this pattern to trust without a proof.
🪣 The Analogy: Water Always Spills at the Shorter Wall
Picture two walls holding back water — one tall, one short. No matter how tall the taller wall is, the water can never rise above the shorter wall; it spills over the low side first. So the shorter wall is the true bottleneck on the container's capacity, not the taller one.
Now ask: if you keep the current pair and only move one pointer inward, which move could possibly do better? Moving the taller wall's pointer inward shrinks the width while the height is still capped by the (unmoved) shorter wall — area can only shrink or tie. Moving the shorter wall's pointer inward also shrinks the width, but it's the only move that has a chance of finding a taller wall to raise the bottleneck height — the only move that could ever produce a bigger area.
🔑 The Key Idea in the Code
Discarding the shorter wall's current position is safe because every other pairing that keeps that same short wall is strictly worse (smaller width, same height cap) — so nothing is ever lost by moving on.
Moving the taller line: Area is bounded by
min(h[left], h[right]) * (right - left). Moving the taller wall only decreases width without any possibility of increasing height. You must always move the SHORTER wall.Using
right - left + 1for width: Width between indexleftandrightisright - left, NOTright - left + 1. Using+1produces incorrect area for all containers.Arbitrary tie-breaking: When
height[left] == height[right], moving either pointer (or both) is mathematically safe because neither can form a larger container with any intermediate wall.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
2D area optimization bounded by two boundary endpoints.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: no container with the current shorter boundary at smaller widths can exceed the current area.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
This problem's traps are in Common Pitfalls above.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I place pointers at 0 and len(height)-1. I compute width * min(h[left], h[right]) and record max area. Then I eliminate whichever pointer has the smaller height. Runs in
O(N)time andO(1)space."
Complexity & Mathematical Proof
O(N)
Look at the execution steps: Left and right pointers start at boundaries. Area is width * min(heights). The pointer with shorter height is moved inward because keeping it could never yield a larger area with a smaller width.
O(1) Auxiliary
Look at memory allocations: Call stack uses O(1) Iterative. Only tracks left and right indices and max_area integer in O(1) space.
T(N) = N-1 width contractions = O(N)
Derivation Progression
Area = (R - L) · min(H[L], H[R])
Computes current bounding box capacity in O(1) time.
if H[L] < H[R]: L += 1 else R -= 1
The shorter line cannot form a larger container with any other remaining inner line, so it is discarded safely.
N-1 steps
Pointers meet after exactly N-1 iterations.
Variable Definitions
Total number of vertical lines in the array
Memory Architecture & Bounds
O(1) Iterative
O(1) 3 scalar registers
O(1) Maximum water integer
Boundary Best / Worst Cases
Pointer Invariant Transition Progression
Senior SWE Deconstruction & Hardware Caveats
Triggers: "two lines together with x-axis forms container", "maximize water container can contain". Bilateral boundary convergence with greedy bottleneck elimination.
. Naive pair checking is (TLE). Requires strictly linear time and space.
Moving both pointers simultaneously when heights are equal: moving either is safe since the limiting height is already bounded by both lines.
Container With Most Water (LeetCode 11)
You're given an integer array height of length n. Imagine n vertical lines, where the i^th line runs from (i, 0) up to (i, height[i]).
Pick any two of these lines: together with the x-axis, they mark out a container. Find the pair that holds the most water.
Return the largest amount of water any such container can hold.
Notice the container's sides can't be slanted — you're choosing two of the existing vertical lines as-is.
8 | | | 7 | | | | 6 | | | | | 5 | | | | | | 4 | | | | | | | 3 | | | | | | | | 2 | | | | | | | | | 1 | | | | | | | | | | 0 +-+--+---+---+---+---+---+---+---+---+ 0 1 2 3 4 5 6 7 8 (index) ^~~~~~~~~~~~~~~~~~~~~~~~~~~~^ L=1 (h=8) R=8 (h=7) <-------- Width = 7 --------> Water Level = min(8, 7) = 7 Max Area = 7 × 7 = 49 (Optimal Reservoir) Worked Examples
height = [1,8,6,2,5,4,8,3,7]49Area = width × min(h[L], h[R])
Here: 7 × 7 = 49
Water level is capped at 7 by the shorter line (right wall [idx 8]). Water filled higher will spill over!
Always advance the shorter wall inward. Moving the taller wall only decreases width while keeping the same cap. Only moving the shorter wall can raise the bottleneck!
height = [1,1]1Area = width × min(h[L], h[R])
Here: 1 × 1 = 1
Water level is capped at 1 by the shorter line (both walls tied). Water filled higher will spill over!
Always advance the shorter wall inward. Moving the taller wall only decreases width while keeping the same cap. Only moving the shorter wall can raise the bottleneck!
⚖️Formal Constraints & Bounds
n == height.length2 <= n <= 1050 <= height[i] <= 104
Core Insight
The shorter line strictly bounds height and cannot produce a larger area with any narrower width, proving greedy elimination correctness.
Real-World Scenario & Production Applications
Fluid dynamics capacity calculation, structural engineering truss bounding, and stock market volatility channel containment.
Subproblems & Recurrence Decomposition3 Phases
Place pointers at extreme boundaries left = 0, right = len(height) - 1 to capture the widest possible container width right - left.
left = 0
right = len(height) - 1
max_area = 0Step-by-Step Execution Trace Table
| Step | left (h) | right (h) | width | min_h | area | Action |
|---|---|---|---|---|---|---|
| 1 | 0 (1) | 8 (7) | 8 | 1 | 8 | h[0]=1 < h[8]=7 → left++ |
| 2 | 1 (8) | 8 (7) | 7 | 7 | 49 | h[1]=8 > h[8]=7 → right-- |
| 3 | 1 (8) | 7 (3) | 6 | 3 | 18 | h[1]=8 > h[7]=3 → right-- |
| 1 | left, right = 0, len(height) - 1 |
| 2 | max_area = 0 |
| 3 | while left < right: |
| 4 | h = min(height[left], height[right]) |
| 5 | max_area = max(max_area, (right - left) * h) |
| 6 | if height[left] < height[right]: |
| 7 | left += 1 |
| 8 | else: |
| 9 | right -= 1 |
| 10 | return max_area |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Discarding the shorter wall on purpose, when it feels like the taller one is "winning," is the single hardest leap in this pattern to trust without a proof.
🪣 The Analogy: Water Always Spills at the Shorter Wall
Picture two walls holding back water — one tall, one short. No matter how tall the taller wall is, the water can never rise above the shorter wall; it spills over the low side first. So the shorter wall is the true bottleneck on the container's capacity, not the taller one.
Now ask: if you keep the current pair and only move one pointer inward, which move could possibly do better? Moving the taller wall's pointer inward shrinks the width while the height is still capped by the (unmoved) shorter wall — area can only shrink or tie. Moving the shorter wall's pointer inward also shrinks the width, but it's the only move that has a chance of finding a taller wall to raise the bottleneck height — the only move that could ever produce a bigger area.
🔑 The Key Idea in the Code
Discarding the shorter wall's current position is safe because every other pairing that keeps that same short wall is strictly worse (smaller width, same height cap) — so nothing is ever lost by moving on.
Moving the taller line: Area is bounded by
min(h[left], h[right]) * (right - left). Moving the taller wall only decreases width without any possibility of increasing height. You must always move the SHORTER wall.Using
right - left + 1for width: Width between indexleftandrightisright - left, NOTright - left + 1. Using+1produces incorrect area for all containers.Arbitrary tie-breaking: When
height[left] == height[right], moving either pointer (or both) is mathematically safe because neither can form a larger container with any intermediate wall.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
2D area optimization bounded by two boundary endpoints.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: no container with the current shorter boundary at smaller widths can exceed the current area.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
This problem's traps are in Common Pitfalls above.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I place pointers at 0 and len(height)-1. I compute width * min(h[left], h[right]) and record max area. Then I eliminate whichever pointer has the smaller height. Runs in
O(N)time andO(1)space."
Complexity & Mathematical Proof
O(N)
Look at the execution steps: Left and right pointers start at boundaries. Area is width * min(heights). The pointer with shorter height is moved inward because keeping it could never yield a larger area with a smaller width.
O(1) Auxiliary
Look at memory allocations: Call stack uses O(1) Iterative. Only tracks left and right indices and max_area integer in O(1) space.
T(N) = N-1 width contractions = O(N)
Derivation Progression
Area = (R - L) · min(H[L], H[R])
Computes current bounding box capacity in O(1) time.
if H[L] < H[R]: L += 1 else R -= 1
The shorter line cannot form a larger container with any other remaining inner line, so it is discarded safely.
N-1 steps
Pointers meet after exactly N-1 iterations.
Variable Definitions
Total number of vertical lines in the array
Memory Architecture & Bounds
O(1) Iterative
O(1) 3 scalar registers
O(1) Maximum water integer
Boundary Best / Worst Cases
Pointer Invariant Transition Progression
Senior SWE Deconstruction & Hardware Caveats
Triggers: "two lines together with x-axis forms container", "maximize water container can contain". Bilateral boundary convergence with greedy bottleneck elimination.
. Naive pair checking is (TLE). Requires strictly linear time and space.
Moving both pointers simultaneously when heights are equal: moving either is safe since the limiting height is already bounded by both lines.