Container With Most Water (LC 11)

Pattern: Two Pointers
Difficulty: Medium
Key Concept: Start with the widest container; moving the taller line never improves area, so always move the shorter pointer inward.

Problem Statement

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

Find two lines that together with the x-axis form a container that holds the most water.

Return the maximum amount of water the container can store.

You may not slant the container.

Input

• height — array of non-negative integers (length ≥ 2)

Output

• int — maximum area (water) between two lines

Example

• height = [1, 8, 6, 2, 5, 4, 8, 3, 7] → 49.

---

1. Algorithm & Pseudocode

Brute force

1. Set best = 0.
2. For each i from 0 to n - 2:
3. For each j from i + 1 to n - 1:
4. Compute area = (j - i) * min(height[i], height[j]).
5. If area > best, set best = area.
6. Return best.

Optimal

1. Set left = 0, right = n - 1, best = 0.
2. While left < right:
3. width = right - left, h = min(height[left], height[right]), area = width * h, best = max(best, area).
4. If height[left] < height[right], left++; else right--.
5. Return best.

---

2. Step-by-Step Analysis (Beginner-Friendly)

Why brute force is correct
Every pair (i, j) defines a valid container; the water is limited by the shorter side times the horizontal distance. Checking all pairs finds the maximum.

Why brute force is slow
There are (O(n^2)) pairs.

Why the two-pointer greedy is safe
Start with the widest width (left=0, right=n-1). That is the best possible width; any other pair is narrower.

When you shrink width by one step, you must drop one of the sides. The area is width * min(leftHeight, rightHeight). The height is capped by the shorter line.

• If you move the taller pointer inward, the width decreases, and the min height is still capped by the unchanged shorter line—so the area cannot increase (width down, height ≤ same short side).
• If you move the shorter pointer, you give up a chance to find a taller short side that might compensate for lost width.

So the only sensible move is to advance the pointer at the shorter line.

Why we do not miss the optimum
Any maximum area is achieved by some pair (i, j). The algorithm explores a path of pairs that provably discards only pairs that cannot beat the best found so far under this rule—formally, skipping the taller-side move is safe because it cannot improve the bottleneck height.

ASCII — bottleneck

height
  |     |
  |  |  |
  |  |  |
--+--+--+--
  L     R

Area = width * min(h[L], h[R])  ← limited by the shorter stick

---

3. The Dry Run

Input: height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
Indices: 0 1 2 3 4 5 6 7 8

Step	left	right	width	min h	area	Move
1	0	8	8	1	8	h[0]<h[8] → left++
2	1	8	7	7	49	tie 8==8 → right-- (either side ok when equal)
…	…	…	…	…	…	(continues; best stays 49)

Early optimum: when left=1, right=8, heights 8 and 7 → min=7, width 7 → 49.

Result: 49.

---

4. Java Solution

Brute Force

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

Time: (O(n^2)).
Space: (O(1)).

Optimal

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

Time: (O(n)) — each pointer moves at most n steps.
Space: (O(1)).

---

5. The “Java vs. Others” Edge

• When height[left] == height[right], moving either pointer is acceptable; some implementations move both—still (O(n)), but one-side move is enough.
• Pure int arithmetic; watch overflow only if you port to huge coordinates—in Java int product for LeetCode constraints is fine.
• No boxing: int[] is faster and clearer than List<Integer> for this hot loop.

---

6. Complexity Summary

Approach	Time	Space	Notes
Brute Force	(O(n^2))	(O(1))	Checks every pair (i, j).
Optimal	(O(n))	(O(1))	Two pointers from both ends; each index visited once.