SyntaxPilot
Courses/DSA and Coding Problems/Lesson 8

DSA and Coding Problems · Lesson 8 of 90 · 15 min

Trapping Rain Water (hard)

queued

These are the notes for DSA episode 8, the course's first hard problem. Trapping Rain Water (LeetCode 42) asks how much rain stays between bars of different heights. Everything comes from one question about a single bar: how much water sits on top of it? Answer it by scanning (O(n²)), with precomputed running maximums (O(n) time, O(n) space), or with two pointers (O(n) time, O(1) space). Every program below was run in the SyntaxPilot compiler (8-second time limit), and the outputs shown are real.

The problem, in real life

Kids stack bricks into towers in their courtyard, in one row, touching each other, each tower a different height. It rains all night. In the morning, water sits in the dips, wherever a low tower has a taller tower somewhere on its left and somewhere on its right. Water at the edges runs off. How many blocks of water are trapped?

Problem statement

Given n non-negative heights h (each bar is 1 unit wide), return the total trapped water. Constraints: 1 ≤ n ≤ 2 × 10⁴, 0 ≤ h[i] ≤ 10⁵.

h answer
[0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1] 6
[4, 2, 0, 3, 2, 5] 9
[1, 2, 3, 4] 0 (a staircase holds nothing)
[5] 0
[3, 0, 3] 3

This is not Container With Most Water (episode 7): there we picked one pair and ignored the middle; here every bar is solid and every dip fills.

The key question: water on ONE bar

Stand on bar i:

  • leftMax = the tallest bar from index 0 to i (including i)
  • rightMax = the tallest bar from i to n - 1 (including i)
  • Water rises only to the lower of the two (any higher and it spills over that side).
water[i] = min(leftMax, rightMax) - h[i]

Because both maximums include bar i, this is never negative. The answer is the sum over all bars.

Solution 1: brute force (scan both sides for every bar)

public class Main {
    static int trap(int[] h) {
        int water = 0;
        for (int i = 0; i < h.length; i++) {
            int left = 0, right = 0;
            for (int j = 0; j <= i; j++) left = Math.max(left, h[j]);
            for (int j = i; j < h.length; j++) right = Math.max(right, h[j]);
            water += Math.min(left, right) - h[i];
        }
        return water;
    }
    public static void main(String[] args) {
        System.out.println(trap(new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}));
    }
}

Output:

6

On ten lakh bars:

int n = 1000000, h[] = new int[n];
for (int i = 0; i < n; i++) h[i] = (int) (i * 7919L % 1000);
System.out.println(trap(h));

Result: Time Limit Exceeded. n bars × a scan of n = O(n²).

Why it is slow, and the first fix

We keep re-scanning. The tallest bar on the left of bar 5 is just the tallest on the left of bar 4, compared with bar 5. So compute running maximums once, like a prefix sum (episode 5) with max instead of +:

leftMax[i]  = max(leftMax[i-1], h[i])      (left to right)
rightMax[i] = max(rightMax[i+1], h[i])     (right to left)

Dry run: [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]

i 0 1 2 3 4 5 6 7 8 9 10 11
h 0 1 0 2 1 0 1 3 2 1 2 1
leftMax 0 1 1 2 2 2 2 3 3 3 3 3
rightMax 3 3 3 3 3 3 3 3 2 2 2 1
water 0 0 1 0 1 2 1 0 0 1 0 0

Total: 1 + 1 + 2 + 1 + 1 = 6.

Solution 2: prefix max and suffix max arrays

public class Main {
    static int trap(int[] h) {
        int n = h.length, water = 0;
        int[] leftMax = new int[n], rightMax = new int[n];
        leftMax[0] = h[0];
        for (int i = 1; i < n; i++) leftMax[i] = Math.max(leftMax[i - 1], h[i]);
        rightMax[n - 1] = h[n - 1];
        for (int i = n - 2; i >= 0; i--) rightMax[i] = Math.max(rightMax[i + 1], h[i]);
        for (int i = 0; i < n; i++) water += Math.min(leftMax[i], rightMax[i]) - h[i];
        return water;
    }
    public static void main(String[] args) {
        System.out.println(trap(new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}));
        System.out.println(trap(new int[]{4, 2, 0, 3, 2, 5}));
    }
}

