Container With Most Water

Problem

Given an integer array height where each element represents a vertical line of that height, find two lines that, together with the x-axis, form a container that holds the most water. Return the maximum area.

Example: height = [1, 8, 6, 2, 5, 4, 8, 3, 7] → 49 (lines at index 1 and 8, width 7 × height 7 = 49).

What the interviewer is testing

• Can you improve from O(n²) to O(n) with two pointers?
• Do you correctly argue why moving the shorter pointer is safe?
• Can you explain the greedy insight without hand-waving?

Brute-force solution — O(n²) time, O(1) space

Try every pair. Correct, but the interviewer will always ask you to beat it.

def max_area(height):
    best = 0
    for i in range(len(height)):
        for j in range(i + 1, len(height)):
            best = max(best, (j - i) * min(height[i], height[j]))
    return best

Optimal solution — O(n) time, O(1) space (two pointers)

Start with the widest possible container: left = 0, right = n − 1. The area is (right − left) × min(h[left], h[right]). Every step, move the pointer at the shorter line inward.

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

Why moving the shorter side is safe

This is the whole interview. Say it precisely:

"The area is width × min(h[left], h[right]). If I move the taller side inward, width shrinks and min doesn't grow — the area can only get worse. So any container with the current shorter side is bounded above by the area we just computed. Moving the shorter side is the only move that can possibly find a better answer."

Complexity — what to say out loud

"Time O(n) — each pointer moves inward at most n/2 times. Space O(1)."

Edge cases the interviewer will ask about

• Fewer than 2 lines — return 0.
• All zeros — return 0.
• Two equal heights — the tie-break in the pointer move doesn't matter for correctness.
• Monotonically increasing heights — the pointer keeps moving left inward; the best is often near the end.

Common follow-ups

• "Trapping rain water." — Different problem: sum of trapped water above all bars, not just between two. Two-pointer variant works with a running max on each side.
• "What if we can pick 3 lines to form a container?" — Trickier; usually not asked in the same interview, but the setup uses similar "shortest side dominates" reasoning.

How to verbalize your answer

"Two pointers, one at each end. The current area is width times the shorter height. Moving the taller side never helps — width shrinks and min can't grow. So I always advance the shorter side, and track the max. O(n) time, O(1) space."