#15 · Two Pointers

Container With Most Water

Given n vertical lines of given heights, pick two of them that together with the x-axis form a container holding the most water, and return that amount. (Area = distance between the lines × the shorter height.)

MediumLeetCode

Active
Found
Window
Visited
Rejected

Speed1×step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

Two pointers moving inward (greedy)

Start with the widest possible container (first and last line). Area is limited by the shorter line, so the only way a narrower container could be better is by replacing the SHORTER line. Move that pointer inward and repeat.

Memory layout

Two integers over one contiguous array, read sequentially from both ends: no allocation and good cache behaviour.

Operation	Cost
one step (measure + move)	O(1)
whole scan	O(n) (each pointer moves at most n times in total)
extra space	O(1)

Why it fits

Area = width × min(heightLeft, heightRight). Moving the taller pointer inward can only shrink the width without raising the limiting (shorter) height, so it can never improve the area; moving the shorter one is the only move that might.
This argument discards a whole row of candidate pairs at every step (all pairs that keep the shorter line and a narrower width), which is why n − 1 steps cover all n(n−1)/2 pairs.
The invariant (the optimal pair is always inside the current [left, right] range, or already measured) is what makes the greedy choice provably safe.

Why alternatives degrade

Check every pair:: O(n²) pairs; correct but about 5 × 10⁹ comparisons for n = 10⁵.
Sorting by height:: Destroys the positions, and width depends on position, so the problem is not solvable from sorted heights alone.
Monotonic stack / DP:: These fit "water trapped between bars" (Trapping Rain Water), a different problem; here no interior bar blocks the container.

Four approaches, from naive to production

1 · beginner

Check every pair

time O(n²)space O(1)

For each pair of lines compute width × shorter height and keep the maximum.

int maxArea(vector<int>& height) {
    int best = 0;
    int n = height.size();
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int area = min(height[i], height[j]) * (j - i);
            best = max(best, area);
        }
    }
    return best;
}

public int maxArea(int[] height) {
    int best = 0;
    int n = height.length;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int area = Math.min(height[i], height[j]) * (j - i);
            best = Math.max(best, area);
        }
    }
    return best;
}

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

function maxArea(height: number[]): number {
  let best = 0;
  for (let i = 0; i < height.length; i++) {
    for (let j = i + 1; j < height.length; j++) {
      const area = Math.min(height[i], height[j]) * (j - i);
      best = Math.max(best, area);
    }
  }
  return best;
}

Flaws & bottlenecks

n(n−1)/2 pairs: ~5 × 10⁹ for n = 10⁵, which times out.
No pruning: pairs that obviously cannot win (a short line with a small width) are still evaluated.
It re-measures the same shorter line against many partners without exploiting how area depends on the minimum.

Interviewer cross-questions

Can you do better than O(n²)?

Say: Yes: start with the widest pair and always discard the shorter line. Any pair that keeps that line and shrinks the width is dominated, so one pointer move eliminates a whole group of candidates, giving O(n).

Is there a cheap pruning without a new idea?

Say: An upper bound helps: area ≤ height[i] × (j − i). Scanning j from far to near, once that bound drops below the current best, the rest of the row cannot win and you can stop (the intermediate approach).

What are the edge cases?

Say: n = 2 (only one pair), all-equal heights (widest pair wins), heights containing 0, and strictly increasing or decreasing heights.

2 · intermediate

Pairs with an early-exit bound

time O(n²) worst casespace O(1)

Scan the right end from far to near for each left line, and stop as soon as height[i] × width can no longer beat the best so far.

int maxArea(vector<int>& height) {
    int best = 0;
    int n = height.size();
    for (int i = 0; i < n; i++) {
        for (int j = n - 1; j > i; j--) {
            if (height[i] * (j - i) <= best) break;
            best = max(best, min(height[i], height[j]) * (j - i));
        }
    }
    return best;
}

