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
Brute Force
n = height.size()
Time complexity: O($n^2$)
Space complexity: O(1)
class Solution {
public:
int trap(const vector<int>& height) {
int water_count = 0;
for (size_t i = 0; i < height.size(); ++i) {
int max_left_height = 0;
for (int j = i - 1; j >= 0; --j) {
max_left_height = max(max_left_height, height[j]);
}
int max_right_height = 0;
for (int j = i + 1; j < height.size(); ++j) {
max_right_height = max(max_right_height, height[j]);
}
water_count += max(min(max_left_height, max_right_height) - height[i], 0);
}
return water_count;
}
};
Dynamic Programming
n = height.size()
Time complexity: O(n)
Space complexity: O(n)
class Solution {
public:
int trap(const vector<int>& height) {
vector<int> max_left_height(height.size());
for (int i = 1; i < height.size(); ++i) {
max_left_height[i] = max(max_left_height[i - 1], height[i - 1]);
}
vector<int> max_right_height(height.size());
for (int i = height.size() - 1 - 1; i >= 0; --i) {
max_right_height[i] = max(max_right_height[i + 1], height[i + 1]);
}
int water_count = 0;
for (int i = 0; i < height.size(); ++i) {
water_count += max(min(max_left_height[i], max_right_height[i]) - height[i], 0);
}
return water_count;
}
};
Two Pointers
n = height.size()
Time complexity: O(n)
Space complexity: O(1)
class Solution {
public:
int trap(const vector<int>& height) {
int water_count = 0;
int max_left_height = 0, max_right_height = 0;
int left_index = 1, right_index = height.size() - 1 - 1;
for (int i = 1; i < height.size() - 1; ++i) {
// we don't need the value of max left height or max right height
// we just need the value of min(max_left_height, max_right_height)
// when the left index's value is smaller than the right index's value
// it must smaller than that column's real max right height, we don't care what it is
// but we know it's safe to update the left index's value
if (height[left_index - 1] < height[right_index + 1]) {
max_left_height = max(max_left_height, height[left_index - 1]);
water_count += max(max_left_height - height[left_index], 0);
++left_index;
} else {
max_right_height = max(max_right_height, height[right_index + 1]);
water_count += max(max_right_height - height[right_index], 0);
--right_index;
}
}
return water_count;
}
};