.png)
Trapping Rain Water
Problem Statement
You are given an array height[] of non-negative integers where each element represents the height of a bar and the width of each bar is 1.
Calculate how much rainwater can be trapped between the bars after raining.
Example 1
Input
height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output
6
Explanation
Water trapped at each index:
Index: 0 1 2 3 4 5 6 7 8 9 10 11
Water: 0 0 1 0 1 2 1 0 0 1 0 0
Total water = 6
Example 2
Input
height = [4,2,0,3,2,5]
Output
9
Why This Problem Is Important
- Very frequently asked interview problem
- Appears in FAANG & top product companies
- Tests two-pointer & prefix logic
- Classic array + geometry problem
- Helps understand space optimization
- Popular medium-level question
Approaches Overview
| Approach | Technique | Time | Space |
|---|---|---|---|
| Approach 1 | Brute Force | O(n²) | O(1) |
| Approach 2 | Prefix & Suffix Arrays | O(n) | O(n) |
| Approach 3 | Two Pointers (Optimal) | O(n) | O(1) |
Approach 1: Brute Force
Idea
For each bar, find the maximum height to its left and maximum height to its right.
Water at index i:
min(leftMax, rightMax) - height[i]
Algorithm
- For each index i
- Find max height on left
- Find max height on right
- Add trapped water if positive
Time & Space Complexity
- Time: O(n²)
- Space: O(1)
Implementations
C
#include
int main() {
int h[] = {0,1,0,2,1,0,1,3,2,1,2,1};
int n = 12, water = 0;
for(int i = 0; i < n; i++) {
int leftMax = 0, rightMax = 0;
for(int j = 0; j <= i; j++)
if(h[j] > leftMax) leftMax = h[j];
for(int j = i; j < n; j++)
if(h[j] > rightMax) rightMax = h[j];
int trapped = (leftMax < rightMax ? leftMax : rightMax) - h[i];
if(trapped > 0)
water += trapped;
}
printf("%d", water);
return 0;
}
C++
#include
using namespace std;
int main() {
int h[] = {0,1,0,2,1,0,1,3,2,1,2,1};
int n = 12, water = 0;
for(int i = 0; i < n; i++) {
int leftMax = 0, rightMax = 0;
for(int j = 0; j <= i; j++)
leftMax = max(leftMax, h[j]);
for(int j = i; j < n; j++)
rightMax = max(rightMax, h[j]);
water += max(0, min(leftMax, rightMax) - h[i]);
}
cout << water;
return 0;
}
Java
public class TrappingRainWater {
public static void main(String[] args) {
int[] h = {0,1,0,2,1,0,1,3,2,1,2,1};
int water = 0;
for(int i = 0; i < h.length; i++) {
int leftMax = 0, rightMax = 0;
for(int j = 0; j <= i; j++)
leftMax = Math.max(leftMax, h[j]);
for(int j = i; j < h.length; j++)
rightMax = Math.max(rightMax, h[j]);
water += Math.max(0, Math.min(leftMax, rightMax) - h[i]);
}
System.out.print(water);
}
}
Python
height = [0,1,0,2,1,0,1,3,2,1,2,1]
water = 0
for i in range(len(height)):
leftMax = max(height[:i+1])
rightMax = max(height[i:])
water += max(0, min(leftMax, rightMax) - height[i])
print(water)
JavaScript
let height = [0,1,0,2,1,0,1,3,2,1,2,1];
let water = 0;
for (let i = 0; i < height.length; i++) {
let leftMax = 0, rightMax = 0;
for (let j = 0; j <= i; j++)
leftMax = Math.max(leftMax, height[j]);
for (let j = i; j < height.length; j++)
rightMax = Math.max(rightMax, height[j]);
water += Math.max(0, Math.min(leftMax, rightMax) - height[i]);
}
console.log(water);
Approach 2: Prefix & Suffix Arrays
Idea
Precompute:
- leftMax[i] → max height to the left
- rightMax[i] → max height to the right
Algorithm
- Build leftMax array
- Build rightMax array
- Sum min(leftMax[i], rightMax[i]) - height[i]
Time & Space Complexity
- Time: O(n)
- Space: O(n)
Implementations
C++
#include
using namespace std;
int main() {
int h[] = {0,1,0,2,1,0,1,3,2,1,2,1};
int n = 12;
int left[12], right[12];
left[0] = h[0];
for(int i = 1; i < n; i++)
left[i] = max(left[i-1], h[i]);
right[n-1] = h[n-1];
for(int i = n-2; i >= 0; i--)
right[i] = max(right[i+1], h[i]);
int water = 0;
for(int i = 0; i < n; i++)
water += max(0, min(left[i], right[i]) - h[i]);
cout << water;
return 0;
}
Python
height = [0,1,0,2,1,0,1,3,2,1,2,1]
n = len(height)
left = [0]*n
right = [0]*n
left[0] = height[0]
for i in range(1, n):
left[i] = max(left[i-1], height[i])
right[n-1] = height[n-1]
for i in range(n-2, -1, -1):
right[i] = max(right[i+1], height[i])
water = 0
for i in range(n):
water += max(0, min(left[i], right[i]) - height[i])
print(water)
Approach 3: Two Pointers (Optimal)
Idea
Use two pointers from both ends and maintain:
- leftMax
- rightMax
Water is decided by the smaller side.
Algorithm
- Initialize l = 0, r = n-1
- Maintain leftMax, rightMax
- Move the pointer with smaller height
- Add trapped water accordingly
Time & Space Complexity
- Time: O(n)
- Space: O(1)
Implementations
C++
#include
using namespace std;
int main() {
int h[] = {0,1,0,2,1,0,1,3,2,1,2,1};
int n = 12;
int l = 0, r = n - 1;
int leftMax = 0, rightMax = 0, water = 0;
while(l < r) {
if(h[l] <= h[r]) {
leftMax = max(leftMax, h[l]);
water += leftMax - h[l];
l++;
} else {
rightMax = max(rightMax, h[r]);
water += rightMax - h[r];
r--;
}
}
cout << water;
return 0;
}
Java
public class TrappingRainWater {
public static void main(String[] args) {
int[] h = {0,1,0,2,1,0,1,3,2,1,2,1};
int l = 0, r = h.length - 1;
int leftMax = 0, rightMax = 0, water = 0;
while(l < r) {
if(h[l] <= h[r]) {
leftMax = Math.max(leftMax, h[l]);
water += leftMax - h[l];
l++;
} else {
rightMax = Math.max(rightMax, h[r]);
water += rightMax - h[r];
r--;
}
}
System.out.print(water);
}
}
Python
height = [0,1,0,2,1,0,1,3,2,1,2,1]
l, r = 0, len(height) - 1
leftMax = rightMax = water = 0
while l < r:
if height[l] <= height[r]:
leftMax = max(leftMax, height[l])
water += leftMax - height[l]
l += 1
else:
rightMax = max(rightMax, height[r])
water += rightMax - height[r]
r -= 1
print(water)
JavaScript
let height = [0,1,0,2,1,0,1,3,2,1,2,1];
let l = 0, r = height.length - 1;
let leftMax = 0, rightMax = 0, water = 0;
while (l < r) {
if (height[l] <= height[r]) {
leftMax = Math.max(leftMax, height[l]);
water += leftMax - height[l];
l++;
} else {
rightMax = Math.max(rightMax, height[r]);
water += rightMax - height[r];
r--;
}
}
console.log(water);
Dry Run (Two Pointers)
Input
[0,1,0,2,1,0,1,3,2,1,2,1]
Water added step-by-step → 6 units
Summary
- Brute force is slow
- Prefix-suffix improves time
- Two-pointer is optimal & interview-preferred
- Classic problem to master arrays
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