public int maxArea(int[] height) {
    int best = 0;
    int n = height.length;
    for (int i = 0; i < n; i++) {
        for (int j = n - 1; j > i; j--) {
            if (height[i] * (j - i) <= best) break;
            best = Math.max(best, Math.min(height[i], height[j]) * (j - i));
        }
    }
    return best;
}

def max_area(height: list[int]) -> int:
    best = 0
    n = len(height)
    for i in range(n):
        for j in range(n - 1, i, -1):
            if height[i] * (j - i) <= best: break
            best = max(best, min(height[i], height[j]) * (j - i))
    return best

function maxArea(height: number[]): number {
  let best = 0;
  for (let i = 0; i < height.length; i++) {
    for (let j = height.length - 1; j > i; j--) {
      if (height[i] * (j - i) <= best) break;
      best = Math.max(best, Math.min(height[i], height[j]) * (j - i));
    }
  }
  return best;
}

Flaws & bottlenecks

The bound only helps once a decent best is known; the first rows still scan many pairs.
Adversarial inputs (for example, increasing heights) defeat the pruning and stay quadratic.
It is a heuristic speed-up, not an algorithmic improvement.

Interviewer cross-questions

Why is the break correct?

Say: For fixed i, area ≤ height[i] × (j − i) because the shorter height is at most height[i]. j only decreases, so the width only shrinks; once the bound is ≤ best, every remaining j in this row has an even smaller bound.

Why scan j from far to near?

Say: The widest containers come first, so the bound shrinks monotonically and the break condition, once true, stays true for the rest of the row.

When does this beat the plain brute force?

Say: On random data it prunes most of the inner loop after a good best is found. Worst-case inputs show no gain, so it is a constant-factor optimization, not a different complexity class.

3 · advanced

Two pointers: move the shorter side

time O(n)space O(1)

Start with the widest container. Measure it, then move whichever pointer is at the shorter line inward, because only that move can increase the limiting height.

int maxArea(vector<int>& height) {
    int left = 0;
    int right = (int)height.size() - 1;
    int best = 0;
    while (left < right) {
        int area = min(height[left], height[right]) * (right - left);
        best = max(best, area);
        if (height[left] < height[right]) left++;
        else right--;
    }
    return best;
}

public int maxArea(int[] height) {
    int left = 0;
    int right = height.length - 1;
    int best = 0;
    while (left < right) {
        int area = Math.min(height[left], height[right]) * (right - left);
        best = Math.max(best, area);
        if (height[left] < height[right]) left++;
        else right--;
    }
    return best;
}

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

function maxArea(height: number[]): number {
  let left = 0;
  let right = height.length - 1;
  let best = 0;
  while (left < right) {
    const area = Math.min(height[left], height[right]) * (right - left);
    best = Math.max(best, area);
    if (height[left] < height[right]) left++;
    else right--;
  }
  return best;
}

Flaws & bottlenecks

The correctness argument (why discarding the shorter line is safe) is non-obvious and must be explained, not just coded.
When both lines are equal, either pointer may move; the choice affects the path but not the answer.
It still measures one container per step even when the next several steps cannot improve on it.

Interviewer cross-questions

Prove that moving the shorter pointer never loses the optimum.

Say: Suppose height[left] ≤ height[right]. Any container using left with a right′ < right has width smaller than the current one and a height at most height[left], so its area is at most the area we just measured. So left cannot belong to a better container than the current one, and can be discarded. Symmetric for right.

What if the heights are equal?

Say: Moving either pointer is safe: both lines are limiting and neither can beat the area just measured with a narrower container. A common tie-break is to move right (the else branch).

How does this generalize?

Say: It is the standard "two pointers from the ends with a monotone argument" template, shared with Two Sum II and 3Sum, and it applies whenever discarding one end provably removes only dominated candidates.

4 · expert

Two pointers that skip dominated lines in bulk

time O(n)space O(1)

