JustPaste.it

Container With Most Water: The One-Line Proof Behind the Two Pointers

Container With Most Water is easy to code and easy to get wrong in the explanation. Interviewers often ask why moving the shorter pointer is safe. Here is the argument in plain words.

The algorithm

Start with lo at the left end and hi at the right end. The area is min(h[lo], h[hi]) times (hi - lo). Record it, then move whichever pointer is shorter inward.

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

Why it is safe

Suppose h[lo] is the shorter side. Any container that keeps lo and uses some hi' < hi is narrower, and its height is still capped by h[lo]. So every remaining pair that includes lo is no better than the one we just measured. We can discard lo forever. That is the whole proof, and saying it in two sentences is what separates a memorised answer from an understood one.

Common mistakes

Moving the taller pointer, or moving both when heights are equal without justifying it (moving either is fine when they are equal). Also, do not confuse this with Trapping Rain Water, which sums water over every bar rather than picking one pair.

Complexity is O(n) time and O(1) space. I am on the team behind Linkjob.ai, which builds tools for practising explanations like this one. Disclosure: I help build Linkjob AI.