Largest Water Container
You get an array height. Each value is the height of a vertical wall. The walls stand in a row, and wall i is at position i.
Choose two different walls i < j. Together with the ground, they hold water. The water level cannot be higher than the shorter wall, so the amount of water is:
min(height[i], height[j]) * (j - i)
The walls between i and j do not matter. Return the largest amount of water that any pair of walls can hold.
Hint
Start with one pointer at each end. The amount is limited by the shorter wall. Moving the taller wall inward can never help, so always move the shorter one. This gives O(n) time.
Examples
Example 1
- Input:
- [3,9,2,6,1,8,4]
- Output:
- 32
Take the walls at positions 1 (height 9) and 5 (height 8). The water is min(9, 8) * (5 - 1) = 8 * 4 = 32. No other pair holds more.
Example 2
- Input:
- [5,5]
- Output:
- 5
There is only one pair. The water is min(5, 5) * (1 - 0) = 5.
Example 3
- Input:
- [0,7,0,7,0]
- Output:
- 14
The two walls of height 7 are at positions 1 and 3, so the water is 7 * 2 = 14. Any pair with a zero-height wall holds nothing.
Constraints
2 <= height.length <= 400 <= height[i] <= 100
Run checks your code against the 3 examples. Submit checks it against all 253 tests and needs a free account. You can also try ideas in the free JavaScript or Python compiler.