Container With Most Water

Check every pair

Treat each line as a possible left wall and pair it with every line to its right. The formula gives the area directly, so keep the largest result seen.

def max_area(height: list[int]) -> int:
    best = 0
    for left in range(len(height) - 1):
        for right in range(left + 1, len(height)):
            width = right - left
            water_height = min(height[left], height[right])
            best = max(best, width * water_height)
    return best

Time O(n²) — every pair gets measured. Space O(1) — only the running maximum and loop positions are stored.

Converging pointers

Start with the widest possible container: left = 0, right = n - 1. After measuring it, every future container is narrower. The only possible compensation is a taller limiting wall.

Suppose the left wall is shorter. Keeping it while moving right inward can't help: the width shrinks, and the water level can never rise above that unchanged left wall. So every pair between this left and a smaller right is already beaten by the pair you just measured. Retire left. The same argument works symmetrically when the right wall is shorter.

def max_area(height: list[int]) -> int:
    left, right = 0, len(height) - 1
    best = 0
 
    while left < right:
        width = right - left
        water_height = min(height[left], height[right])
        best = max(best, width * water_height)
 
        if height[left] <= height[right]:
            left += 1
        else:
            right -= 1
 
    return best

Time O(n) — one pointer moves inward on every step, so there are at most n - 1 measurements. Space O(1).

This isn't a lucky greedy move. The shorter wall is a bottleneck — the part that caps the whole result — and the width only gets worse. That proof is what makes one discarded pointer safe.