Given an array of heights, find two lines that together with the x-axis form a container that holds the most water.
Place one pointer at the far left and one at the far right, track the best area seen so far, then always move the pointer sitting at the shorter height inward. Moving the taller side inward could only reduce width without any chance of gaining height, so it's never optimal — this greedy squeeze finds the answer in O(n).
How to think about it
Recognise the pattern
The signal is two-element selection + “maximise area/product”. Area here is min(height[left], height[right]) * (right - left). Two things are fighting each other: width shrinks as pointers converge, but height can grow. That tension — and the fact that there are exactly two endpoints — screams two-pointer.
Build the approach step by step
Brute force tries every pair (i, j). Area is min(h[i], h[j]) * (j - i). O(n²) time.
The insight (the key move): start with the widest possible container (left=0, right=n-1). To get a bigger area you’d need a taller minimum height — and you can only change that by moving a pointer. If you move the taller pointer inward, you’re guaranteed to make width smaller and height can only stay the same or decrease (because the shorter side still caps it). So moving the taller side is provably never helpful. Always move the shorter side — it’s the only pointer that has a chance of finding a taller wall.
Walk through [1, 8, 6, 2, 5, 4, 8, 3, 7]:
- left=0 (h=1), right=8 (h=7) → area = min(1,7)*8 = 8. Move left (shorter).
- left=1 (h=8), right=8 (h=7) → area = min(8,7)*7 = 49. Move right (shorter).
- left=1 (h=8), right=7 (h=3) → area = min(8,3)*6 = 18. Move right.
- … and so on. The best is 49.
Complexity
- Time — O(n): each pointer moves inward at most n steps combined.
- Space — O(1): only two pointers and a running best.