# 42. Trapping Rain Water
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.
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.
Example:
Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
# Solution
Approach 1: two passes -- for each bar, calculate the height of bars it's bounded by on both directions. Essentially use two passes to store highest_bar_so_far from both sides. O(N) time, O(N) space.
Approach 2: stack -- keep a stack of decreasing/nonincreasing bar heights (indices). Upon seeing a higher bar, pop from the stack and calculate trapped water in between. O(N) time, O(N) space.
Approach 3: two pointers -- the tower of bars and the trapped rain water forms pyramid shape, so we can use 2 pointers to trace the area of the pyramid. O(N) time, O(1) space.
Approach 4: (Time Limit Exceeded) Calculate layer by layer.
# Code (Python)
Approach 1:
def trap(self, height):
if len(height) < 2:
return 0
highest_from_left = [height[0]]
for i in range(1, len(height)):
highest_from_left.append(max(height[i], highest_from_left[-1]))
highest_from_right = [0 for _ in range(len(height) - 1)] + [height[-1]]
for i in range(len(height) - 2, -1, -1):
highest_from_right[i] = max(height[i], highest_from_right[i+1])
total = 0
for i in range(len(height)):
total += min(highest_from_left[i], highest_from_right[i]) - height[i]
return total
Approach 2:
def trap(self, height):
if len(height) < 2:
return 0
stack = []
total = 0
for i in range(len(height)):
while stack and height[i] > height[stack[-1]]:
# calc trapped water with height stack[-1] or higher
base_height = height[stack.pop()]
if not stack:
break # no water trapped if bar just popped isn't bounded on the left
total += (i - stack[-1] - 1) * (min(height[stack[-1]], height[i]) - base_height)
stack.append(i)
return total
Approach 3:
def trap(self, height):
if len(height) < 2:
return 0
prev_elevation = 0
left, right = 0, len(height) - 1
area_pyramid = 0
while left < right:
while height[left] <= prev_elevation and left < right:
left += 1 # can deduct height[left] here to save another pass at the end: sum(height)
while height[right] <= prev_elevation and left < right:
right -= 1
elevation = min(height[left], height[right])
if elevation == prev_elevation: # two pointers meet
return area_pyramid - sum(height)
else:
area_pyramid += (right - left + 1) * (elevation - prev_elevation)
prev_elevation = elevation
return area_pyramid - sum(height) # two pointers meet on a single highest point
# Code (C++)
Approach 1:
// DP.
class Solution {
public:
int trap(vector<int>& height) {
int n = height.size();
if (n == 0) return 0;
int leftMax[n];
int rightMax[n];
leftMax[0] = height[0];
for (int i = 1; i < n; ++i)
leftMax[i] = std::max(leftMax[i-1], height[i]);
rightMax[n-1] = height[n-1];
for (int i = n-2; i >= 0; --i)
rightMax[i] = std::max(rightMax[i+1], height[i]);
int total = 0;
for (int i = 0; i < n; ++i)
{
if (i-1 >= 0 && i+1 < n &&
leftMax[i-1] > height[i] &&
rightMax[i+1] > height[i])
total += std::min(leftMax[i-1], rightMax[i+1]) - height[i];
}
return total;
}
};
Approach 2:
// Stack.
class Solution {
public:
int trap(vector<int>& height) {
stack<int> st;
int total = 0;
for (int i = 0; i < height.size(); ++i)
{
while (!st.empty() && height[st.top()] <= height[i])
{
int j = st.top();
st.pop();
if (!st.empty())
{
int h = std::min(height[st.top()], height[i]);
total += (h - height[j]) * (i - st.top() - 1);
}
}
st.push(i);
}
return total;
}
};
Approach 3:
// Two pointers.
class Solution {
public:
int trap(vector<int>& height) {
int head = 0;
int tail = height.size() - 1;
int headMax = head;
int tailMax = tail;
int total = 0;
while (head <= tail)
{
if (height[headMax] < height[tailMax])
{
if (height[head] >= height[headMax])
{
headMax = head;
head++;
}
else
{
total += height[headMax] - height[head];
head++;
}
}
else
{
if (height[tail] >= height[tailMax])
{
tailMax = tail;
tail--;
}
else
{
total += height[tailMax] - height[tail];
tail--;
}
}
}
return total;
}
};
Approach 4:
// Time Limit Exceeded.
// Calculate layer by layer.
class Solution {
public:
int trap(vector<int>& height) {
int nonZeroCount = 2;
int totalCount = 0;
while (nonZeroCount > 1)
{
nonZeroCount = 0;
int head = 0;
int tail = 0;
int minHeight = 0;
for (int i = 0; i < height.size(); ++i)
{
if (height[i] > 0 && minHeight == 0)
minHeight = height[i];
else if (height[i] > 0)
minHeight = std::min(minHeight, height[i]);
}
while (tail < height.size())
{
if (height[head] == 0)
{
head++;
}
else if (head < tail && height[tail] > 0)
{
totalCount += minHeight * (tail - head - 1);
height[head] -= minHeight;
nonZeroCount++;
head = tail;
}
tail++;
}
if (head < height.size() && height[head] > 0)
{
height[head] -= minHeight;
nonZeroCount++;
}
}
return totalCount;
}
};