Container With Most Water

Problem

Given n non-negative integers representing vertical line heights at positions 0..n-1, find the two lines that together with the x-axis form a container holding the most water.

Approach

Start with two pointers at the outermost lines. The area is limited by the shorter line, so always move the pointer at the shorter side inward to try for a taller line.

When to Use

Maximizing area/product with two boundaries — shrink from both ends, always moving the weaker constraint inward. Keywords: "maximize rectangle", "widest pair", "two-boundary optimization".

Complexity

Time	O(n)
Space	O(1)

Source

"""Container With Most Water — max area between two vertical lines.

Problem:
    Given n non-negative integers representing vertical line heights at
    positions 0..n-1, find the two lines that together with the x-axis
    form a container holding the most water.

Approach:
    Start with two pointers at the outermost lines. The area is limited
    by the shorter line, so always move the pointer at the shorter side
    inward to try for a taller line.

When to use:
    Maximizing area/product with two boundaries — shrink from both ends,
    always moving the weaker constraint inward.
    Keywords: "maximize rectangle", "widest pair", "two-boundary optimization".

Complexity:
    Time:  O(n)
    Space: O(1)
"""

from collections.abc import Sequence


def max_area(height: Sequence[int]) -> int:
    """Return the maximum water area between any two lines in *height*.

    >>> max_area([1, 8, 6, 2, 5, 4, 8, 3, 7])
    49
    """
    lo, hi = 0, len(height) - 1
    best = 0

    while lo < hi:
        area = min(height[lo], height[hi]) * (hi - lo)
        best = max(best, area)
        # the shorter line caps the area no matter what — moving it inward is
        # the only move that can possibly find something taller
        if height[lo] < height[hi]:
            lo += 1
        else:
            hi -= 1

    return best