Trapping Rain Water

Find how much rain water the map can trap.

Trapping Rain Water

Problem

You are given n non-negative integers. They show an elevation map, where each bar has a width of 1. Find how much rain water the map can trap.

Examples

Example 1

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

• 6 units of water are trapped in the gaps between the bars.

Example 2

Input: height = [4,2,0,3,2,5]
Output: 9

Constraints

• n == height.length
• 1 <= n <= 2 * 10^4
• 0 <= height[i] <= 10^5

Main Idea

Look at one bar at index i. The water above it depends on two walls:

• leftMax: the tallest bar from index 0 to i.
• rightMax: the tallest bar from index i to n - 1.

Water can rise only up to the shorter of the two walls. If it rises higher, it spills over the shorter wall. So:

water at i = min(leftMax, rightMax) - height[i]

The total answer is the sum of this value for every index.

Note: leftMax and rightMax both include the bar i itself. So the result is never negative.

Brute Force (For Comparison)

For every index, scan to the left and to the right to find the two maximum values.

var trap = function (height) {
    let total = 0;

    for (let i = 0; i < height.length; i++) {
        let leftMax = 0;
        let rightMax = 0;

        for (let l = 0; l <= i; l++) {
            leftMax = Math.max(leftMax, height[l]);
        }

        for (let r = i; r < height.length; r++) {
            rightMax = Math.max(rightMax, height[r]);
        }

        total += Math.min(leftMax, rightMax) - height[i];
    }

    return total;
};

Complexity

• Time Complexity: O(n²)
  • For each index, we scan the array again.
• Space Complexity: O(1)
  • We use only a few variables.

Solution 1: Prefix and Suffix Arrays

The brute force repeats the same scans. We can compute all leftMax and rightMax values once and save them.

• left[i] is the tallest bar from 0 to i.
• right[i] is the tallest bar from i to n - 1.

var trap = function (height) {
    const n = height.length;

    const left = new Array(n);
    const right = new Array(n);

    // tallest bar from the left
    left[0] = height[0];
    for (let i = 1; i < n; i++) {
        left[i] = Math.max(left[i - 1], height[i]);
    }

    // tallest bar from the right
    right[n - 1] = height[n - 1];
    for (let i = n - 2; i >= 0; i--) {
        right[i] = Math.max(right[i + 1], height[i]);
    }

    // add the water above each bar
    let total = 0;
    for (let i = 0; i < n; i++) {
        total += Math.min(left[i], right[i]) - height[i];
    }

    return total;
};

How the Code Works

• Step 1: Fill left from left to right. Each value is the bigger of the previous left value and the current bar.
• Step 2: Fill right from right to left in the same way.
• Step 3: For each index, the water is min(left[i], right[i]) - height[i]. We add all of them.

Dry Run

Let us take height = [4, 2, 0, 3, 2, 5].

The total is 0 + 2 + 4 + 1 + 2 + 0 = 9.

Complexity

• Time Complexity: O(n)
  • We use three simple loops.
• Space Complexity: O(n)
  • The left and right arrays hold n values each.

Solution 2: Two Pointers (Optimal)

We can remove the two arrays. The key point is this:

The water at an index depends on the smaller of the two walls. So if we know one side's wall is smaller, we do not need the exact value of the other side.

We use two pointers, l at the start and r at the end. We also keep leftMax and rightMax as we move.

• If height[l] < height[r], then the left side is the smaller wall. There is a wall on the right that is at least as tall as height[r], so rightMax >= height[l]. This means the water at l depends only on leftMax.
  • If height[l] >= leftMax, no water is trapped. We update leftMax.
  • Otherwise, we add leftMax - height[l].
  • Then we move l forward.
• Otherwise, we do the same on the right side with rightMax, and move r backward.

var trap = function (height) {
    let l = 0;
    let r = height.length - 1;

    let leftMax = 0;
    let rightMax = 0;
    let total = 0;

    while (l < r) {
        if (height[l] < height[r]) {
            // the left side is the smaller wall
            if (height[l] >= leftMax) {
                leftMax = height[l];
            } else {
                total += leftMax - height[l];
            }
            l++;
        } else {
            // the right side is the smaller (or equal) wall
            if (height[r] >= rightMax) {
                rightMax = height[r];
            } else {
                total += rightMax - height[r];
            }
            r--;
        }
    }

    return total;
};

How the Code Works

• Step 1: l and r start at both ends. leftMax and rightMax start at 0.
• Step 2: We always move the pointer that has the smaller bar. That side is safe, because the other side has a taller or equal wall.
• Step 3: If the current bar is a new tallest bar on its side, it traps no water, so we update the max. Otherwise, it traps max - height water.
• Step 4: The loop ends when the pointers meet. Every index was handled once.

Dry Run

Let us take height = [4, 2, 0, 3, 2, 5].

The answer is 9.

Complexity

• Time Complexity: O(n)
  • Each step moves one pointer, so we visit each index once.
• Space Complexity: O(1)
  • We use only a few variables.

Solution 3: Monotonic Stack (Optional)

We can also count water in layers. We keep a stack of indexes with decreasing heights. When a taller bar arrives, the bar on top of the stack is a "valley" between two walls.

var trap = function (height) {
    const stack = [];
    let total = 0;

    for (let i = 0; i < height.length; i++) {
        // the current bar is taller than the top, so we found a valley
        while (stack.length > 0 && height[i] > height[stack[stack.length - 1]]) {
            const bottom = stack.pop();

            // no left wall, so no water can be trapped
            if (stack.length === 0) break;

            const leftWall = stack[stack.length - 1];
            const width = i - leftWall - 1;
            const h = Math.min(height[leftWall], height[i]) - height[bottom];

            total += width * h;
        }

        stack.push(i);
    }

    return total;
};

• bottom is the valley floor. leftWall is the next bar in the stack. i is the right wall.
• The water layer has width = i - leftWall - 1 and h = min(left wall, right wall) - floor.
• Each index is pushed once and popped at most once.

Complexity

• Time Complexity: O(n)
• Space Complexity: O(n)
  • In the worst case, the stack holds all indexes, for example when the heights only go down.

Comparison

Summary

• The water above a bar is min(leftMax, rightMax) - height[i].
• Brute force finds both maximums for each bar. It takes O(n²) time.
• The prefix and suffix arrays save the maximums once. This gives O(n) time but uses O(n) space.
• The two pointers solution moves the pointer with the smaller bar. That side is limited only by its own max, so we do not need the arrays.
• The monotonic stack counts water layer by layer.
• The two pointers solution is the best: O(n) time and O(1) space.