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).

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

• Invariant: any container using a line outside [l, r] cannot beat the best area found so far.
• Each step moves at least one pointer, shrinking the remaining search space.
• The invariant ensures elements outside the active window are already handled correctly.
• When pointers meet or cross, all candidates have been considered.

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).

Complexity

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

Implementation notes (Go)

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