Container With Most Water

1. Problem & Core Objective

The problem

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

Find two lines that, together with the x-axis, form a container holding the most water. Return that maximum amount.

You may not slant the container.

Input:  height = [1,8,6,2,5,4,8,3,7]     Output: 49
Input:  height = [1,1]                   Output: 1

For the first example, lines at index 1 (height 8) and index 8 (height 7) give width 8 − 1 = 7 and usable height min(8,7) = 7, so area 7 × 7 = 49.

Constraints:

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

What the interviewer is actually testing

The code is six lines. The proof is the question.

1. Do you derive the area formula correctly? width × min(left, right) — water spills over the shorter wall, so the taller one is irrelevant to the height.
2. Can you justify moving the shorter wall? This is a greedy choice, and greedy choices are only valid with an argument. Being unable to prove it is the failure mode here — the code will look right and you'll have no defence when asked "why is that safe?"
3. Do you avoid confusing this with Trapping Rain Water? They look similar and are completely different problems. This one holds water between two chosen lines; that one traps water in every valley.

If you only rehearse one thing for this problem, rehearse the exchange argument in §2 Step 4.

2. First-Principles Thought Process

Step 1 — Constraints

n up to 10^5.

• O(n²) → 10^10. Too slow.
• O(n log n) or O(n) → fine.

So a nested loop is out, and you need either sorting (which makes no sense here — positions matter) or a linear scan.

Step 2 — Derive the area formula

Two lines at indices i and j (with i < j) form a container:

• Width = j − i (the horizontal distance).
• Height = min(height[i], height[j]).

Why the minimum? Water fills up to the level of the shorter wall — beyond that it spills over the top. The taller wall contributes nothing above that level.

      8 |█                    
        |█         █          ← water level is capped at 7, the SHORTER wall
      7 |█ ~ ~ ~ ~ █
        |█ ~ ~ ~ ~ █
        +----------+
         i        j

So: area = (j − i) × min(height[i], height[j])

Step 3 — Brute force, and where the waste is

Try every pair: O(n²). Too slow.

But notice the structure — there are two competing factors:

• The widest container is the outermost pair (indices 0 and n−1), but its walls may be short.
• A taller pair must be closer together, so it loses width.

You're maximizing a product where increasing one factor decreases the other. That suggests starting at one extreme and trading.

Step 4 — The greedy insight, and its proof

Start at maximum width: l = 0, r = n − 1. Now you must move one pointer inward — which one?

Always move the pointer at the SHORTER wall.

Here is the argument. Rehearse it:

"The area is width × min(left, right). Moving either pointer inward always decreases the width by at least 1.

Suppose I move the taller wall inward. The shorter wall is unchanged, so min(left, right) is still capped by that same shorter wall — the height cannot increase. And the width just shrank. So every container I could form that way is at most as good as the one I already measured. Nothing is lost by never trying them.

Therefore the only move that can possibly improve the answer is to move the shorter wall — because replacing it is the only way the height can go up enough to offset the lost width.

So discarding the shorter wall is safe: no better container using it exists."

The formal version — this is an exchange argument, the same proof style used throughout Greedy:

Let the shorter wall be at l. Every pair (l, k) for l < k < r has width k − l < r − l and height min(height[l], height[k]) <= height[l]. So its area is strictly less than (r − l) × height[l], which we have already computed. Hence no pair involving l beats what we've recorded, and l can be discarded permanently.

Step 5 — Termination and completeness

Each iteration moves exactly one pointer inward, so the loop runs at most n − 1 times: O(n).

Does it examine all the right candidates? It examines only O(n) of the O(n²) pairs — but Step 4 proves that every skipped pair is dominated by one already measured. So the maximum is never missed.

Step 6 — What about ties?

If height[l] == height[r], which do you move? Either. When the walls are equal, the argument applies to both symmetrically: moving either one discards only dominated pairs. Some implementations move both; moving one is simpler and equally correct.

3. Solution Paths

Approach 1 — Brute force

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

Tries every pair.

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

