Container with most water

You get an array of non-negative integers where heights[i] is the height of a vertical line at position i. Pick two lines that, with the x-axis, form a container, and return the most water a container can hold. The water level is set by the shorter line, and the width is the distance between the two positions.

Interface

Unless you agree on a different interface with the interviewer, assume:

• max_area(heights: list[int]) -> int — 0 when there are fewer than two lines.

Example

max_area([1, 8, 6, 2, 5, 4, 8, 3, 7])  ->  49    # lines at 1 and 8: width 7, height 7
max_area([4, 3, 2, 1, 4])              ->  16    # the two 4s, width 4
max_area([1, 1])                       ->  1
max_area([5])                          ->  0

Constraints

• 0 <= len(heights) <= 10^5; 0 <= heights[i] <= 10^4.

Clarifying questions

• Can the array have fewer than two lines?
• Do the lines between the chosen two matter? (They don't.)
• Do you want the area or the two positions?

What a strong answer covers

• Brute force over all pairs is O(n^2); the two-pointer sweep is O(n): start at both ends, record the area, and move the pointer at the shorter line inward.
• Why moving the shorter side is safe: any container that keeps it is narrower and no taller, so none beats the area just recorded.
• Ties: moving either pointer is fine.
• O(1) extra space; tests with the examples and with all-equal heights.

Follow-ups

• Trapping rain water: how much water the whole elevation map holds after rain, in O(n) time and O(1) space.
• Return the pair of positions with the best area.