11. Container With Most Water
You are given an array of non-negative integers height, where height[i] is the height of a thin vertical wall standing at position i on the x-axis.
Choose two of the walls. Together with the x-axis they form an open-topped tank: its width is the distance between the two positions, and its water level is capped by the shorter wall — anything above that spills out. Return the largest amount of water any such tank can hold. In other words, return the maximum of (j - i) * min(height[i], height[j]) over all pairs i < j.
The walls have no thickness, and the tank cannot be tilted.
Example 1:
Input: height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
Output: 49
Explanation: The walls at indices 1 and 8 have heights 8 and 7. Width is 8 - 1 = 7 and the water level is min(8, 7) = 7, so the tank holds 7 × 7 = 49. No other pair does better.
Example 2:
Input: height = [1, 1]
Output: 1
Explanation: Only one pair exists: width 1, level min(1, 1) = 1, area 1.
Constraints:
- 2 ≤ height.length ≤ 10⁵
- 0 ≤ height[i] ≤ 10⁴
Hints:
Checking every pair of walls is a correct O(n²) baseline. Notice that a pair's area depends only on its width and its shorter wall.
Start with the widest tank possible — the two outermost walls — and shrink inward. If you move the taller wall's pointer, the width drops and the level cannot rise, so the area can only get worse. Which pointer is the only one worth moving?
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
Expected output: 49