Container With Most Water

You are given an array height of length n. Picture n vertical walls standing on a flat floor, one unit apart: wall i stands at position i and is height[i] units tall.

Choose any two walls. Together with the floor they form an open container, and the water it holds is limited by the shorter wall: its amount is min(height[i], height[j]) * (j - i). All other walls are ignored (they do not block or split the water).

Return the largest amount of water any pair of walls can hold.

Example 1

Example 2

Example 3

Constraints

• 2 <= n <= 105
• 0 <= height[i] <= 104

Pattern Path · Two Pointers · problem 21 of 169

Start simple

Evaluate every pair of walls and keep the best: O(n²) time, O(1) space.

The key idea

Place one pointer on the first wall and one on the last, record the water between them, and then move the pointer at the shorter wall one step inward. Repeat until the pointers meet.

Why is it safe to discard the shorter wall? Say height[left] <= height[right]. Any container that uses left together with some wall between the pointers is narrower than the current one, and its height is still at most height[left]. So none of those pairs can beat what we just recorded, and left can never again be part of a better answer. Dropping it loses nothing.

Each step eliminates one wall, so after n - 1 steps every candidate pair has been either measured or proven no better than one that was. That turns an O(n²) search into a single linear sweep.

Complexity

• Time: O(n)
• Space: O(1)

Python

class Solution:
    def maxArea(self, height):
        left, right = 0, len(height) - 1
        best = 0
        while left < right:
            water = min(height[left], height[right]) * (right - left)
            best = max(best, water)
            # The shorter wall can never be part of a better container.
            if height[left] <= height[right]:
                left += 1
            else:
                right -= 1
        return best

JavaScript

var maxArea = function(height) {
  let left = 0, right = height.length - 1;
  let best = 0;
  while (left < right) {
    const water = Math.min(height[left], height[right]) * (right - left);
    best = Math.max(best, water);
    // The shorter wall can never be part of a better container.
    if (height[left] <= height[right]) left++;
    else right--;
  }
  return best;
};

What the interviewer is checking

The code is short; the real test is whether you can justify why moving the shorter pointer never skips the optimal pair.

Mistakes to avoid

• Moving the taller wall, which can skip the best answer.
• Using the taller wall (or the sum) as the water height instead of the shorter one.
• Confusing this with trapping rain water, where the walls in between do matter.

Follow-ups to expect

• How would you compute the total water trapped between all walls instead? (Prefix maxima or two pointers.)
• Prove the greedy step formally. (Exchange argument on discarded pairs.)
• What if equal heights are common, can you move both pointers? (Yes, both are dominated.)

In real software

The same shrink-the-window-from-the-weaker-side reasoning appears in optimising pairs under a min/product objective, such as picking two price points or two sensors that maximise a bottlenecked throughput times distance.

Practice next