At n = 10^5 that's 5 × 10^9 iterations. Name it, give the formula (which is the useful part), and move on.

Counter-questions on this approach

⭐ "How bad is O(n²) at n = 10^5?"

About 5 × 10^9 pair evaluations — far beyond what's acceptable. The useful part of writing this out isn't the loop, it's the area formula: (j − i) × min(height[i], height[j]). That formula is what I actually need to carry into the optimal solution.

"Why min and not max in that formula?"

Water fills only to the level of the shorter wall — above that it spills over the top. The taller wall contributes nothing beyond the shorter one's height, so it's the minimum that determines the usable height.

Approach 2 — Two pointers (optimal)

public int maxArea(int[] height) {
    int l = 0, r = height.length - 1;
    int best = 0;

    while (l < r) {
        int area = (r - l) * Math.min(height[l], height[r]);
        best = Math.max(best, area);

        if (height[l] < height[r]) l++;     // move the SHORTER wall
        else r--;
    }
    return best;
}

Full trace on height = [1,8,6,2,5,4,8,3,7]:

Answer: 49 ✓

Notice step 1 → 2: the first move discards index 0 (height 1) forever. That single line had width 8 but height 1 — and the proof guarantees no better container uses it.

• Time: O(n) — one pointer moves per iteration, at most n − 1 iterations.
• Space: O(1) — three integers.

Counter-questions on this approach

⭐ "Prove that moving the shorter wall doesn't lose the optimal answer."

Let the shorter wall be at l. Consider any pair (l, k) with k < r. Its width is k − l, strictly less than r − l. Its height is min(height[l], height[k]), which is at most height[l]. So its area is strictly less than (r − l) × height[l] — the area I just measured. Every container involving l is therefore already dominated by one I've recorded, so discarding l loses nothing.

⭐ "You examine n − 1 pairs out of n(n−1)/2. Could the optimal pair be one you never look at?"

No. Every pair that gets skipped is provably dominated by a pair already measured — that's exactly what the exchange argument establishes. The skipping is justified by proof, not by sampling or heuristic.

"What if both walls are the same height — which one do you move?"

Either. The dominance argument is symmetric when the heights are equal, so neither choice can discard the optimum. The < versus <= in the branch condition is genuinely arbitrary here.

"Does this pruning still work if I want the top-k containers rather than the best one?"

No, and that's an important limitation. The argument discards pairs proven worse than the current best — but a discarded pair could easily be the second- or third-best overall. A greedy proof that eliminates candidates is valid only for finding the single optimum.

A refinement worth mentioning

You can skip walls that can't possibly help:

while (l < r) {
    int h = Math.min(height[l], height[r]);
    best = Math.max(best, (r - l) * h);

    while (l < r && height[l] <= h) l++;     // skip all walls no taller than the current min
    while (l < r && height[r] <= h) r--;
}

Any wall no taller than the current limiting height, and closer in, is strictly dominated. Same O(n) complexity — each pointer still only moves forward — but fewer iterations in practice.

Present the simple version first. Offer this only if asked to optimize further; it's a constant-factor win, not a complexity one.

Counter-questions on this approach

⭐ "You've now got skip loops nested inside the main loop. Is it still O(n)?"

Yes. Both pointers only ever move forward, and neither backtracks, so their combined movement is bounded by n regardless of how the inner loops are written. It's the same aggregate-accounting argument that makes a monotonic stack linear. This is a constant-factor improvement, not a complexity one — which is why I'd present the simple version first.

Comparison

4. Why the Optimal Wins

Against brute force. The brute force evaluates every pair. Two pointers evaluates n − 1 of them — and the exchange argument proves that every pair not evaluated is dominated by one that was. That's the difference between exhaustive search and a proof-backed shortcut.

The reason this is worth understanding rather than memorizing: the technique is only valid because of the argument. There's no structural property like sortedness here — nothing about height is ordered. What makes two pointers work is that you can always identify which candidate is provably useless.

That's the general shape of a greedy algorithm: at each step, prove one option can be discarded without loss.

