## Trapping Rain Water

https://leetcode.com/problems/trapping-rain-water/description/

## Problem Description

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

![42.trapping-rain-water-1](https://tva1.sinaimg.cn/large/007S8ZIlly1ghlu2p6pzfj30bg04hmx3.jpg)

> The above elevation map 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. Thanks Marcos for contributing this image!

```
Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
```

## Prerequisites

- Space-time tradeoff
- Two Pointers
- Monotonic Stack

## Two Arrays

### Solution

The difficulty of this problem is `hard`.
We'd like to compute how much water a given elevation map can trap.

A brute force solution would be adding up the maximum level of water that each element of the map can trap.

Pseudo Code:

```js
for (let i = 0; i < height.length; i++) {
  area += h[i] - height[i]; // the maximum level of water that the element i can trap
}
```

Now the problem becomes how to calculating h[i], which is in fact the minimum of maximum height of bars on both sides minus height[i]:
`h[i] = Math.min(leftMax, rightMax)` where `leftMax = Math.max(leftMax[i-1], height[i])` and `rightMax = Math.max(rightMax[i+1], height[i])`.

For the given example, h would be [0, 1, 1, 2, 2, 2 ,2, 3, 2, 2, 2, 1].

The key is to calculate `leftMax` and `rightMax`.

### Key Points

- Figure out the modeling of `h[i] = Math.min(leftMax, rightMax)`

### Code (JavaScript/Python3/C++)

JavaScript Code:

```js
/*
 * @lc app=leetcode id=42 lang=javascript
 *
 * [42] Trapping Rain Water
 *
 */
/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function (height) {
  let max = 0;
  let volume = 0;
  const leftMax = [];
  const rightMax = [];

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

  max = 0;

  for (let i = height.length - 1; i >= 0; i--) {
    rightMax[i] = max = Math.max(height[i], max);
  }

  for (let i = 0; i < height.length; i++) {
    volume = volume + Math.min(leftMax[i], rightMax[i]) - height[i];
  }

  return volume;
};
```

Python Code:

```python
class Solution:
    def trap(self, heights: List[int]) -> int:
        n = len(heights)
        l, r = [0] * (n + 1), [0] * (n + 1)
        ans = 0
        for i in range(1, len(heights) + 1):
            l[i] = max(l[i - 1], heights[i - 1])
        for i in range(len(heights) - 1, 0, -1):
            r[i] = max(r[i + 1], heights[i])
        for i in range(len(heights)):
            ans += max(0, min(l[i + 1], r[i]) - heights[i])
        return ans
```

C++ code:

```c++
int trap(vector<int>& heights)
{
	if(heights == null)
		return 0;
    int ans = 0;
    int size = heights.size();
    vector<int> left_max(size), right_max(size);
    left_max[0] = heights[0];
    for (int i = 1; i < size; i++) {
        left_max[i] = max(heights[i], left_max[i - 1]);
    }
    right_max[size - 1] = heights[size - 1];
    for (int i = size - 2; i >= 0; i--) {
        right_max[i] = max(heights[i], right_max[i + 1]);
    }
    for (int i = 1; i < size - 1; i++) {
        ans += min(left_max[i], right_max[i]) - heights[i];
    }
    return ans;
}

```

**Complexity Analysis**

- Time Complexity: $O(N)$
- Space Complexity: $O(N)$

## Two Pointers

### Solution

The above code is easy to understand, but it needs the extra space of N. We can tell from it that we in fact only cares about the minimum of (left[i], right[i]). Specifically:

- If l[i + 1] < r[i], the maximum in the left side of i will determine the height of trapping water.
- If l[i + 1] >= r[i], the maximum in the right side of i will determine the height of trapping water.

Thus, we don't need to keep two complete arrays. We can rather keep only a left max and a right max, using constant variable. This problem is a typical two pointers problem.

Algorithm:

1. Initialize two pointers `left` and `right`, pointing to the begin and the end of our height array respectively.
2. Initialize the left maximum height and the right maximum height to be 0.
3. Compare height[left] and height[right]

- If height[left] < height[right]
  - 3.1.1 If height[left] >= left_max, the current trapping volume is (left_max - height[left])
  - 3.1.2 Otherwise, no water is trapped and the volume is 0
- 3.2 Iterate the left pointer to the right
- 3.3 If height[left] >= height[right]
  - 3.3.1 If height[right] >= right_max, the current trapping volume is (right_max - height[right])
  - 3.3.2 Otherwise, no water is trapped and the volume is 0
- 3.4 Iterate the right pointer to the left

### Code (Python3/C++)

```python
class Solution:
    def trap(self, heights: List[int]) -> int:
        n = len(heights)
        l_max = r_max = 0
        l, r = 0, n - 1
        ans = 0
        while l < r:
            if heights[l] < heights[r]:
                if heights[l] < l_max:
                    ans += l_max - heights[l]
                else:
                    l_max = heights[l]
                l += 1
            else:
                if heights[r] < r_max:
                    ans += r_max - heights[r]
                else:
                    r_max = heights[r]
                r -= 1
        return ans
```

```c++

class Solution {
public:
    int trap(vector<int>& heights)
{
    int left = 0, right = heights.size() - 1;
    int ans = 0;
    int left_max = 0, right_max = 0;
    while (left < right) {
        if (heights[left] < heights[right]) {
            heights[left] >= left_max ? (left_max = heights[left]) : ans += (left_max - heights[left]);
            ++left;
        }
        else {
            heights[right] >= right_max ? (right_max = heights[right]) : ans += (right_max - heights[right]);
            --right;
        }
    }
    return ans;
}

};
```

**Complexity Analysis**

- Time Complexity: $O(N)$
- Space Complexity: $O(1)$

## Similar Problems

- [84.largest-rectangle-in-histogram](https://github.com/azl397985856/leetcode/blob/master/problems/84.largest-rectangle-in-histogram.md)

For more solutions, visit my [LeetCode Solution Repo](https://github.com/azl397985856/leetcode) (which has 30K stars).

Follow my WeChat official account 力扣加加, which has lots of graphic solutions and teaches you how to recognize problem patterns to solve problems with efficiency.

![](https://tva1.sinaimg.cn/large/007S8ZIlly1ghlu2wi41cj30p00dwt9t.jpg)
