Problem Statement:
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:
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.length1 <= n <= 2 * 1040 <= height[i] <= 105
Approach
- Create two arrays
maxL[i]: Max height to the left of indexi(including i).maxR[i]: Max height to the right of indexi(including i).
- Pre-fill
maxLandmaxR:- Traverse from left to right for
maxL. - Traverse from right to left for
maxR.
- Traverse from left to right for
- Calculate water trapped at each index i as:
min(maxL[i], maxR[i]) - height[i]
- Sum it up to get the final answer.
Time Complexity:
Time Complexity = O(n)
Space Complexity:
Space Complexity = O(n)
Dry Run
Input: arr = [0,1,0,2,1,0,1,3,2,1,2,1]
// Step 1: Build maxL array (maximum height to the left including current) Initialize: maxL[0] = arr[0] = 0 i = 1 → maxL[1] = max(maxL[0], arr[1]) = max(0, 1) = 1 i = 2 → maxL[2] = max(1, 0) = 1 i = 3 → maxL[3] = max(1, 2) = 2 i = 4 → maxL[4] = max(2, 1) = 2 i = 5 → maxL[5] = max(2, 0) = 2 i = 6 → maxL[6] = max(2, 1) = 2 i = 7 → maxL[7] = max(2, 3) = 3 i = 8 → maxL[8] = max(3, 2) = 3 i = 9 → maxL[9] = max(3, 1) = 3 i = 10 → maxL[10] = max(3, 2) = 3 i = 11 → maxL[11] = max(3, 1) = 3 Final maxL = [0,1,1,2,2,2,2,3,3,3,3,3] // Step 2: Build maxR array (maximum height to the right including current) Initialize: maxR[11] = arr[11] = 1 i = 10 → maxR[10] = max(arr[10], maxR[11]) = max(2, 1) = 2 i = 9 → maxR[9] = max(1, 2) = 2 i = 8 → maxR[8] = max(2, 2) = 2 i = 7 → maxR[7] = max(3, 2) = 3 i = 6 → maxR[6] = max(1, 3) = 3 i = 5 → maxR[5] = max(0, 3) = 3 i = 4 → maxR[4] = max(1, 3) = 3 i = 3 → maxR[3] = max(2, 3) = 3 i = 2 → maxR[2] = max(0, 3) = 3 i = 1 → maxR[1] = max(1, 3) = 3 i = 0 → maxR[0] = max(0, 3) = 3 Final maxR = [3,3,3,3,3,3,3,3,2,2,2,1] // Step 3: Calculate water trapped at each index Initialize: ans = 0 i = 0 → min(0, 3) - 0 = 0 → ans = 0 i = 1 → min(1, 3) - 1 = 0 → ans = 0 i = 2 → min(1, 3) - 0 = 1 → ans = 1 i = 3 → min(2, 3) - 2 = 0 → ans = 1 i = 4 → min(2, 3) - 1 = 1 → ans = 2 i = 5 → min(2, 3) - 0 = 2 → ans = 4 i = 6 → min(2, 3) - 1 = 1 → ans = 5 i = 7 → min(3, 3) - 3 = 0 → ans = 5 i = 8 → min(3, 2) - 2 = 0 → ans = 5 i = 9 → min(3, 2) - 1 = 1 → ans = 6 i = 10 → min(3, 2) - 2 = 0 → ans = 6 i = 11 → min(3, 1) - 1 = 0 → ans = 6 Final trapped water = 6
Output: Result: 6
Visualisation:
var trap = function(arr) {
let n = arr.length;
let maxL = [];
maxL[0] = arr[0];
for (let i = 1; i < n; i++) {
maxL[i] = Math.max(maxL[i - 1], arr[i]);
}
let maxR = [];
maxR[n - 1] = arr[n - 1];
for (let i = n - 2; i >= 0; i--) {
maxR[i] = Math.max(arr[i], maxR[i + 1]);
}
let ans = 0;
for (let i = 0; i < n; i++) {
let waterTrapped = Math.min(maxL[i], maxR[i]) - arr[i];
ans += Math.max(waterTrapped, 0); // Avoid negative values
}
return ans;
};
def trap(arr):
n = len(arr)
maxL = [0] * n
maxL[0] = arr[0]
for i in range(1, n):
maxL[i] = max(maxL[i-1], arr[i])
maxR = [0] * n
maxR[n-1] = arr[n-1]
for i in range(n-2, -1, -1):
maxR[i] = max(arr[i], maxR[i+1])
ans = 0
for i in range(n):
waterTrapped = min(maxL[i], maxR[i]) - arr[i]
ans += max(waterTrapped, 0)
return ans
class Solution {
public int trap(int[] arr) {
int n = arr.length;
int[] maxL = new int[n];
maxL[0] = arr[0];
for (int i = 1; i < n; i++) {
maxL[i] = Math.max(maxL[i - 1], arr[i]);
}
int[] maxR = new int[n];
maxR[n - 1] = arr[n - 1];
for (int i = n - 2; i >= 0; i--) {
maxR[i] = Math.max(arr[i], maxR[i + 1]);
}
int ans = 0;
for (int i = 0; i < n; i++) {
int waterTrapped = Math.min(maxL[i], maxR[i]) - arr[i];
ans += Math.max(waterTrapped, 0);
}
return ans;
}
}
class Solution {
public:
int trap(vector& arr) {
int n = arr.size();
vector maxL(n);
maxL[0] = arr[0];
for (int i = 1; i < n; i++) {
maxL[i] = max(maxL[i - 1], arr[i]);
}
vector maxR(n);
maxR[n - 1] = arr[n - 1];
for (int i = n - 2; i >= 0; i--) {
maxR[i] = max(arr[i], maxR[i + 1]);
}
int ans = 0;
for (int i = 0; i < n; i++) {
int waterTrapped = min(maxL[i], maxR[i]) - arr[i];
ans += max(waterTrapped, 0);
}
return ans;
}
};
int trap(int* arr, int n){
int maxL[n];
maxL[0] = arr[0];
for(int i=1; i arr[i]) ? maxL[i-1] : arr[i];
}
int maxR[n];
maxR[n-1] = arr[n-1];
for(int i=n-2; i>=0; i--){
maxR[i] = (arr[i] > maxR[i+1]) ? arr[i] : maxR[i+1];
}
int ans = 0;
for(int i=0; i 0) ? waterTrapped : 0;
}
return ans;
}
public class Solution {
public int Trap(int[] arr) {
int n = arr.Length;
int[] maxL = new int[n];
maxL[0] = arr[0];
for (int i = 1; i < n; i++) {
maxL[i] = Math.Max(maxL[i - 1], arr[i]);
}
int[] maxR = new int[n];
maxR[n - 1] = arr[n - 1];
for (int i = n - 2; i >= 0; i--) {
maxR[i] = Math.Max(arr[i], maxR[i + 1]);
}
int ans = 0;
for (int i = 0; i < n; i++) {
int waterTrapped = Math.Min(maxL[i], maxR[i]) - arr[i];
ans += Math.Max(waterTrapped, 0);
}
return ans;
}
}
