Trapping Rain Water

HARD✓ CHIP-TIMEDLC #42 — FULL STATEMENT ↗

The drill: Elevation bars stand in a row; after rain, water pools above each bar up to the shorter of the tallest walls on either side — total up all the water trapped.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A row of elevation bars stands side by side, each with its own height, and after imagining rain falling evenly across the whole row, water settles into the dips between taller bars.

Above any given bar, water can pool only up to the shorter of the tallest bar somewhere to its left and the tallest bar somewhere to its right — anything beyond that spills away rather than being trapped.

The task is to total up the water trapped above every bar in the row and report that single sum, not a picture of where it sits.

EX 01

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

→ 6

THE BOARD'S EXAMPLE

EX 02

height = [4, 2, 0, 3, 2, 5]

→ 9

DEEP BASIN BETWEEN TWO TALL WALLS

EX 03

height = [1, 1, 1, 1]

→ 0

FLAT SURFACE TRAPS NOTHING

the row holds anywhere from zero to around two hundred thousand bars
bar heights are non-negative and can repeat or reach zero
trapped water above a bar is capped by the shorter of its two bounding maxima
only the total trapped volume is reported

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Each bar's trapped water is min(tallest wall to its left, tallest wall to its right) minus its own height. Precomputing both of those directly costs an array on each side — can one inward pass track enough to skip storing them?

HINT 2 THE STRUCTURE

Walk two pointers from the outside in, keeping a running max on each side as you go. Whichever side currently has the smaller running max is already fully decided — the far side is guaranteed to be at least as tall.

HINT 3 ONE STEP FROM THE ANSWER

Step whichever pointer's running max is smaller, add that running max minus the bar's height to the total, and move that pointer inward — the other side's true max no longer matters for this bar.

COACH'S BOARD — THE PATTERN, STEP BY STEP

RUNNING MAX FROM BOTH SIDESPATTERN · TWO POINTERS, RUNNING MAXheight = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]

RUNNING STATE

leftMax → 0

rightMax → 1

water → 0

STEP 1

L=0, R=11. leftMax starts at height[0]=0, rightMax at height[11]=1 — the running maxima seed the walk.

STEP 1 / 13 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/trapping-rain-water.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def trap(self, height: List[int]) -> int:
        n = len(height)
        if n == 0:
            return 0
        l, r = 0, n - 1
        left_max, right_max = height[l], height[r]
        water = 0
        while l < r:
            if left_max < right_max:
                l += 1
                left_max = max(left_max, height[l])
                water += left_max - height[l]
            else:
                r -= 1
                right_max = max(right_max, height[r])
                water += right_max - height[r]
        return water

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

class Solution:
    def trap(self, height: List[int]) -> int:
        n = len(height)
        if n == 0:
            return 0
        left_max = [0] * n
        right_max = [0] * n
        left_max[0] = height[0]
        for i in range(1, n):
            left_max[i] = max(left_max[i - 1], height[i])
        right_max[n - 1] = height[n - 1]
        for i in range(n - 2, -1, -1):
            right_max[i] = max(right_max[i + 1], height[i])
        return sum(min(left_max[i], right_max[i]) - height[i] for i in range(n))

TIME O(N)SPACE O(N)PYTHON · TRAINING PACE · 14 LN

class Solution {
    public int trap(int[] height) {
        int n = height.length;
        if (n == 0) {
            return 0;
        }
        int l = 0;
        int r = n - 1;
        int leftMax = height[l];
        int rightMax = height[r];
        int water = 0;
        while (l < r) {
            if (leftMax < rightMax) {
                l++;
                leftMax = Math.max(leftMax, height[l]);
                water += leftMax - height[l];
            } else {
                r--;
                rightMax = Math.max(rightMax, height[r]);
                water += rightMax - height[r];
            }
        }
        return water;
    }
}

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

class Solution {
    public int trap(int[] height) {
        int n = height.length;
        if (n == 0) {
            return 0;
        }
        int[] leftMax = new int[n];
        int[] rightMax = new int[n];
        leftMax[0] = height[0];
        for (int i = 1; i < n; i++) {
            leftMax[i] = Math.max(leftMax[i - 1], height[i]);
        }
        rightMax[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            rightMax[i] = Math.max(rightMax[i + 1], height[i]);
        }
        int water = 0;
        for (int i = 0; i < n; i++) {
            water += Math.min(leftMax[i], rightMax[i]) - height[i];
        }
        return water;
    }
}

TIME O(N)SPACE O(N)JAVA · TRAINING PACE · 23 LN

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