Trapping Rain Water

Q: What is the best time complexity for Trapping Rain Water?

Optimal (two pointers) runs in O(n) time and O(1) extra space. Each step moves one pointer, so there are fewer than n steps.

Q: Which pattern does Trapping Rain Water use?

It is a arrays & hashing problem that uses the two pointer pattern. Other problems with the same pattern: Two Sum II - Input Array Is Sorted, Valid Triangle Number, Container With Most Water.

Q: Is there a brute force solution for Trapping Rain Water?

Yes. Brute force takes O(n²) time and O(1) space. For every column, scan left to find the tallest bar up to it and scan right to find the tallest bar from it.

Q: Which edge cases should I test for Trapping Rain Water?

One or two bars: nothing can be trapped; Strictly increasing or strictly decreasing bars: the answer is 0; Several equal tallest bars, like [3, 0, 3, 0, 3]; Bars of height 0 at both ends.

Hard Arrays & Hashing Two Pointer Original on LeetCode

Reported atAmazon Microsoft Goldman Sachs Salesforce Flipkart

Trapping Rain Water is a hard arrays & hashing problem solved with the two pointer pattern. The best approach, optimal (two pointers), runs in O(n) time and O(1) space. Below are 3 approaches in Java, Python, C++ and JavaScript, from brute force up.

Problem

You are given height, a list of non-negative integers that describe an elevation map: bar i is height[i] units tall and exactly one unit wide.

After a heavy rain, water settles in the dips between bars. Return the total number of units of water the map holds.

Examples

Example 1

Input: height = [3, 0, 2, 0, 4]
Output: 7
Why: Column 1 holds 3, column 2 holds 1 and column 3 holds 3: the walls 3 and 4 cap the water at level 3.

Example 2

Input: height = [1, 4, 2, 1, 3, 5, 0, 2]
Output: 8
Why: Between the 4 and the 5 the columns hold 2 + 3 + 1 = 6, and between the 5 and the last 2 the gap holds 2.

Example 3

Input: height = [5, 4, 3, 2]
Output: 0
Why: The bars only go down, so no column has a taller wall on its right.

Constraints

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

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00

Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 14 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

Approach	Time	Space
Brute force	`O(n²)`	`O(1)`
Better (prefix and suffix maximums)	`O(n)`	`O(n)`
Optimal (two pointers)	`O(n)`	`O(1)`

1Brute force

TimeO(n²)Each of the n columns scans up to n bars.

SpaceO(1)Only a few counters.

For every column, scan left to find the tallest bar up to it and scan right to find the tallest bar from it. The water above the column is the smaller of the two minus its own height.

For each index i, find leftMax = max(height[0..i]) by scanning left.
Find rightMax = max(height[i..n-1]) by scanning right.
Add min(leftMax, rightMax) - height[i] to the total.

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

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

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        int total = 0;
        for (int i = 0; i < n; i++) {
            int leftMax = 0, rightMax = 0;
            for (int j = i; j >= 0; j--) leftMax = max(leftMax, height[j]);
            for (int j = i; j < n; j++) rightMax = max(rightMax, height[j]);
            total += min(leftMax, rightMax) - height[i];
        }
        return total;
    }
};

function trap(height) {
    const n = height.length;
    let total = 0;
    for (let i = 0; i < n; i++) {
        let leftMax = 0, rightMax = 0;
        for (let j = i; j >= 0; j--) leftMax = Math.max(leftMax, height[j]);
        for (let j = i; j < n; j++) rightMax = Math.max(rightMax, height[j]);
        total += Math.min(leftMax, rightMax) - height[i];
    }
    return total;
}

2Better (prefix and suffix maximums)

TimeO(n)Three linear passes.

SpaceO(n)Two extra arrays of length n.

The inner scans repeat work. Precompute leftMax[i] (tallest bar from the start to i) in one pass left to right and rightMax[i] (tallest bar from i to the end) in one pass right to left. Then each column's water is a single lookup.

Fill leftMax: leftMax[0] = height[0], leftMax[i] = max(leftMax[i - 1], height[i]).
Fill rightMax: rightMax[n - 1] = height[n - 1], rightMax[i] = max(rightMax[i + 1], height[i]).
Sum min(leftMax[i], rightMax[i]) - height[i] over all i.

