Problem 8 · Two Pointers & Sliding Window

Container With Most Water

MediumClassic DSA & systems

01Problem

Given heights of vertical lines, find two lines that with the x-axis hold the most water and return that area.

02Key insight

Start with the widest pair and always move the shorter side inward: keeping the shorter line can never yield a larger area as width shrinks, so it is safely discarded.

03Solution

solution.pypython10 lines

def max_area(height: list[int]) -> int:
    lo, hi, best = 0, len(height) - 1, 0
    while lo < hi:
        h = min(height[lo], height[hi])
        best = max(best, h * (hi - lo))
        if height[lo] < height[hi]:
            lo += 1
        else:
            hi -= 1
    return best

Try it first.

TimeO(n)

SpaceO(1)

tests.py · 3 passing

tests.pypython3 lines

assert max_area([1,8,6,2,5,4,8,3,7]) == 49
assert max_area([1,1]) == 1
assert max_area([5]) == 0

04Staff-level follow-up

How do you convince a reviewer the greedy is correct? Exchange argument: every pair skipped when moving the shorter pointer has smaller width and height bounded by the same short line, so none beats the current area.