#42 Trapping Rain Water

Hardsolve on LeetCode ↗

frequently reported atGoldman Sachs Walmart Samsung Amazon ByteDance / TikTok Bloomberg

the problem

In plain words

Given bar heights of width 1, compute how much rain water is trapped after raining.

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

out 6

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

out 9

1 ≤ n ≤ 2·10⁴
0 ≤ height[i] ≤ 10⁵

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternTwo pointers (opposite ends)Prefix & suffix passes

Water above bar i = min(tallest bar on its left, tallest on its right) − height[i]. You only need the smaller of the two maxima — and the side with the smaller wall already knows it.

solutions

From brute force to optimal

For each bar, find the max to its left and right by scanning.

For each i: leftMax = max(h[0..i]), rightMax = max(h[i..n−1]).
Add min(leftMax, rightMax) − h[i].

timeO(n²)

Two scans per bar.

spaceO(1)

Counters only.

java

1class Solution {2    public int trap(int[] height) {3        int water = 0;4        for (int i = 0; i < height.length; i++) {5            int leftMax = 0, rightMax = 0;6            for (int l = 0; l <= i; l++) leftMax = Math.max(leftMax, height[l]);7            for (int r = i; r < height.length; r++) rightMax = Math.max(rightMax, height[r]);8            water += Math.min(leftMax, rightMax) - height[i];9        }10        return water;11    }12}

Store leftMax[i] and rightMax[i] in two arrays.

Fill leftMax left→right.
Fill rightMax right→left.
Sum min(leftMax[i], rightMax[i]) − h[i].

timeO(n)

Three linear passes.

spaceO(n)

Two helper arrays.

java

1class Solution {2    public int trap(int[] height) {3        int n = height.length;4        if (n == 0) return 0;5        int[] leftMax = new int[n], rightMax = new int[n];6        leftMax[0] = height[0];7        for (int i = 1; i < n; i++) leftMax[i] = Math.max(leftMax[i - 1], height[i]);8        rightMax[n - 1] = height[n - 1];9        for (int i = n - 2; i >= 0; i--) rightMax[i] = Math.max(rightMax[i + 1], height[i]);10        int water = 0;11        for (int i = 0; i < n; i++) water += Math.min(leftMax[i], rightMax[i]) - height[i];12        return water;13    }14}

Move the side with the smaller wall; its running max is the true limit.

left, right at the ends; leftMax = rightMax = 0.
If h[left] < h[right]: the right side has a wall ≥ h[left], so water at left = leftMax − h[left]. Move left.
Otherwise do the mirror on the right.

timeO(n)

One pass.

spaceO(1)

Four variables.

java

1class Solution {2    public int trap(int[] height) {3        int left = 0, right = height.length - 1;4        int leftMax = 0, rightMax = 0, water = 0;5        while (left < right) {6            if (height[left] < height[right]) {7                // the right side has a wall at least this tall, so leftMax decides8                leftMax = Math.max(leftMax, height[left]);9                water += leftMax - height[left];10                left++;11            } else {12                rightMax = Math.max(rightMax, height[right]);13                water += rightMax - height[right];14                right--;15            }16        }17        return water;18    }19}

sim

Dry run

loading simulation…

java

1class Solution {2    public int trap(int[] height) {3        int left = 0, right = height.length - 1;4        int leftMax = 0, rightMax = 0, water = 0;5        while (left < right) {6            if (height[left] < height[right]) {7                // the right side has a wall at least this tall, so leftMax decides8                leftMax = Math.max(leftMax, height[left]);9                water += leftMax - height[left];10                left++;11            } else {12                rightMax = Math.max(rightMax, height[right]);13                water += rightMax - height[right];14                right--;15            }16        }17        return water;18    }19}

in the room

How to say it in the interview

talk track

Start from the per-bar formula — it makes every approach obvious.
Present prefix arrays first, then optimise space with two pointers. Mention the monotonic-stack approach as an alternative.

traps

Writing leftMax − height[i] before updating leftMax: the result goes negative on a new tallest bar.
Moving the taller side: its running max is not the real limit, so the water you add is wrong.

what they ask next

Follow-ups

Trapping Rain Water II (LC 407) — a 2D height map?

Use a min-heap of boundary cells and expand inwards (Dijkstra-like). O(mn log(mn)).

before you submit

Edge cases to test

One or two bars: nothing can be trapped → 0.
Heights only rising or only falling → 0 (there's no wall on one side).
A pit between two equal walls: [3, 0, 3] → 3.
Big totals: 2·10⁴ bars × heights up to 10⁵ stays below 2·10⁹, so an int just fits.

practise next