Widest container
Pick two walls that hold the most water. About 12 minutes.
What can you rule out?
Checking every pair of walls takes about n × n steps. Every fast idea in this topic worked by ruling things out instead: the two fingers dropped a number for good, the window dropped the left end.
So ask: which walls could never be part of a better container than the best you've found? Start with the widest possible pair, the two ends, and think about which one can go.
- best
- 8
- water
- 8
The widest pair first: the water rises only as high as the shorter wall (1), across a width of 8, so it holds 8. The 1 can't do better with any closer partner, so drop it.
The two end walls are 3 tall (left) and 8 tall (right). Which one can you safely drop?
- AThe 3 on the left
- BThe 8 on the right
- CBoth
Show the answer
The 3 on the left. Any other partner for the 3 is closer, and the water can never rise above 3.
Widest container
You get the heights of walls standing in a row, one per position. Two walls and the ground between them form a container holding min(height i, height j) × (j − i) water. Return the most water any two walls can hold.
heights = [1, 8, 6, 2, 5, 4, 8, 3, 7] → 49
2 ≤ n ≤ 1,000,000 · 0 ≤ each height ≤ 10^6 · return a long