Container with the most water

Question

Given non-negative heights, each a vertical line at unit spacing, pick two of them so that the container formed with the x-axis holds the most water. The volume between lines l and r is min(height[l], height[r]) * (r - l).

height = [1,8,6,2,5,4,8,3,7]  ->  49

Return the maximum water a container can hold. Aim for $O(n)$ time and $O(1)$ space.

Accepted Answer

Start with the widest possible container, one pointer at each end, and shrink inward. The area is capped by the shorter of the two walls, so widening is impossible and the only hope of a bigger area is a taller wall. Moving the taller wall inward can never help: width drops and the height is still capped by the shorter wall. So always advance the pointer on the shorter side. Tracing [1,8,6,2,5,4,8,3,7]: the winning pair is the 8 at index 1 and the 7 at index 8, giving min(8,7) (8 - 1) = 7 7 = 49. Every other pair the pointers skip is provably no larger, because we only ever discard the wall t…

Container with the most water

Your answer

More Coding questions