×=
Legend blue box = water between walls l and r · dashed = best container so far · grey walls are ruled out
public int maxArea(int[] height) { int l = 0; int r = height.length - 1; int res = 0; while (l < r) { int area = (r - l) * Math.min(height[l], height[r]); res = Math.max(res, area); if (height[l] < height[r]) { l++; // the shorter wall cannot do better } else { r--; } } return res;}
- l
- —
- r
- —
- area
- —
- res
- 0
Why it works
- Brute force tries every pair of walls: n(n − 1)/2 areas, O(n²).
- The shorter wall is finished. Start with the widest container. Any other container that keeps the shorter wall is narrower, and its water level is still capped by that wall, so it holds less. Drop the shorter wall and lose nothing.
- Why O(n): each step rules out one wall for good, so the pointers meet after n − 1 steps. Two indices and the best area are the only memory.
- Pitfall: moving the taller wall is wrong: the width shrinks while the level stays capped by the same short wall. And the water level is the shorter wall, not the average.
- Ties: when both walls are equal, moving either one is safe. Neither can pair with anything inside for more water than now.
- Related: Trapping Rain Water also walks two pointers inward from the shorter side, but sums water over every column.