11. Container With Most Water

Everyone gets to “use two pointers and move the shorter line” quickly. The part that’s worth understanding — and the part interviewers actually probe — is why throwing away the shorter line can’t cost you the best answer.

Question

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the i-th line are (i, 0) and (i, height[i]).

• Find two lines that together with the x-axis form a container, such that the container contains the most water.
• Return the maximum amount of water a container can store.

Note that you may not slant the container.

• Example

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation:
The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7].
In this case, the max area of water (blue section) the container can contain is 49.

• Example

Input: height = [1,1]
Output: 1

• Constraints
  • $n == height.length$
  • $2 <= n <= 10^5$
  • $0 <= height[i] <= 10^4$

The area is capped by the shorter wall

The water a pair holds is width × height, but the height is not the average or the taller line — it’s the shorter of the two, because water spills over the lower wall:

area = (right - left) * min(height[left], height[right])

Brute force checks all $O(n^2)$ pairs. To get to $O(n)$, start with the widest possible container — one pointer at each end — and shrink it inward, keeping the best area as you go. The whole trick is which pointer to move.

Why you move the shorter line

Say left is the shorter wall. The pair (left, right) gives area (right - left) * height[left]. Now ask the question that makes the algorithm correct: could any other pair that still includes left beat this one?

No. Moving right inward only makes the width smaller, and the height stays capped by height[left] (the short wall doesn’t get taller). So every remaining pair using left is worse than the one you just measured. That means left has nothing left to offer — you can discard it and advance the pointer. Discarding the taller line instead would be the mistake: that taller wall might still pair with an even taller wall further in, so throwing it away could skip the real maximum. The shorter wall carries no such risk.

This is a greedy exchange argument: at each step you eliminate a pointer that provably can’t be part of a better answer, so one linear pass is enough. It’s the same two-pointer shape as many sorted-array problems, but here the ordering that justifies it is the height cap, not a sort.

Answer

/**
 * Two pointers / Greedy
 * TC: O(n)
 * SC: O(1)
 */
public int maxArea(int[] height) {

    if (height == null || height.length < 2) {
        return 0;
    }

    int max   = 0; // maximum area
    int left  = 0;
    int right = height.length - 1;

    while (left < right) {
        // The water level is determined by the shorter line
        // area = width (right - left) * min height
        int tmpMax = (right - left) * Math.min(height[left], height[right]);
        max = Math.max(max, tmpMax);

        // Move the pointer with the smaller height
        // because we need to find a taller line to increase the area
        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }

    return max;
}

When the two heights are equal, it doesn’t matter which side you move — both remaining pairs are capped by the same height, so the code’s else branch (move right) is an arbitrary but safe choice.

Walking through the example

Trace height = [1,8,6,2,5,4,8,3,7] — the key steps (right also passes 7, 5, 4, 3 in between), and the winner shows up almost immediately:

left (h)	right (h)	width	area = width × min	max	move
0 (1)	8 (7)	8	8 × 1 = 8	8	left (shorter)
1 (8)	8 (7)	7	7 × 7 = 49	49	right (shorter)
1 (8)	6 (8)	5	5 × 8 = 40	49	right (tie)
1 (8)	2 (6)	1	1 × 6 = 6	49	right

The first move throws away the height-1 wall on the left — and it should, because a wall of height 1 caps any container it’s part of at 1 unit tall, no matter how wide. From then on left sits on the tall wall (height 8) while right sweeps inward, and nothing narrower ever beats the 7-wide, 7-tall pair. That’s the proof playing out: every discarded pointer was provably dead weight.

Complexity

• Time: $O(n)$ — each pointer moves inward at most n times, so the loop runs n - 1 iterations total.
• Space: $O(1)$ — two indices and a running max, nothing that grows with the input.

Watch the pointers collapse inward and the recorded max update step by step:

The instinct to resist

The tempting wrong move is to always shrink from the right, or to move whichever side is taller to “hunt for more water.” Both can walk right past the answer. The only move with a correctness proof behind it is dropping the shorter wall — everything else is a guess.

References

• https://leetcode.com/problems/container-with-most-water/
• https://walkccc.me/LeetCode/problems/0011/
• https://leetcode.ca/all/11.html