Output:

6
9

On ten lakh bars (time varies from run to run):

499486140   26 ms

O(n) time, but O(n) extra space for two arrays (8 MB for a million ints).

Solution 3: two pointers, O(1) space

The formula only uses the smaller of the two maximums. Put l at the left end and r at the right end, and keep leftMax (tallest seen from the left) and rightMax (tallest seen from the right).

  • If h[l] < h[r]: there is a wall at least h[r] tall on the right, which is taller than the left side, so the left side is the bottleneck. Bar l's water is leftMax - h[l], settled without knowing the exact right maximum. Move l.
  • Otherwise: the mirror argument settles bar r with rightMax - h[r]. Move r.

Dry run: [4, 2, 0, 3, 2, 5]

l (h) r (h) side leftMax water added total
0 (4) 5 (5) 4 < 5: left 4 0 0
1 (2) 5 (5) left 4 2 2
2 (0) 5 (5) left 4 4 6
3 (3) 5 (5) left 4 1 7
4 (2) 5 (5) left 4 2 9
5 5 l meets r: stop 9
public class Main {
    static int trap(int[] h) {
        int l = 0, r = h.length - 1, leftMax = 0, rightMax = 0, water = 0;
        while (l < r) {
            if (h[l] < h[r]) {
                leftMax = Math.max(leftMax, h[l]);
                water += leftMax - h[l];
                l++;
            } else {
                rightMax = Math.max(rightMax, h[r]);
                water += rightMax - h[r];
                r--;
            }
        }
        return water;
    }
    public static void main(String[] args) {
        System.out.println(trap(new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}));
        System.out.println(trap(new int[]{4, 2, 0, 3, 2, 5}));
        System.out.println(trap(new int[]{1, 2, 3, 4}));
        System.out.println(trap(new int[]{5}));
        System.out.println(trap(new int[]{3, 0, 3}));
    }
}

Output:

6
9
0
0
3

On ten lakh bars (time varies from run to run):

499486140   10 ms

The same solution in C++ and Python

Both use a 64-bit total (see the overflow bug below).

#include <bits/stdc++.h>
using namespace std;

long long trap(const vector<int>& h) {
    int l = 0, r = (int)h.size() - 1, leftMax = 0, rightMax = 0;
    long long water = 0;
    while (l < r) {
        if (h[l] < h[r]) {
            leftMax = max(leftMax, h[l]);
            water += leftMax - h[l];
            l++;
        } else {
            rightMax = max(rightMax, h[r]);
            water += rightMax - h[r];
            r--;
        }
    }
    return water;
}

int main() {
    cout << trap({0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}) << "\n";   // 6
    cout << trap({4, 2, 0, 3, 2, 5}) << "\n";                     // 9
}
def trap(h):
    l, r = 0, len(h) - 1
    left_max = right_max = water = 0
    while l < r:
        if h[l] < h[r]:
            left_max = max(left_max, h[l])
            water += left_max - h[l]
            l += 1
        else:
            right_max = max(right_max, h[r])
            water += right_max - h[r]
            r -= 1
    return water

print(trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]))  # 6
print(trap([4, 2, 0, 3, 2, 5]))                    # 9

Python integers never overflow, so no long is needed.

The overflow bug

Same ten lakh bars, but the first and last are 100,000 tall (the maximum allowed), so almost everything fills:

h[0] = 100000;
h[n - 1] = 100000;
System.out.println(trap(h));

With int water, the output is:

716052273

Wrong: the real total is about 10¹¹, and an int holds at most 2,147,483,647, so it wrapped around silently (no error). With long water (and static long trap):

99500300081

LeetCode's limits keep the answer inside an int, but mentioning this in an interview shows care.

Complexity

Approach Time Extra space n = 10⁶
Brute force (scan both sides per bar) O(n²) O(1) Time Limit Exceeded
Prefix max + suffix max arrays O(n) O(n) milliseconds
Two pointers O(n) O(1) milliseconds

Common mistakes

