Container With Most Water

Given an array height, where each element represents the height of a vertical line at that index, choose two lines that form a container holding the most water. Return the maximum area.

Brute force is O(n^2). A two-pointer approach works in O(n).

Why this is worth learning

The discard is about a fixed shorter endpoint: its current widest remaining partner is already the best area that endpoint can possibly achieve.

Before coding: one-minute experiment

Why must [1,8,6,2,5,4,8,3,7] move the left pointer at its first step?

Function signature

func MaxArea(height []int) int

Inputs / outputs

• height: non-negative integers.
• Return: the maximum container area.

Example

height = [1,8,6,2,5,4,8,3,7]
Output: 49

Constraints

• 2 <= len(height) <= 100_000
• 0 <= height[i] <= 1_000_000_000

Core idea (near-solution)

Use two pointers at the ends. The area is limited by the shorter line. Moving the taller line cannot increase area because the width shrinks and the height limit stays the same or decreases. Therefore, always move the pointer at the shorter line.

Invariant: any container using a line outside [l, r] cannot beat the best area found so far.

Algorithm (step-by-step)

1. Set l = 0, r = len(height)-1, best = 0.
2. While l < r:
   • Compute area = min(height[l], height[r]) * (r - l).
   • Update best.
   • Move the pointer at the shorter line inward.
3. Return best.

Correctness sketch

At endpoints l and r, suppose height[l]<=height[r]. Any remaining pair (l,j) with j<r has smaller width and height bounded by height[l], so its area is at most the area just evaluated. Thus every pair involving l is either previously discarded or cannot improve best, and l may be removed. The symmetric argument applies when r is shorter. Equal heights allow either endpoint to be discarded. Maintaining the best evaluated area and this domination invariant leaves no potentially superior pair outside the active interval. When fewer than two positions remain, best is globally maximal.

Trace (hand walkthrough)

Example input:
height = [1,8,6,2,5,4,8,3,7]
Output: 49

Walk:
- l=0,r=8: area=min(1,7)*8=8, move l
- l=1,r=8: area=min(8,7)*7=49 (best), move r
- r=7: area=min(8,3)*6=18 -> best stays 49

Pitfalls to avoid

• Moving the taller pointer (can skip the optimal pair).
• Overflow when computing the area (use 64-bit if needed).

Debugging lens

Compare against all pairs on short arrays. A wrong implementation that always moves the taller side can still pass symmetric examples. Include zero heights and a large 64-bit area.

Complexity

• Time: O(n)
• Extra space: O(1)

Implementation notes (Go)

• Use int but cast to int64 if you expect large products.

Contract precision

The published bounds can produce an area near 10^14. The provided int signature therefore requires a 64-bit Go target for the full stated domain; casting after an overflowing multiplication would not repair it.

Reconstruction checkpoint

Why must [1,8,6,2,5,4,8,3,7] move the left pointer at its first step?

Return to Two Pointers · Module quiz