# Trapping Rain Water

`Two Pointers`, `Stack`, `Dynamic Programming`

Hard

## Question

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.

Trapping Rain Water

Example

Given `[0,1,0,2,1,0,1,3,2,1,2,1]`, return `6`.

Challenge

O(n) time and O(1) memory

O(n) time and O(n) memory is also acceptable.

Tags

Two Pointers Forward-Backward Traversal Array

Related Problems

• Medium Container With Most Water
• Hard Trapping Rain Water II
• Candy

## Analysis

#### Brute Force

Time Complexity O(n^2), Space Complexity O(1)

#### Dynamic Programming

（1）左侧最大height和当前bar的height的差值（left[i] - heights[i]）

（2）右侧最大height和当前bar的height的差值（right[i] - heights[i]），

The water each bar can trap depends on the maximum height on its left and right. Thus scan twice - from left to right, and right to left and record the max height in each direction. The third time calculate the min difference between left/right height and current bar height. Sum the trapped water to get the final result.

dpLeft[i] = Math.max(dpLeft[i - 1], height[i]);
dpRight[i] = Math.max(dpRight[i + 1], height[i]);

Time: O(N), Space: O(2*N)

#### Two Pointers

@Grandyang: 我们来看一种只需要遍历一次即可的解法，这个算法需要left和right两个指针分别指向数组的首尾位置，从两边向中间扫描，在当前两指针确定的范围内，先比较两头找出较小值，如果较小值是left指向的值，则从左向右扫描，如果较小值是right指向的值，则从右向左扫描，若遇到的值比当较小值小，则将差值存入结果，如遇到的值大，则重新确定新的窗口范围，以此类推直至left和right指针重合。

Time: O(N), Space: O(1)

#### Monotonic Stack

@reeestart: 和largest rectangle in histogram一样的思路. 只不过histogram是用递增栈, 这道题是使用递减栈. stack里存的也是index.

• height[stk.peek()] < height[stk.peek().peek()], stk.peek().peek() 就是栈顶第二大的元素.
• height[stk.peek()] < height[i]

## Solution

#### Brute Force

``````class Solution {
public int trap(int[] height) {
if (height == null || height.length <= 2) {
return 0;
}
int ans = 0;
for (int i = 0; i < height.length; i++) {
int leftMax = 0;
int rightMax = 0;
int j = i - 1;
int k = i + 1;
int waterHeight = 0;
while (j >= 0) {
leftMax = Math.max(height[j], leftMax);
j--;
}
while (k < height.length) {
rightMax = Math.max(height[k], rightMax);
k++;
}
waterHeight = Math.min(leftMax, rightMax);
ans += Math.max(waterHeight - height[i], 0);
}
return ans;
}
}
``````

#### Dynamic Programming

``````public class Solution {
/**
* @param heights: an array of integers
* @return: a integer
*/
public int trapRainWater(int[] heights) {
if (heights == null || heights.length < 3) {
return 0;
}
int length = heights.length;

int[] left = new int[length];
int[] right = new int[length];

int trapped = 0;

// For heights[0] or heights[length - 1], the max left/right height is 0
left[0] = 0;
right[length - 1] = 0;

// Keep track of the max height on the left of height[i]
for (int i = 1; i < length; i++) {
left[i] = Math.max(left[i - 1], heights[i - 1]);
}

// Keep track of the max height on the right of height[i]
for (int j = length - 2; j >= 0; j--) {
right[j] = Math.max(right[j + 1], heights[j + 1]);
}

// Calculate the total trapped water
for (int k = 0; k < length; k++) {
trapped += Math.max(Math.min(left[k], right[k]) - heights[k], 0);
}

return trapped;
}
}
``````

#### Two Pointers

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

#### Monotonic Stack

``````class Solution {
public int trap(int[] height) {
int n = height.length;
Stack<Integer> stk = new Stack<>();
int res = 0;
for (int i = 0; i < n; i++) {
if (stk.isEmpty() || height[i] < height[stk.peek()]) {
stk.push(i);
} else {
while (!stk.isEmpty() && height[i] >= height[stk.peek()]) {
int h = height[stk.pop()];
if (!stk.isEmpty()) {
int len = i - stk.peek() - 1;
res += (Math.min(height[i], height[stk.peek()]) - h) * len;
}
}
stk.push(i);
}
}
return res;
}
}
``````