Frontend Beauty
ESC

Type to search the knowledge base.

Container With Most Water

Two pointers on heights for max water area — why you move the shorter side, brute O(n²) vs O(n), and edge cases.

intermediate3 min read
  • dsa
  • two-pointers
  • interview
  • Google
  • Meta
  • Amazon

The problem

Array height[i] = vertical line at x = i. Choose two lines so the container holds the most water:
area = min(height[i], height[j]) * (j - i).

height = [1,8,6,2,5,4,8,3,7]
max area = 49  // indices 1 and 8: min(8,7)*7

Brute force

function maxAreaBrute(height: number[]): number {
  let best = 0;
  for (let i = 0; i < height.length; i++) {
    for (let j = i + 1; j < height.length; j++) {
      best = Math.max(best, Math.min(height[i], height[j]) * (j - i));
    }
  }
  return best;
}
Time O(n²)
Space O(1)

Optimal: two pointers from outside

Start lo = 0, hi = n-1 (max width). Area uses the shorter height. To maybe improve, you must move the shorter pointer inward — moving the taller can only shrink width while the min is still limited by the short side.

function maxArea(height: number[]): number {
  let lo = 0;
  let hi = height.length - 1;
  let best = 0;

  while (lo < hi) {
    const h = Math.min(height[lo], height[hi]);
    best = Math.max(best, h * (hi - lo));
    if (height[lo] <= height[hi]) lo++;
    else hi--;
  }

  return best;
}
Time O(n)
Space O(1)

Intuition check

If height[lo] < height[hi], every pair (lo, k) for k < hi has width smaller and height ≤ height[lo], so ≤ current candidate involving this short bar — you can discard this lo. Symmetric for hi.

Edge cases

  • Two elements only
  • All equal heights → area = h * (n-1)
  • Strictly increasing / decreasing
  • Zeros

Common mistakes

  • Moving both pointers
  • Moving the taller side first
  • Using max height instead of min
  • Confusing with trapping rain water (different problem)

Interview delivery

  1. Area formula.
  2. Brute, then two pointers + why move shorter.
  3. Trace sample.
  4. O(n)/O(1).

Mental model

Width starts maximal. Height is gated by the shorter line. The only way to beat the current area is a taller limiting line, so discard the shorter index. This is a correctness argument, not a heuristic — every discarded pointer is dominated for future pairs involving that short bar at current or smaller widths.

Contrast: trapping rain water

Trapping rain water asks how much water sits above each index given taller bars on both sides. Different structure (prefix/suffix max or two pointers with left_max/right_max). Don’t paste container code into trapping.

Out-loud answer

“Max area between two lines. Brute all pairs O(n²). Optimal two pointers from ends; compute area; move the shorter side. O(n) time O(1) space. Mention unimodal intuition only if asked.”

Further reading