Container With Most Water
You are given an array of vertical line heights at unit-spaced positions. Pick two lines so that, together with the x-axis, they enclose the largest possible amount of water. Return that area (width × shorter height).
- 2 ≤ n ≤ 10^5
- 0 ≤ height[i] ≤ 10^4
- Answer depends on the pair (width × min height)
- Starting from the widest span, only moving the *shorter* side can improve
- Opposite-direction pointers
When order gives you a way to decide which of two ends to move, you can replace an O(n^2) double loop by a single pass. Opposite-direction pointers exploit sortedness (move the side that must change); same-direction pointers maintain a "written so far" prefix for in-place compaction.
Start with l = 0 and r = n - 1, the widest container. Compute its area and then move whichever pointer has the shorter line inward. Keeping the shorter line while narrowing can never increase the area because the height is capped by it, so discarding it loses no candidate. Continue until the pointers meet and return the maximum area seen.
- Brute force over all pairs is O(n^2); no faster exact alternative is needed.