Container with most water

Question

You're given n vertical lines; line i has height height[i] and stands at x-coordinate i. Choose two lines that, together with the x-axis, contain the most water. The water level is set by the shorter line, so the area between lines i and j is (j - i)\cdot\min(hi, hj). Return the maximum area. Aim for O(n), and be ready to justify why your pointer move is safe.

Accepted Answer

Start with pointers at both ends and repeatedly move the pointer at the shorter line inward. Why is that safe? The current area is capped by the shorter line. Any container keeping the shorter line but narrower can't beat the current one: its width is smaller and its height is still capped by that same short line. So the shorter line is finished, no better container uses it, and discarding it loses nothing. Each step retires one line, so the scan is linear. On the example, the first area is 8 \cdot \min(1,7) = 8; the left pointer (height 1) moves, the next area is 7 \cdot \min(8,7) = 49, and …

Container with most water

Your answer

More Coding questions