Container With Most Water

Interview Prep

Warm-upTwo Pointersarraystwo-pointers

The problem

Given an array h of non-negative heights, treat each element as a vertical line of that height on the x-axis. Pick two lines that, together with the x-axis, form a container holding the most water. Return that area.

Pattern: two-pointer convergence

Start with the widest possible container: indices 0 and n−1. The area is (width) · min(h[lo], h[hi]). Now the key insight: moving the taller line inward can never help — width shrinks, and the smaller line still caps the height. So we must move the shorter line inward; that's the only move that has a chance of improving the area, because the new line might be taller and unlock the partner's height.

Each step eliminates one line from consideration, so the loop runs at most n − 1 times: O(n) total.

Brute force

def max_area_brute(h: list[int]) -> int:
    n, best = len(h), 0
    for i in range(n):
        for j in range(i + 1, n):
            best = max(best, (j - i) * min(h[i], h[j]))
    return best

Optimal: two pointers in O(n)

def max_area(h: list[int]) -> int:
    lo, hi = 0, len(h) - 1
    best = 0
    while lo < hi:
        best = max(best, (hi - lo) * min(h[lo], h[hi]))
        if h[lo] < h[hi]:    # only chance to improve is by moving the shorter line
            lo += 1
        else:
            hi -= 1
    return best

Trace

h = [1, 8, 6, 2, 5, 4, 8, 3, 7]

lo=0, hi=8: (8-0)*min(1,7) = 8*1 = 8.  h[lo]<h[hi], lo++.  best=8
lo=1, hi=8: (8-1)*min(8,7) = 7*7 = 49. h[lo]>=h[hi], hi--. best=49
lo=1, hi=7: (7-1)*min(8,3) = 6*3 = 18. hi--.              best=49
lo=1, hi=6: (6-1)*min(8,8) = 5*8 = 40. hi--.              best=49
lo=1, hi=5: (5-1)*min(8,4) = 4*4 = 16. hi--.              best=49
lo=1, hi=4: (4-1)*min(8,5) = 3*5 = 15. hi--.              best=49
lo=1, hi=3: (3-1)*min(8,2) = 2*2 = 4.  hi--.              best=49
lo=1, hi=2: (2-1)*min(8,6) = 1*6 = 6.  hi--, lo>=hi stop. best=49

return 49

Complexity

Why the greedy move is provably safe

Suppose h[lo] < h[hi]. The current area is bounded by (hi − lo) · h[lo]. If we move hi inward, the new width is smaller, and the new height is still capped by h[lo] (since h[lo] is the bottleneck). So no future configuration with lo still in play can beat this one — we can safely discard lo. A formal correctness proof of the two-pointer sweep.

Variations worth knowing