Back to Two Pointers
Hard
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.
Examples
Input:height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output:6
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.
Constraints
n == height.length1 <= n <= 2 * 10^40 <= height[i] <= 10^5
Approach
The amount of water trapped at any index `i` is `min(max_left, max_right) - height[i]`. We can precompute the maximum height to the left of each bar and store it in an array, and do the same for the maximum height to the right. Then, we iterate through the array once more to calculate the trapped water using these precomputed arrays.
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(n)
This approach is conceptually simple but requires O(n) extra space to store the max arrays.
Solution.java
class Solution { public int trap(int[] height) { if (height == null || height.length == 0) return 0; int n = height.length; int[] leftMax = new int[n]; int[] rightMax = new int[n]; // Fill left max array leftMax[0] = height[0]; for (int i = 1; i < n; i++) { leftMax[i] = Math.max(leftMax[i - 1], height[i]); } // Fill right max array rightMax[n - 1] = height[n - 1]; for (int i = n - 2; i >= 0; i--) { rightMax[i] = Math.max(rightMax[i + 1], height[i]); } // Calculate trapped water int trappedWater = 0; for (int i = 0; i < n; i++) { trappedWater += Math.min(leftMax[i], rightMax[i]) - height[i]; } return trappedWater; }}