Same greedy, but after measuring, skip over every line on the limiting side that is no taller than the current limiting height, instead of re-measuring each one.

long long maxArea(const vector<int>& height) {
    int left = 0;
    int right = (int)height.size() - 1;
    long long best = 0;
    while (left < right) {
        int hl = height[left];
        int hr = height[right];
        int h = hl < hr ? hl : hr;
        long long area = (long long)h * (right - left);
        if (area > best) best = area;
        if (hl < hr) {
            while (left < right && height[left] <= h) left++;
        } else {
            while (left < right && height[right] <= h) right--;
        }
    }
    return best;
}

public long maxArea(int[] height) {
    int left = 0;
    int right = height.length - 1;
    long best = 0;
    while (left < right) {
        int hl = height[left];
        int hr = height[right];
        int h = hl < hr ? hl : hr;
        long area = (long) h * (right - left);
        if (area > best) best = area;
        if (hl < hr) {
            while (left < right && height[left] <= h) left++;
        } else {
            while (left < right && height[right] <= h) right--;
        }
    }
    return best;
}

def max_area(height: Sequence[int]) -> int:
    left = 0
    right = len(height) - 1
    best = 0
    while left < right:
        hl = height[left]
        hr = height[right]
        h = hl if hl < hr else hr
        area = h * (right - left)
        if area > best: best = area
        if hl < hr:
            while left < right and height[left] <= h: left += 1
        else:
            while left < right and height[right] <= h: right -= 1
    return best

function maxArea(height: ArrayLike<number>): number {
  let left = 0;
  let right = height.length - 1;
  let best = 0;
  while (left < right) {
    const hl = height[left];
    const hr = height[right];
    const h = hl < hr ? hl : hr;
    const area = h * (right - left);
    if (area > best) best = area;
    if (hl < hr) {
      while (left < right && height[left] <= h) left++;
    } else {
      while (left < right && height[right] <= h) right--;
    }
  }
  return best;
}

Flaws & bottlenecks

The worst case is unchanged (O(n)); the gain is a smaller constant, mostly on inputs with many short lines.
The inner while loops each re-check left < right: dropping that guard can walk a pointer past the other.
Area can reach about 10⁹ for typical limits, so the product needs a wide integer type in fixed-width languages.

Interviewer cross-questions

Why is skipping all lines ≤ h safe?

Say: After measuring with limiting height h, any line on that side with height ≤ h combined with any narrower range has height at most h and strictly smaller width, so its area is below the area just measured. Skipping them all at once is just applying the one-step argument repeatedly.

Does it change the complexity?

Say: No: still O(n), because each pointer moves at most n times in total. It reduces the number of area computations, which are the expensive part (a multiply and compare), not the number of pointer moves.

How do you guard against overflow?

Say: height × width can reach 10⁴ × 10⁵ = 10⁹ for typical limits, which fits a 32-bit int, but wider inputs need 64-bit arithmetic (long / long long). Compute the product in the wider type before comparing.

Synchronized code walkthrough

Showing: Check every pair — shares the player above; click any step to jump.

int maxArea(vector<int>& height) {
    int best = 0;
    int n = height.size();
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int area = min(height[i], height[j]) * (j - i);
            best = max(best, area);
        }
    }
    return best;
}

public int maxArea(int[] height) {
    int best = 0;
    int n = height.length;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int area = Math.min(height[i], height[j]) * (j - i);
            best = Math.max(best, area);
        }
    }
    return best;
}

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

function maxArea(height: number[]): number {
  let best = 0;
  for (let i = 0; i < height.length; i++) {
    for (let j = i + 1; j < height.length; j++) {
      const area = Math.min(height[i], height[j]) * (j - i);
      best = Math.max(best, area);
    }
  }
  return best;
}