class Solution {
    public int trap(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;
    }
}

class Solution:
    def trap(self, height: List[int]) -> int:
        n = len(height)
        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))

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        vector<int> leftMax(n), rightMax(n);
        leftMax[0] = height[0];
        for (int i = 1; i < n; i++) leftMax[i] = max(leftMax[i - 1], height[i]);
        rightMax[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; i--) rightMax[i] = max(rightMax[i + 1], height[i]);
        int total = 0;
        for (int i = 0; i < n; i++) {
            total += min(leftMax[i], rightMax[i]) - height[i];
        }
        return total;
    }
};

function trap(height) {
    const n = height.length;
    const leftMax = new Array(n);
    const rightMax = new Array(n);
    leftMax[0] = height[0];
    for (let i = 1; i < n; i++) leftMax[i] = Math.max(leftMax[i - 1], height[i]);
    rightMax[n - 1] = height[n - 1];
    for (let i = n - 2; i >= 0; i--) rightMax[i] = Math.max(rightMax[i + 1], height[i]);
    let total = 0;
    for (let i = 0; i < n; i++) {
        total += Math.min(leftMax[i], rightMax[i]) - height[i];
    }
    return total;
}

3Optimal (two pointers)

TimeO(n)Each step moves one pointer, so there are fewer than n steps.

SpaceO(1)Two pointers and two running maximums.

Keep a pointer at each end with the running maximum seen from that side. If leftMax <= rightMax, the left column's level is decided by leftMax, because some bar on the right is at least as tall. So settle the left column and move inward; otherwise settle the right column. No arrays are needed.

Set l = 0, r = n - 1, leftMax = rightMax = 0, total = 0.
While l < r: update leftMax with height[l] and rightMax with height[r].
If leftMax <= rightMax, add leftMax - height[l] and move l right.
Otherwise add rightMax - height[r] and move r left.

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

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

class Solution {
public:
    int trap(vector<int>& height) {
        int l = 0, r = (int)height.size() - 1;
        int leftMax = 0, rightMax = 0;
        int total = 0;
        while (l < r) {
            leftMax = max(leftMax, height[l]);
            rightMax = max(rightMax, height[r]);
            if (leftMax <= rightMax) {
                total += leftMax - height[l];
                l++;
            } else {
                total += rightMax - height[r];
                r--;
            }
        }
        return total;
    }
};

function trap(height) {
    let l = 0, r = height.length - 1;
    let leftMax = 0, rightMax = 0;
    let total = 0;
    while (l < r) {
        leftMax = Math.max(leftMax, height[l]);
        rightMax = Math.max(rightMax, height[r]);
        if (leftMax <= rightMax) {
            total += leftMax - height[l];
            l++;
        } else {
            total += rightMax - height[r];
            r--;
        }
    }
    return total;
}

Edge cases to test

One or two bars: nothing can be trapped
Strictly increasing or strictly decreasing bars: the answer is 0
Several equal tallest bars, like [3, 0, 3, 0, 3]
Bars of height 0 at both ends

Hints

Hint 1

Look at a single column. How high can the water above it rise?

Hint 2

The level over column i is min(tallest bar on its left, tallest bar on its right). Can you precompute both sides?

Hint 3

With two pointers, the side whose running maximum is smaller already knows its water level. Move that side inward.

FAQ

What is the best time complexity for Trapping Rain Water?

Optimal (two pointers) runs in O(n) time and O(1) extra space. Each step moves one pointer, so there are fewer than n steps.

Which pattern does Trapping Rain Water use?

It is a arrays & hashing problem that uses the two pointer pattern. Other problems with the same pattern: Two Sum II - Input Array Is Sorted, Valid Triangle Number, Container With Most Water.

Is there a brute force solution for Trapping Rain Water?

Yes. Brute force takes O(n²) time and O(1) space. For every column, scan left to find the tallest bar up to it and scan right to find the tallest bar from it.

Which edge cases should I test for Trapping Rain Water?

One or two bars: nothing can be trapped; Strictly increasing or strictly decreasing bars: the answer is 0; Several equal tallest bars, like [3, 0, 3, 0, 3]; Bars of height 0 at both ends.