The widest, deepest container
MediumStuck?
Show a hintHide the hint
One index at each end. The water is the shorter height times the width, and moving the taller line inward can never help.
The idea behind this problem
Next in this lesson
How many triples add to zeroEach number is the height of a vertical line. Choose two lines so that they and the ground hold the most water. Return that amount.
The water held is the shorter of the two lines multiplied by the distance between them.
Worked example#
For [1, 8, 6, 2, 5, 4, 8, 3, 7], start with the two outermost lines and walk inward, always moving the shorter one:
| left | right | width | shorter height | water |
|---|---|---|---|---|
| 1 (pos 0) | 7 (pos 8) | 8 | 1 | 8 |
| 8 (pos 1) | 7 (pos 8) | 7 | 7 | 49 |
| 8 (pos 1) | 3 (pos 7) | 6 | 3 | 18 |
| 8 (pos 1) | 8 (pos 6) | 5 | 8 | 40 |
The best seen is 49.
Why move the shorter line: the water is capped by the shorter one, so moving the taller one inward can only reduce the width without ever raising the cap. Moving the shorter one is the only move that can possibly help, which is what lets you discard half the options at each step.
Constraints#
2 <= n <= 1000000 <= height[i] <= 10000
Input
height is a count then that many integers.
Output
The most water that can be held.
Examples
Input
9 1 8 6 2 5 4 8 3 7
Output
49
The 8 at position 1 and the 7 at position 8 are 7 apart, and the shorter is 7.
Input
2 1 1
Output
1
Two lines of height 1, one apart.
Input
5 4 3 2 1 4
Output
16
The two 4s at each end: width 4, height 4.
Something wrong with this problem? Report an issue
Ready to try it
Write your solution in C, C++, Java or Python and see every test case come back with the time and memory it took.
Free, and it stays free. No card.