Mistake What you see Why Fix
int water on a huge input 716052273 (real total: 99500300081) the total passes 2,147,483,647 and wraps long water
Maximums of h[0..i-1] and h[i+1..] (bar left out) 1 for the first example (answer is 6) on tall bars the level is below the bar: negative water is added include h[i] in both maximums, or add Math.max(0, ...)
Math.max(leftMax[i], rightMax[i]) too much water water would rise above the lower side Math.min
leftMax[0] = h[0] on new int[]{} ArrayIndexOutOfBoundsException: Index 0 out of bounds for length 0 no bars at all if (h.length == 0) return 0; (the two-pointer version needs no check)
Two pointers comparing the wrong side wrong totals settling the taller side uses an unknown bottleneck settle the side with the smaller bar

Mini project: draw the courtyard

Print the bars and the water as text, top row first: # for brick, ~ for water, . for air. Use the two-pointer or prefix version to get water[i] for each bar, then for each level from the tallest bar down to 1, print # if h[i] ≥ level, ~ if h[i] + water[i] ≥ level, else .. For [4, 2, 0, 3, 2, 5] the top row is .....# and the bottom row is ##~###.

Practice

  1. Print the water on every bar of [3, 0, 2, 0, 4].
Solution

Level for each inner bar = min(3, 4) = 3: water [0, 3, 1, 3, 0], total 7.

  1. Solve it with a monotonic stack.
Solution

Keep indexes of decreasing heights. When h[i] is taller than the top, pop the top as the "floor"; the new top is the left wall, i is the right wall. Add (min(h[left], h[i]) - h[floor]) × (i - left - 1). This fills water layer by layer. O(n) time, O(n) space. (Monotonic stacks get their own episode later.)

  1. Trapping Rain Water II (LeetCode 407) is the 2D version. What changes?
Solution

The "lower wall" is now the lowest point of the whole boundary. Push all border cells into a min-heap, repeatedly pop the lowest, and for each unvisited neighbour add max(0, level - height) and push it with height max(level, height). O(mn log(mn)).

  1. Explain in one line why Container With Most Water (episode 7) is a different problem.
Solution

Container picks one pair and the middle walls don't block; Trapping Rain Water fills every dip, and every bar blocks water.

Quick quiz

What does trap(new int[]{5, 1, 3, 0, 4}) return?

  • 8
  • 6
  • 7
  • 4
Answer

8. For every inner bar the tallest on the left is 5 and on the right is 4, so the level is 4: (4 - 1) + (4 - 3) + (4 - 0) = 3 + 1 + 4 = 8.

Interview questions

  1. What is the water above one bar? min(max height to its left, max height to its right) - its height, with both maximums including the bar.
  2. Why is the two-pointer version correct? When h[l] < h[r], the right side has a wall ≥ h[r] > h[l]'s side, so the left maximum is the bottleneck and bar l's water is final.
  3. Time and space of each approach? Brute force O(n²)/O(1), prefix arrays O(n)/O(n), two pointers O(n)/O(1).
  4. Can the answer overflow? With n = 2 × 10⁴ and heights ≤ 10⁵ it is at most 2 × 10⁹, which just fits an int; for bigger limits use long.
  5. How would you handle a 2D grid? A min-heap over the boundary (Trapping Rain Water II).

Glossary

Term Meaning
Elevation map An array of bar heights, each bar 1 unit wide
Trapped water Water held above a bar by taller bars on both sides
leftMax / rightMax The tallest bar on each side of a position, including it
Prefix maximum A running maximum from the left: leftMax[i] = max(leftMax[i-1], h[i])
Suffix maximum A running maximum from the right
Bottleneck The lower of the two walls, which decides the water level
Two pointers Indexes at both ends that move inward, settling one bar per step
Integer overflow A result bigger than the type's maximum (2,147,483,647 for int), which wraps to a wrong value
long Java's 64-bit integer, up to about 9.2 × 10¹⁸
Monotonic stack A stack kept in increasing or decreasing order (a later episode)

Summary

  • Water on bar i = min(leftMax, rightMax) - h[i], both maximums including bar i.
  • Brute force re-scans for every bar: O(n²).
  • Running maximums from both sides: O(n) time, O(n) space.
  • Two pointers settle the side with the smaller bar each step: O(n) time, O(1) space.
  • Use long when the total can pass 2.1 billion.

Next episode: Sliding window: longest substring without repeating characters.