42. Trapping Rain Water
1. 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.
2. Example
Example 1
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
3. Constraints
- n == height.length
- 1 <= n <= 2 * $10^4$
- 0 <= height[i] <= $10^5$
4. Solutions
Dynamic Programming
n = height.size()
Time complexity: O(n)
Space complexity: O(n)
class Solution {
public:
int trap(const vector<int> &height) {
const int n = height.size();
vector<int> left_max_height = height;
for (int i = 1; i < n; ++i) {
left_max_height[i] = max(left_max_height[i - 1], left_max_height[i]);
}
vector<int> right_max_height = height;
for (int i = n - 2; i >= 0; --i) {
right_max_height[i] = max(right_max_height[i + 1], right_max_height[i]);
}
int trapped_water = 0;
for (int i = 1; i < n - 1; ++i) {
trapped_water +=
max(min(left_max_height[i - 1], right_max_height[i + 1]) - height[i], 0);
}
return trapped_water;
}
};
Monotonic Stack
n = height.size()
Time complexity: O(n)
Space complexity: O(n)
class Solution {
public:
int trap(const vector<int> &height) {
const int n = height.size();
vector<int> mono_decrease_indexes;
mono_decrease_indexes.reserve(n);
int trapped_water = 0;
for (int i = 0; i < n; ++i) {
while (!mono_decrease_indexes.empty() &&
height[i] > height[mono_decrease_indexes.back()]) {
int bottom = mono_decrease_indexes.back();
mono_decrease_indexes.pop_back();
if (mono_decrease_indexes.empty()) {
break;
}
int left = mono_decrease_indexes.back();
int width = i - left - 1;
int bounded_height =
min(height[left], height[i]) - height[bottom];
trapped_water += width * bounded_height;
}
mono_decrease_indexes.push_back(i);
}
return trapped_water;
}
};
Two Pointers
n = height.size()
Time complexity: O(n)
Space complexity: O(1)
class Solution {
public:
int trap(const vector<int> &height) {
const int n = height.size();
int left = 0, right = n - 1, trapped_water = 0;
int left_max_height = 0, right_max_height = 0;
while (left < right) {
if (height[left] < height[right]) {
left_max_height = max(height[left], left_max_height);
trapped_water += left_max_height - height[left];
++left;
} else {
right_max_height = max(height[right], right_max_height);
trapped_water += right_max_height - height[right];
--right;
}
}
return trapped_water;
}
};