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 can trap after raining.
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
Constraints:
n == height.length
1 <= n <= 2 * 104
0 <= height[i] <= 105
Trapping Rain Water Solutions
✅Time: O(n)
✅Space: O(n)
C++
class Solution {
public:
int trap(vector<int>& height) {
const int n = height.size();
int ans = 0;
vector<int> l(n); // l[i] := max(height[0..i])
vector<int> r(n); // r[i] := max(height[i..n))
for (int i = 0; i < n; ++i)
l[i] = i == 0 ? height[i] : max(height[i], l[i - 1]);
for (int i = n - 1; i >= 0; --i)
r[i] = i == n - 1 ? height[i] : max(height[i], r[i + 1]);
for (int i = 0; i < n; ++i)
ans += min(l[i], r[i]) - height[i];
return ans;
}
};
Java
class Solution {
public int trap(int[] height) {
final int n = height.length;
int ans = 0;
int[] l = new int[n]; // l[i] := max(height[0..i])
int[] r = new int[n]; // r[i] := max(height[i..n))
for (int i = 0; i < n; ++i)
l[i] = i == 0 ? height[i] : Math.max(height[i], l[i - 1]);
for (int i = n - 1; i >= 0; --i)
r[i] = i == n - 1 ? height[i] : Math.max(height[i], r[i + 1]);
for (int i = 0; i < n; ++i)
ans += Math.min(l[i], r[i]) - height[i];
return ans;
}
}
Python
class Solution:
def trap(self, height: List[int]) -> int:
n = len(height)
l = [0] * n # l[i] := max(height[0..i])
r = [0] * n # r[i] := max(height[i..n))
for i, h in enumerate(height):
l[i] = h if i == 0 else max(h, l[i - 1])
for i, h in reversed(list(enumerate(height))):
r[i] = h if i == n - 1 else max(h, r[i + 1])
return sum(min(l[i], r[i]) - h
for i, h in enumerate(height))
Watch Tutorial
Checkout more Solutions here