Total Rainwater Trapped Across an Elevation Map

Hard25–35 min

Topics

ArrayTwo Pointer

Companies

AmazonGoogleMicrosoftAdobeBloomberg

You're given an array height where each value is the height of a unit-width bar standing at that position. After it rains, water settles in the dips between bars — compute the total volume of water trapped across the whole map. Try to avoid two extra O(n) arrays for the left/right running maximums — a two-pointer sweep from both ends can get you there in O(1) extra space.

Test Case 1:

Input:height = [2, 0, 3, 0, 4, 0, 1]

Output:6

Explanation:Water pools above the 0s wherever a taller bar stands on both sides of it.

Test Case 2:

Input:height = [4, 1, 3, 1, 5, 2]

Output:7

Explanation:Both dips (at index 1 and index 3) hold water up to the shorter of their two surrounding walls.

Test Case 3:

Input:height = [1, 0, 2]

Output:1

Explanation:A single unit of water sits above the 0, capped by min(1, 2) = 1.

Constraints

◆1 ≤ height.length ≤ 2 × 10⁴
◆0 ≤ height[i] ≤ 10⁵

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

🧪Try your own test case

height (array) — 1-14 non-negative integers, separated by commas or spaces

1	class Solution {
2	public int totalRainwaterTrapped(int[] height) {
3	int left = 0, right = height.length - 1;
4	int leftMax = 0, rightMax = 0;
5	int total = 0;
6	while (left < right) {
7	if (height[left] <= height[right]) {
8	leftMax = Math.max(leftMax, height[left]);
9	total += leftMax - height[left];
10	left++;
11	} else {
12	rightMax = Math.max(rightMax, height[right]);
13	total += rightMax - height[right];
14	right--;
15	}
16	}
17	return total;
18	}
19	}
20

↑left

↑right

Variables

left0

right6

leftMax0

rightMax0

total0

INITIALIZE

left starts at index 0, right at index 6. leftMax, rightMax, and total all start at 0.

Step 1 / 14

Approach & Solutions

Brute Force — Scan Both Sides for Every Bar

Brute

For every bar, the water sitting above it is capped by the shorter of the tallest wall to its left and the tallest wall to its right. Find those two walls by scanning outward from that bar in each direction, then add min(leftMax, rightMax) - height[i] to the running total (it never goes negative, since leftMax and rightMax both include the bar itself). Repeating the two scans for every index costs O(n²).

TimeO(n²)

SpaceO(1)

Java

Try it out

class Solution {
    public int totalRainwaterTrapped(int[] height) {
        int total = 0;
        for (int i = 0; i < height.length; i++) {
            int leftMax = 0, rightMax = 0;
            for (int j = 0; j <= i; j++) leftMax = Math.max(leftMax, height[j]);
            for (int j = i; j < height.length; j++) rightMax = Math.max(rightMax, height[j]);
            total += Math.min(leftMax, rightMax) - height[i];
        }
        return total;
    }
}

Better — Precompute Left/Right Max Arrays

Better

Precompute two helper arrays in two clean linear passes: leftMax[i] holds the tallest bar from the start up through i, and rightMax[i] holds the tallest bar from i through the end. With both ready, a third pass adds min(leftMax[i], rightMax[i]) - height[i] at every index. No repeated inner scans like the brute force, but it costs O(n) extra space for the two helper arrays — space the two-pointer version below doesn't need.

TimeO(n)

SpaceO(n)

Java

Try it out

class Solution {
    public int totalRainwaterTrapped(int[] height) {
        int n = height.length;
        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 total = 0;
        for (int i = 0; i < n; i++) {
            total += Math.min(leftMax[i], rightMax[i]) - height[i];
        }
        return total;
    }
}

Optimal — Two Pointers with Running Maxes

Optimal

Walk inward from both ends at once, tracking the tallest wall seen so far from the left (leftMax) and from the right (rightMax). Whichever side currently has the shorter running max is the side whose water level is already fully decided — that bar's cap can't come from further away on the other side, since the current far wall is at least as tall as the near one. So process that side: add its trapped water and step it inward. One pass, no extra arrays.

TimeO(n)

SpaceO(1) extra

Java

Try it out

class Solution {
    public int totalRainwaterTrapped(int[] height) {
        int left = 0, right = height.length - 1;
        int leftMax = 0, rightMax = 0;
        int total = 0;
        while (left < right) {
            if (height[left] <= height[right]) {
                leftMax = Math.max(leftMax, height[left]);
                total += leftMax - height[left];
                left++;
            } else {
                rightMax = Math.max(rightMax, height[right]);
                total += rightMax - height[right];
                right--;
            }
        }
        return total;
    }
}

Total Rainwater Trapped Across an Elevation Map

Constraints

Try the Dry Run

Approach & Solutions

Brute Force — Scan Both Sides for Every Bar

Better — Precompute Left/Right Max Arrays

Optimal — Two Pointers with Running Maxes

Related Problems