Two Pointers · LC #11
Container With Most Water
Two pointers start at the widest span and greedily move the shorter wall inward - the only move that can possibly improve area. Classic greedy proof for two-pointer correctness.
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
Given `n` heights representing vertical lines, find two lines that together form a container holding the most water. Return the maximum amount of water the container can store.
Sample I/O
Input: height = [1,8,6,2,5,4,8,3,7] Output: 49 (lines at index 1 and 8: min(8,7) * 7 = 49) Input: height = [1,1] Output: 1
Time: O(n) · Space: O(1)
Intuition
How to Think About It
Intuition
Area = min(left, right) × width. Starting at maximum width, the only way to possibly increase area is to find a taller wall. The shorter wall limits the current area, so moving it inward is the only candidate - moving the taller wall can only decrease or maintain the height cap while strictly reducing width, which is provably worse.
Core Concept
Place `l=0`, `r=n-1`. Compute area = `min(h[l], h[r]) * (r - l)`. Update max. Move the pointer on the shorter side inward. Repeat until `l >= r`. The greedy argument: skipping any pair by moving the taller side provably cannot miss the optimum.
When to use
Two-variable maximisation on a 1D array where the constraint depends on both endpoints. Also useful as a mental model for "when is a greedy two-pointer provably correct?"
When NOT to use
When you need to enumerate ALL pairs with area ≥ threshold (brute force or binary-search variant needed). When the problem has a 2D structure.
Key Insights
What to Know Cold
- Area is bounded by the SHORTER of the two walls - moving the taller wall inward never helps.
- The greedy choice is provably optimal: at each step we discard pairs that cannot be the answer.
- Width strictly decreases each step, so the algorithm terminates in exactly n-1 iterations.
- This is NOT a sliding-window problem - the window size is not fixed and the inner content is irrelevant.
- Contrast with Trapping Rain Water: that problem accumulates water at every cell, not between two chosen endpoints.
1 example
Worked Examples
Greedy Two-Pointer Area Maximisation
height=[1,8,6,2,5,4,8,3,7]. Start with widest span, always move the shorter pointer.
l=0 (h=1), r=8 (h=7). Area=min(1,7)*8=8. Move l (shorter). Continue until l=1 (h=8), r=8 (h=7): area=min(8,7)*7=49. That is the max.
def maxArea(height: list[int]) -> int:
l, r, best = 0, len(height) - 1, 0
while l < r:
best = max(best, min(height[l], height[r]) * (r - l))
if height[l] < height[r]:
l += 1
else:
r -= 1
return bestClassic greedy two-pointer proof: you can rigorously argue the algorithm never skips the optimal pair - a must-explain in FAANG coding interviews.