Why you can't do better than O(n). Every line must be examined at least once — an adversary could make any unexamined line part of the optimal pair. So O(n) is optimal.

The comparison to Trapping Rain Water (next question) is worth pre-empting, because they look alike:

Saying "these are different problems despite looking similar" before being asked shows you're reading rather than pattern-matching.

5. Java Prerequisites

Math.min and Math.max

int area = (r - l) * Math.min(height[l], height[r]);
best = Math.max(best, area);

Both are overloaded for int, long, float, double. With int arguments you get int back — no accidental widening.

Overflow analysis

(r - l) * Math.min(height[l], height[r])

Maximum width is 10^5 − 1; maximum height is 10^4. So the largest possible area is about 10^9 — which fits in an int (max ≈ 2.1 × 10^9), but not by much.

Worth stating: "Width up to 10⁵ times height up to 10⁴ is about 10⁹, which fits in an int with room to spare. If either bound were larger I'd use long." Showing you computed the bound rather than assuming is the senior move. See 03.

Initializing best

int best = 0;

Safe because heights are non-negative (0 <= height[i]), so no area is ever negative. If values could be negative you'd initialize to Integer.MIN_VALUE — the same reasoning as Kadane's algorithm (20).

while (l < r), not l <= r

The two lines must be distinct — a container needs two walls. At l == r the width is 0 and the area is 0, so it's harmless but meaningless. Use <.

Loop structure

while (l < r) {
    // measure FIRST
    // then move
}

Measuring before moving matters: the initial pair (maximum width) must be evaluated, and the final pair before the pointers meet must be too. Moving first would skip the widest container entirely.

6. Interview Communication Guide

Clarifying questions

1. "Do the lines themselves have width, or are they infinitely thin?" — infinitely thin. This is the distinction from Trapping Rain Water, where bars occupy space.
2. "Can heights be zero?" — yes, 0 <= height[i]. A zero-height wall gives zero area.
3. "Can the container be slanted?" — no, per the problem. Water is level.
4. "Do I return the area, or the indices?" — the area.
5. "Is n >= 2 guaranteed?" — yes, so there's always at least one pair.

The pitch

"For two lines at i and j, the container's width is j − i and its height is min(height[i], height[j]) — the minimum, because water spills over the shorter wall. So the area is (j − i) × min(...).

Brute force checks all pairs at O(n²), too slow for n = 10⁵.

Instead I'll start at maximum width — one pointer at each end — and move inward. The key question is which pointer to move, and the answer is always the shorter wall.

Here's why that's safe. Moving either pointer reduces the width. If I move the taller wall, the shorter one still caps the height, so the height can't improve and the width just got smaller — every such container is worse than what I've already measured. So those pairs can be skipped entirely. The only move that can help is replacing the shorter wall.

That means each step safely discards one line forever. O(n) time, O(1) space.

On overflow: width up to 10⁵ times height up to 10⁴ is about 10⁹, which fits in an int."

Edge cases to raise proactively

The tie case is worth volunteering: "When both walls are equal, I can move either — the argument is symmetric, so neither choice can lose the optimum." It shows you thought about the branch condition rather than copying < from memory.

The [1,0,1] case is a nice one-liner for proving you understand the formula: the middle zero doesn't block anything, because lines have no thickness.

7. Follow-Up Questions — Modified Constraints

The interviewer changes a constraint of the original problem and asks you to solve it again. These are new problems, asked after your solution is accepted — not challenges to it. (Those are the counter-questions attached to each approach in §3.) ⭐ marks the most likely.

⭐ "What if you had to return the two indices, not just the area?"

Record l and r whenever best improves. No complexity change.

"What if the container could be slanted?"

The problem becomes geometric rather than combinatorial — water level is no longer min of two heights, and you'd need to reason about the surface. Very different question; the two-pointer argument doesn't transfer.

"Can you do it in one pass over a stream?"

No. Two pointers requires access to both ends simultaneously, which a forward-only stream doesn't provide. You'd need to buffer the whole array.