> For the complete documentation index, see [llms.txt](https://jaywin.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jaywin.gitbook.io/leetcode/solutions/0042-trapping-rain-water.md).

# 0042. Trapping Rain Water

<https://leetcode.com/problems/trapping-rain-water>

## Description

Given `n` non-negative integers representing an elevation map where the width of each bar is `1`, compute how much water it can trap after raining.

**Example 1:**

![](https://assets.leetcode.com/uploads/2018/10/22/rainwatertrap.png)

```
**Input:** height = [0,1,0,2,1,0,1,3,2,1,2,1]
**Output:** 6
**Explanation:** The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.
```

**Example 2:**

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

**Constraints:**

* `n == height.length`
* `1 <= n <= 2 * 104`
* `0 <= height[i] <= 105`

## ac1: two pointers

[https://leetcode.com/problems/trapping-rain-water/discuss/17357/Sharing-my-simple-c%2B%2B-code%3A-O(n)-time-O(1)-space](https://leetcode.com/problems/trapping-rain-water/discuss/17357/Sharing-my-simple-c%2B%2B-code%3A-O%28n%29-time-O%281%29-space)

```java
class Solution {
    public int trap(int[] height) {
        int res = 0;
        int leftMax = 0, rightMax = 0, left = 0, right = height.length - 1;
        
        while (left <= right) {
            if (leftMax < rightMax) {
                if (height[left] >= leftMax) {
                    leftMax = height[left];
                } else {
                    res += leftMax - height[left];
                }
                left++;
            } else {
                if (height[right] >= rightMax) {
                    rightMax = height[right];
                } else {
                    res += rightMax - height[right];
                } 
                right--;
            }
        }
        
        return res;
    }
}
```

## ac2: brute force

```java
class Solution {
    public int trap(int[] height) {
        int n = height.length;
        // edge cases
        if (n < 3) return 0;

        int water = 0;
        // 1st pass walk through, 2nd pass find left max, 3rd pass find right max
        for (int i = 0; i < n; i++) {
            // find left max
            int lmax = 0;
            for (int l = 0; l <= i; l++) {
                lmax = Math.max(lmax, height[l]);
            }
            // find right max
            int rmax = 0;
            for (int r = n-1; r >= i; r--) {
                rmax = Math.max(rmax, height[r]);
            }
            // calculate water volumn
            water += Math.min(rmax, lmax) - height[i];
        }

        // result
        return water;
    }
}

/*
brute force, O(n2) time + O(1) space
DP-like memorization + 3 pass, O(3n) time + O(2n) space
stack + 1 pass, O(n) time + O(n) space
two pointers + 1 pass, O(n) time + O(1) space
*/
```

## ac3: DP-like memorization

```java
class Solution {
    public int trap(int[] height) {
        int n = height.length;
        // edge cases
        if (n < 3) return 0;

        int[] lmax = new int[n];
        int[] rmax = new int[n];
        lmax[0] = height[0];
        rmax[n-1] = height[n-1];

        // find left max
        for (int i = 1; i < n; i++) {
            lmax[i] = Math.max(lmax[i-1], height[i]);
        }
        // find right max
        for (int i = n - 2; i >= 0; i--) {
            rmax[i] = Math.max(rmax[i+1], height[i]);
        }

        // accumulate water
        int water = 0;
        for (int i = 0; i < n; i++) {
            water += Math.min(lmax[i], rmax[i]) - height[i];
        }

        // result
        return water;
    }
}
```

## ac4: stack

Very hard to understand, doubt if it's suitable for interview.\
<https://leetcode.com/problems/trapping-rain-water/discuss/17414/A-stack-based-solution-for-reference-inspired-by-Histogram>

```java
class Solution {
    public int trap(int[] height) {
        int n = height.length;
        int water = 0;
        // edge cases
        if (n < 3) return 0;

        // stack 
        Stack<Integer> stack = new Stack<Integer>();
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
                int bottom = height[stack.pop()];
                if (stack.isEmpty()) break;
                int length = i - stack.peek() - 1;
                int h = Math.min(height[i], height[stack.peek()]) - bottom;
                water += length * h;
            }
            stack.push(i);
        }

        // result
        return water;
    }
}
```