int maxArea(vector<int>& height) {
    int best = 0;
    int n = height.size();
    for (int i = 0; i < n; i++) {
        for (int j = n - 1; j > i; j--) {
            if (height[i] * (j - i) <= best) break;
            best = max(best, min(height[i], height[j]) * (j - i));
        }
    }
    return best;
}

public int maxArea(int[] height) {
    int best = 0;
    int n = height.length;
    for (int i = 0; i < n; i++) {
        for (int j = n - 1; j > i; j--) {
            if (height[i] * (j - i) <= best) break;
            best = Math.max(best, Math.min(height[i], height[j]) * (j - i));
        }
    }
    return best;
}

def max_area(height: list[int]) -> int:
    best = 0
    n = len(height)
    for i in range(n):
        for j in range(n - 1, i, -1):
            if height[i] * (j - i) <= best: break
            best = max(best, min(height[i], height[j]) * (j - i))
    return best

function maxArea(height: number[]): number {
  let best = 0;
  for (let i = 0; i < height.length; i++) {
    for (let j = height.length - 1; j > i; j--) {
      if (height[i] * (j - i) <= best) break;
      best = Math.max(best, Math.min(height[i], height[j]) * (j - i));
    }
  }
  return best;
}

int maxArea(vector<int>& height) {
    int left = 0;
    int right = (int)height.size() - 1;
    int best = 0;
    while (left < right) {
        int area = min(height[left], height[right]) * (right - left);
        best = max(best, area);
        if (height[left] < height[right]) left++;
        else right--;
    }
    return best;
}

public int maxArea(int[] height) {
    int left = 0;
    int right = height.length - 1;
    int best = 0;
    while (left < right) {
        int area = Math.min(height[left], height[right]) * (right - left);
        best = Math.max(best, area);
        if (height[left] < height[right]) left++;
        else right--;
    }
    return best;
}

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

function maxArea(height: number[]): number {
  let left = 0;
  let right = height.length - 1;
  let best = 0;
  while (left < right) {
    const area = Math.min(height[left], height[right]) * (right - left);
    best = Math.max(best, area);
    if (height[left] < height[right]) left++;
    else right--;
  }
  return best;
}

long long maxArea(const vector<int>& height) {
    int left = 0;
    int right = (int)height.size() - 1;
    long long best = 0;
    while (left < right) {
        int hl = height[left];
        int hr = height[right];
        int h = hl < hr ? hl : hr;
        long long area = (long long)h * (right - left);
        if (area > best) best = area;
        if (hl < hr) {
            while (left < right && height[left] <= h) left++;
        } else {
            while (left < right && height[right] <= h) right--;
        }
    }
    return best;
}

public long maxArea(int[] height) {
    int left = 0;
    int right = height.length - 1;
    long best = 0;
    while (left < right) {
        int hl = height[left];
        int hr = height[right];
        int h = hl < hr ? hl : hr;
        long area = (long) h * (right - left);
        if (area > best) best = area;
        if (hl < hr) {
            while (left < right && height[left] <= h) left++;
        } else {
            while (left < right && height[right] <= h) right--;
        }
    }
    return best;
}

def max_area(height: Sequence[int]) -> int:
    left = 0
    right = len(height) - 1
    best = 0
    while left < right:
        hl = height[left]
        hr = height[right]
        h = hl if hl < hr else hr
        area = h * (right - left)
        if area > best: best = area
        if hl < hr:
            while left < right and height[left] <= h: left += 1
        else:
            while left < right and height[right] <= h: right -= 1
    return best

function maxArea(height: ArrayLike<number>): number {
  let left = 0;
  let right = height.length - 1;
  let best = 0;
  while (left < right) {
    const hl = height[left];
    const hr = height[right];
    const h = hl < hr ? hl : hr;
    const area = h * (right - left);
    if (area > best) best = area;
    if (hl < hr) {
      while (left < right && height[left] <= h) left++;
    } else {
      while (left < right && height[right] <= h) right--;
    }
  }
  return best;
}