ArrayProblem 29 of 36
Trapping Rain water problem
Problem Statement
Given an array of non-negative integers representing an elevation map where the width of each bar is 1, compute how much water can be trapped after raining.
Example:
- Input:
height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1] - Output:
6 - Explanation: The elevation map can trap 6 units of rain water.
Approach 1: Brute Force
Intuition
For each element, find the maximum height to its left and right. The water trapped at that position is min(maxLeft, maxRight) - height[i].
Algorithm
- For each position i (except boundaries)
- Find maximum height to the left of i
- Find maximum height to the right of i
- Water at i = min(maxLeft, maxRight) - height[i]
- Sum all positive water values
java
public class Solution {
public int trap(int[] height) {
int n = height.length;
if (n <= 2) return 0;
int totalWater = 0;
for (int i = 1; i < n - 1; i++) {
// Find max height to the left
int maxLeft = 0;
for (int j = 0; j < i; j++) {
maxLeft = Math.max(maxLeft, height[j]);
}
// Find max height to the right
int maxRight = 0;
for (int j = i + 1; j < n; j++) {
maxRight = Math.max(maxRight, height[j]);
}
// Water at position i
int waterLevel = Math.min(maxLeft, maxRight);
if (waterLevel > height[i]) {
totalWater += waterLevel - height[i];
}
}
return totalWater;
}
}Complexity Analysis
- Time Complexity: O(n²) - For each element, we scan left and right subarrays
- Space Complexity: O(1) - Only constant extra space used
Approach 2: Precomputation (Dynamic Programming)
Intuition
Precompute the maximum height to the left and right of each position. Then calculate water at each position.
Algorithm
- Create leftMax[i] = max height from 0 to i
- Create rightMax[i] = max height from i to n-1
- Water at i = min(leftMax[i], rightMax[i]) - height[i]
java
public class Solution {
public int trap(int[] height) {
int n = height.length;
if (n <= 2) return 0;
// Precompute left max
int[] leftMax = new int[n];
leftMax[0] = height[0];
for (int i = 1; i < n; i++) {
leftMax[i] = Math.max(leftMax[i - 1], height[i]);
}
// Precompute right max
int[] rightMax = new int[n];
rightMax[n - 1] = height[n - 1];
for (int i = n - 2; i >= 0; i--) {
rightMax[i] = Math.max(rightMax[i + 1], height[i]);
}
// Calculate total water
int totalWater = 0;
for (int i = 0; i < n; i++) {
totalWater += Math.min(leftMax[i], rightMax[i]) - height[i];
}
return totalWater;
}
}Complexity Analysis
- Time Complexity: O(n) - Three linear passes
- Space Complexity: O(n) - Two arrays for left and right max
Approach 3: Optimal - Two Pointers
Intuition
Use two pointers from both ends. We only need to know the max from one side at a time. Move the pointer with smaller max value.
Algorithm
- Initialize left = 0, right = n-1
- Track leftMax and rightMax
- If height[left] < height[right], process left side
- Else process right side
- Water = max - current height at each step
java
public class Solution {
public int trap(int[] height) {
int n = height.length;
if (n <= 2) return 0;
int left = 0, right = n - 1;
int leftMax = 0, rightMax = 0;
int totalWater = 0;
while (left < right) {
if (height[left] < height[right]) {
if (height[left] >= leftMax) {
leftMax = height[left];
} else {
totalWater += leftMax - height[left];
}
left++;
} else {
if (height[right] >= rightMax) {
rightMax = height[right];
} else {
totalWater += rightMax - height[right];
}
right--;
}
}
return totalWater;
}
}Complexity Analysis
- Time Complexity: O(n) - Single pass with two pointers
- Space Complexity: O(1) - Only constant extra space used
Approach 4: Stack Based
Intuition
Use a stack to track indices of bars. When we find a bar taller than the top of stack, we can calculate water trapped between current bar and bars in the stack.
Algorithm
- Use stack to store indices
- For each bar, pop shorter bars and calculate water
- Water trapped = width × height between bounding bars
java
import java.util.Stack;
public class Solution {
public int trap(int[] height) {
int n = height.length;
if (n <= 2) return 0;
Stack<Integer> stack = new Stack<>();
int totalWater = 0;
for (int i = 0; i < n; i++) {
while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
int top = stack.pop();
if (stack.isEmpty()) break;
int width = i - stack.peek() - 1;
int boundedHeight = Math.min(height[i], height[stack.peek()]) - height[top];
totalWater += width * boundedHeight;
}
stack.push(i);
}
return totalWater;
}
}Complexity Analysis
- Time Complexity: O(n) - Each element pushed and popped at most once
- Space Complexity: O(n) - Stack can store all elements in worst case
Key Takeaways
- Water formula - Water at position i = min(maxLeft, maxRight) - height[i]
- Two pointers insight - We only need the limiting factor (smaller of two maxes)
- Precomputation tradeoff - O(n) space for O(n) time improvement
- Stack for bounded regions - Useful for problems involving enclosed areas
- Classic interview problem - Appears frequently in coding interviews