Container With Most Water

Statement

Given an integer array height where height[i] represents the height of a vertical line at index i, find two lines that together with the x-axis form a container holding the most water. Return the maximum amount of water the container can store.

Examples

height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
→ 49      (indices 1 and 8, heights 8 and 7, width 7 → min(8,7) × 7 = 49)

height = [1, 1]
→ 1       (single rectangle of width 1 and height 1)

height = [4, 3, 2, 1, 4]
→ 16      (indices 0 and 4, both height 4, width 4)

Constraints

• 2 ≤ len(height) ≤ 10⁵
• 0 ≤ height[i] ≤ 10⁴
• You cannot tilt the container; the water level is bounded by the shorter line.

What this problem is really testing

Whether you can spot a two-pointer optimisation that beats the obvious O(n²) brute force. The trick is that at every step, advancing the shorter side is the only direction that could improve the answer, shrinking the width while keeping the shorter height fixed can only decrease the area. That insight turns a quadratic algorithm into a linear one.