Container With Most Water
MediumTwo Pointers · NVIDIA
You are given an integer array height of length n. Picture n vertical lines: line i stands at x-position i and is height[i] tall.
Pick two different lines i < j. Together with the x-axis they form a container that holds (j - i) * min(height[i], height[j]) units of water (the water level cannot rise above the shorter line, and the container cannot be tilted).
Return the maximum amount of water any such container can hold.
Example 1
- Input:
- height = [3,1,2,4,5]
- Output:
- 12
- Explanation
- The best pair is the two ends, 4 apart with a shorter side of 3, giving 12. The two tallest lines are adjacent, so they are only 1 apart and give 4.
Example 2
- Input:
- height = [2,7,3,1,6,2]
- Output:
- 18
- Explanation
- Heights 7 (index 1) and 6 (index 4) are 3 apart, giving 3 × 6 = 18. The outermost pair is wider (5 apart) but its shorter line is only 2, giving 10.
Example 3
- Input:
- height = [0,8,0,8]
- Output:
- 16
- Explanation
- The two lines of height 8 (indices 1 and 3) are 2 apart, giving 2 × 8 = 16. Any container using a 0-height line holds nothing.
Constraints
2 <= height.length <= 10^50 <= height[i] <= 10^4