Container With Most Water

Problem

You are given an array height of n non-negative integers. Picture the i-th value as a vertical wall of that height standing at x-coordinate i. Choose two walls; together with the x-axis they form an open-top container whose width is the distance between the walls and whose water level is limited by the shorter wall. Return the largest volume of water any pair of walls can hold.

• n is between 2 and 100,000.
• Heights are integers from 0 to 5,000.

Examples

• height = [3, 9, 2, 7, 6, 1, 8] → 40. The walls at index 1 (height 9) and index 6 (height 8) are 5 apart; min(9, 8) * 5 = 40.
• height = [6, 6] → 6. A single pair: width 1, level 6.
• height = [5, 1, 1, 1, 6] → 20. The outermost walls give min(5, 6) * 4 = 20; every inner wall is too short to help.

Hints

1. Start with the widest possible container. What can you say about any narrower container that keeps the shorter of the two current walls?
2. Once you know one wall can never participate in a better answer, you can discard it forever.
3. Two pointers from both ends; at each step move the pointer at the shorter wall inward, tracking the best area seen.