Container With Most Water

MEDIUM✓ CHIP-TIMEDLC #11 — FULL STATEMENT ↗

The drill: A row of vertical lines marks possible container walls; pick the two that hold the most water between them, where capacity is limited by the shorter wall.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A row of vertical lines arrives, each with its own height, standing at evenly spaced positions, and the task is to pick two of them to act as container walls.

The water held between two chosen walls is bounded by the shorter of the pair — height beyond that shorter wall simply spills over — and the width is just the distance between their positions.

The goal is to report the largest amount of water any single pair of walls could hold, not the pair itself.

EX 01

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

→ 49

THE BOARD'S EXAMPLE

EX 02

height = [1, 1]

→ 1

MINIMUM SIZE, TWO WALLS

EX 03

height = [4, 3, 2, 1, 4]

→ 16

BEST ANSWER USES THE TWO OUTER WALLS

the row holds anywhere from two to around one hundred thousand lines
heights are non-negative and can repeat
capacity between two walls is limited by the shorter of the pair
only the maximum area is reported, not which walls achieve it

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Scoring every pair works, but starting at the two outer walls already gives the widest span for free. If moving the taller wall inward can only shrink the width without ever raising the limiting height, which wall is worth moving?

HINT 2 THE STRUCTURE

The shorter of the two current walls is the bottleneck — it is the only side whose movement has any chance of finding something taller and beating the current best.

HINT 3 ONE STEP FROM THE ANSWER

Two pointers start at both ends; record width × min(height at each pointer) as the running best, then always step the shorter side inward, since the taller side could never do better at a smaller width.

COACH'S BOARD — THE PATTERN, STEP BY STEP

SHRINK THE SHORT SIDEPATTERN · TWO POINTERSheight = [1, 8, 6, 2, 5, 4, 8, 3, 7]

BEST AREA SO FAR

— empty —

STEP 1

L at 0 (height 1), R at 8 (height 7). Width 8 × the shorter wall, 1, = area 8.

STEP 1 / 6 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/container-with-most-water.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def maxArea(self, height: List[int]) -> int:
        l, r = 0, len(height) - 1
        best = 0
        while l < r:
            best = max(best, (r - l) * min(height[l], height[r]))
            if height[l] < height[r]:
                l += 1
            else:
                r -= 1
        return best

TIME O(N)SPACE O(1)PYTHON · RACE PACE · 11 LN

class Solution:
    def maxArea(self, height: List[int]) -> int:
        best = 0
        n = len(height)
        for i in range(n):
            for j in range(i + 1, n):
                best = max(best, (j - i) * min(height[i], height[j]))
        return best

TIME O(N²)SPACE O(1)PYTHON · TRAINING PACE · 8 LN

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

TIME O(N)SPACE O(1)JAVA · RACE PACE · 16 LN

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++) {
                best = Math.max(best, (j - i) * Math.min(height[i], height[j]));
            }
        }
        return best;
    }
}

TIME O(N²)SPACE O(1)JAVA · TRAINING PACE · 12 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED