13.Container With Most Water

MediumBlind 75Two Pointers · 4/5

Problem

You are given an array height of length n. Picture n vertical lines where line i goes from (i, 0) to (i, height[i]).

Choose two lines that, together with the x-axis, form a container. Its water capacity is width × shorter height = (j - i) * min(height[i], height[j]). Return the maximum amount of water a container can store. The container cannot be tilted.

Examples

Input:  height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
Output: 49
Explanation: Lines at index 1 (height 8) and index 8 (height 7): width 7 × min(8, 7) = 49.

Input:  height = [1, 1]
Output: 1
Explanation: Width 1 × height 1.

Constraints

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

💡 Key Insight

Start with the widest container (left = 0, right = n - 1). The area is capped by the shorter line. Moving the taller line inward can never help — width shrinks and the height is still capped by the same shorter line. So the only move that might find a bigger area is to move the shorter line inward. That greedy rule discards one line per step and gives an O(n) scan.

Brute Force

TimeO(n²)SpaceO(1).

Intuition

Evaluate every pair of lines and keep the maximum area.

Algorithm

best = 0.
For all i < j: best = max(best, (j - i) * min(height[i], height[j])).
Return best.

Visualization

height = [1, 8, 6, 2, 5, 4, 8, 3, 7]

(1, 8): width 7, min(8, 7) = 7 → 49   ← best
(1, 6): width 5, min(8, 8) = 8 → 40
(0, 8): width 8, min(1, 7) = 1 → 8
...

Code

java

class Solution {
    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 = (j - i) * Math.min(height[i], height[j]); // shorter line caps the water
                best = Math.max(best, area);
            }
        }
        return best;
    }
}

Complexity

Time: O(n²) — every pair is evaluated (too slow for n = 10^5).
Space: O(1).

Two PointersOptimal

TimeO(n)SpaceO(1)

Intuition

Suppose height[left] < height[right]. Every container that uses left with some other right end j < right has smaller width and height at most height[left] — so none can beat the current one. Line left has therefore already achieved its best possible pairing, and we can safely discard it with left++. The symmetric argument discards right when it is the shorter line (on a tie, either can go). Each step eliminates one line, so after n - 1 steps every line has been considered.

Algorithm

left = 0, right = n - 1, best = 0.
While left < right:
- best = max(best, (right - left) * min(height[left], height[right])).
- If height[left] < height[right], left++; else right--.
Return best.

Dry Run

flowchart TD
    A["L=0 (1), R=8 (7)<br/>area 8·1 = 8, best 8"] -->|"left shorter: L++"| B["L=1 (8), R=8 (7)<br/>area 7·7 = 49, best 49"]
    B -->|"right shorter: R--"| C["L=1 (8), R=7 (3)<br/>area 6·3 = 18"]
    C -->|"R--"| D["L=1 (8), R=6 (8)<br/>area 5·8 = 40"]
    D -->|"tie: R--"| E["L=1 (8), R=5 (4)<br/>area 4·4 = 16"]
    E -->|"R-- repeatedly"| F["areas 15, 4, 6 ... L meets R"]
    F --> G["return 49"]

Code

java

class Solution {
    public int maxArea(int[] height) {
        int left = 0;
        int right = height.length - 1;
        int best = 0;
        while (left < right) {
            int h = Math.min(height[left], height[right]);
            best = Math.max(best, (right - left) * h);
            // The shorter line cannot do better with any narrower partner: discard it
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return best;
    }
}

Complexity

Time: O(n) — each iteration moves one pointer; at most n - 1 iterations.
Space: O(1) — a few integers.

Complexity Comparison

Approach	Time	Space
Brute Force	O(n²)	O(1)
Two Pointers	O(n)	O(1)

Common Pitfalls

Moving the taller pointer — it can only shrink the width while the shorter line still caps the height, so you may miss the optimum.
Confusing this with Trapping Rain Water: here only the two chosen lines matter; the lines between them are ignored.
Using max(height[left], height[right]) for the water level — water spills over the shorter side.
Width is right - left, not right - left + 1.