Container With Most Water: Brute Force to Optimal

LeetCode 11, solved three ways — checking every pair, the classic two-pointer sweep, and a skip-optimized two-pointer version — with intuition, C++ code, an animated bar-chart dry run for each approach, and complexity analysis you can explain out loud.

On this page

Problem statement
Approach 1 — Brute force (check every pair)
Approach 2 — Better (two pointers)
Approach 3 — Optimal (two pointers + skip)
Complexity comparison
Interview notes
FAQ

Problem Statement

Given n vertical lines at each index with height height[i], find the two lines that, together with the x-axis, hold the most water. The container's area is (distance between the two lines) × (the shorter of the two heights) — the water can't rise above the shorter wall.

Example: height = [1,8,6,2,5,4,8,3,7] → output 49, using the lines at index 1 (height 8) and index 8 (height 7): width 7 × height 7 = 49.

We'll trace all three approaches on this exact array, watching each one arrive at the same answer, 49 — but with very different amounts of wasted work along the way.

Approach 1 · Brute Force

Check Every Pair of Lines

Intuition

The problem is asking for the best pair among all possible pairs, so the most direct approach just tries every one: for each pair (i, j), compute the area using the shorter of the two heights and the distance between them, and keep the largest one seen. It's guaranteed correct because nothing is skipped — but with n lines there are roughly n²/2 pairs to check.

Algorithm

Initialize best = 0.
For every pair of indices i < j, compute area = (j - i) × min(height[i], height[j]).
Update best if this area is larger.
After checking every pair, return best.

C++ Code

int maxArea(vector<int>& height) {
    int n = height.size();
    int best = 0;

    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int width = j - i;
            int h = min(height[i], height[j]);
            best = max(best, width * h);
        }
    }
    return best;
}

Dry Run

Complexity Analysis

Metric	Value	Why
Time	O(n²)	Every pair of the n lines is checked exactly once
Space	O(1)	Only a running maximum is tracked
Practical issue	Wasted work	Most pairs, like two adjacent short lines, are obviously never going to win

Approach 2 · Better

Two Pointers, Always Move the Shorter Side

Intuition

Start with the widest container possible — the two outermost lines — and shrink inward one step at a time. The key insight: whichever line is shorter is the one limiting the area, so it's always safe to move that pointer inward, hoping to find something taller. The taller line should stay, since discarding it while keeping the shorter one could only ever shrink the width without any chance of raising the limiting height.

Algorithm

Set left = 0 and right = n - 1.
While left < right, compute the area using min(height[left], height[right]) and the current width, updating best.
If height[left] < height[right], move left forward by one; otherwise move right backward by one.
Repeat until the pointers meet, then return best.

C++ Code

int maxArea(vector<int>& height) {
    int left = 0, right = height.size() - 1;
    int best = 0;

    while (left < right) {
        int width = right - left;
        int h = min(height[left], height[right]);
        best = max(best, width * h);

        if (height[left] < height[right]) left++;
        else right--;
    }
    return best;
}

Dry Run

pproach 3 · Optimal

Two Pointers, Skipping Guaranteed Losers

Intuition

The basic two-pointer sweep still evaluates every single step, even when it's obvious in advance that a step won't help. If the left pointer just moved because height[left] was the limiting factor, then any later index with an even smaller or equal height can't possibly beat what's already been seen — its width is smaller and its height is no taller. Skip straight past all of those in one go, instead of evaluating them one at a time.

Algorithm

Set left = 0 and right = n - 1, exactly as before.
While left < right, compute the area and update best, same as Approach 2.
If height[left] < height[right], remember the current height[left] and advance left past every following index whose height doesn't exceed it.
Otherwise, do the mirrored skip on the right pointer.
Repeat until the pointers meet, then return best.

C++ Code

int maxArea(vector<int>& height) {
    int left = 0, right = height.size() - 1;
    int best = 0;

    while (left < right) {
        int width = right - left;
        int h = min(height[left], height[right]);
        best = max(best, width * h);

        if (height[left] < height[right]) {
            int curr = height[left];
            while (left < right && height[left] <= curr) left++;
        } else {
            int curr = height[right];
            while (left < right && height[right] <= curr) right--;
        }
    }
    return best;
}

Dry Run

Complexity Analysis

Metric	Value	Why
Time	O(n)	each index is still visited at most once total across both skip loops combined
Space	O(1)	same two pointers and running maximum as Approach 2
Why optimal	Fewest wasted evaluations	provably-worse indices are skipped in bulk instead of visited one at a time

Interview Notes

How to talk through it

State the shorter-side argument out loud before writing any two-pointer code — it's the single insight that makes this problem click, and interviewers want to hear you reason about why it's safe, not just recite the technique.
Mention brute force briefly to establish a correct baseline, then move straight to the two-pointer version as your primary answer.
Offer the skip optimization only if asked to go further — it's a nice detail, but the basic two-pointer version is already the expected "optimal" answer in most interviews.

Common follow-ups

"Prove that moving the shorter pointer never loses the optimal answer." → the container's area is capped by its shorter wall; keeping that wall fixed while shrinking the width can only shrink or hold the area, never grow it, so the shorter side is the only one worth moving.
"What if two heights are equal?" → either pointer can move; it doesn't affect correctness since both sides are equally limiting.
"Could you solve this with sorting or divide and conquer?" → sorting loses the original index positions needed for width, so it doesn't directly help; two pointers on the original array is the standard efficient approach.

Edge cases to mention

Fewer than 2 lines → no container can be formed, return 0.
All heights equal → the widest pair (the two ends) is always optimal.
Strictly increasing or strictly decreasing heights → the two-pointer sweep still finds the optimal pair in a single pass.

Frequently Asked Questions

What is the key insight for Container With Most Water?

Start with the widest container and always move the pointer at the shorter line inward — the shorter line is what caps the area, so it's the only side that could possibly lead to a better result.

Which approach should I lead with in an interview?

Mention brute force briefly to set a correct baseline, then write the two-pointer solution as your main answer, explaining the shorter-side argument clearly as you go.

Why is the brute force approach too slow?

It checks all O(n²) pairs of lines, which is wasteful since most pairs — like two short, nearby lines — can be ruled out without ever computing their area.

What is the time and space complexity of the optimal solution?

The two-pointer approach runs in O(n) time, since the pointers together move at most n steps, and uses O(1) extra space beyond the two pointers and a running maximum.

video reference:

problem link:

https://leetcode.com/problems/container-with-most-water/

Container With Most Water: Brute Force to Optimal

Problem Statement

Check Every Pair of Lines

Intuition

Algorithm

C++ Code

Dry Run

Complexity Analysis

Two Pointers, Always Move the Shorter Side

Intuition

Algorithm

C++ Code

Dry Run

Two Pointers, Skipping Guaranteed Losers

Intuition

Algorithm

C++ Code

Dry Run

Complexity Analysis

Interview Notes

How to talk through it

Common follow-ups

Edge cases to mention

Frequently Asked Questions

Chakradhar

Container With Most Water: Brute Force to Optimal

Problem Statement

Check Every Pair of Lines

Intuition

Algorithm

C++ Code

Dry Run

Complexity Analysis

Two Pointers, Always Move the Shorter Side

Intuition

Algorithm

C++ Code

Dry Run

Two Pointers, Skipping Guaranteed Losers

Intuition

Algorithm

C++ Code

Dry Run

Complexity Analysis

Interview Notes

How to talk through it

Common follow-ups

Edge cases to mention

Frequently Asked Questions