Container With Most Water

Problem Statement

You are given an array height where height[i] is the height of a vertical line drawn at position i. Pick two lines that, together with the x-axis, form a container. Return the maximum amount of water it can hold.

Input:  height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
Output: 49
Why:    lines at index 1 (height 8) and index 8 (height 7)
        width  = 8 - 1 = 7
        height = min(8, 7) = 7
        area   = 7 × 7 = 49

Intuition

Brute force checks all n × (n-1) / 2 pairs — O(n²).

To do better, start from the widest possible container: left = 0, right = n - 1. This maximises the width. Any other pair is narrower, so it can only win by being taller.

Now the crucial question: which pointer should move inward?

That argument is what makes the algorithm correct rather than just plausible. Each step permanently eliminates one line, so n steps suffice.

Real-world analogy

Two people hold a sheet between them to catch water. The sheet fills only up to the lower hand. Asking the taller person to step closer helps nobody — the water level is set by the lower hand. The only hope of improvement is to replace the lower hand.

Approach

Watch it run

Solution

def max_area(height: list[int]) -> int:
    """Largest area of water between any two vertical lines."""
    left, right = 0, len(height) - 1
    best = 0

    while left < right:
        # Water spills over the shorter wall, so it caps the height.
        area = (right - left) * min(height[left], height[right])
        best = max(best, area)

        # Moving the taller line can never help — see the proof above.
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1

    return best

Complexity Analysis

• Time — the pointers only ever move toward each other, so the loop runs at most n - 1 times. Brute force is O(n²): at n = 10⁵, that is 100,000 steps versus 5 billion.
• Space — two indices and a running maximum.

Edge Cases

Related Problems

• Trapping Rain Water — the same two-pointer setup, but summing water above every bar
• Merge Sorted Array — two pointers draining rather than converging
• Valid Palindrome — the simplest converging-pointer problem