ASAPUtils
The signal
Maximise a quantity over pairs, where the quantity depends on both the distance between them and their values. Trying every pair is O(n²). The two-pointer escape works whenever you can prove that one side of the current pair is safe to discard — which is exactly what happens here.
Note this is one of the rare two-pointer problems where you must not sort: the indices are the width.
Approach ladder
1. Brute force — O(n²)
Every pair, min(h[i], h[j]) * (j - i). Correct, too slow at n ≤ 10⁵.
2. Start from the widest pair
Put l = 0, r = n-1. This is the maximum possible width. From here width only decreases, so
any improvement has to come from height.
3. The exchange argument (this is the whole problem)
Suppose h[l] < h[r]. Consider every remaining pair that still uses l. Each one:
- has width ≤ the current width (because
rcan only move left), and - has height ≤
h[l](because the shorter wall caps it, andh[l]is already the shorter).
So every such pair has area ≤ the one you just measured. l can be discarded with nothing lost.
Move it. Symmetrically if h[r] is the shorter.
That paragraph is what an interviewer wants to hear. The code is four lines.
4. Optimal — O(n)
int maxArea(vector<int>& h) {
int l = 0, r = h.size() - 1, best = 0;
while (l < r) {
best = max(best, min(h[l], h[r]) * (r - l));
if (h[l] < h[r]) l++;
else r--;
}
return best;
}
function maxArea(h) {
let l = 0, r = h.length - 1, best = 0;
while (l < r) {
best = Math.max(best, Math.min(h[l], h[r]) * (r - l));
if (h[l] < h[r]) l++;
else r--;
}
return best;
}
Complexity
- Time O(n) — one pointer moves every iteration and they meet once.
- Space O(1).
Traps
- Using
maxinstead ofminfor the height. Water spills over the shorter wall. - Moving the taller pointer. Symmetric-looking, completely wrong: you can discard the answer.
- Ties. When
h[l] === h[r]either move is safe — both walls cap at the same height and the width shrinks either way. Don’t overthink it. - Computing the area after moving. Measure first, then move.
Blank re-solve prompt
Given an array of heights, return the maximum water two lines can hold. O(n), and be ready to justify the pointer move in one sentence.