Trapping Rain Water
Sat Apr 27 2024 Left Max Array:
Build an array where each index i contains the maximum height from the start of the array to that index. This array helps determine the maximum height of water that can be trapped on the left side of each tower.
Right Max Array:
Similarly, construct an array from the right where each index i contains the maximum height from the end of the array to that index. This indicates the potential maximum height of water that can be trapped on the right side of each tower.
Water Trapping Calculation:
With both arrays constructed, the amount of water trapped above each tower can be calculated by determining the minimum of the left and right maximum heights at that index (since water can only be as high as the shorter "wall" on either side) and then subtracting the height of the tower itself.
1function totalTrapped(arr) {
2 const n = arr.length;
3 let leftMax = new Array(n);
4 let rightMax = new Array(n);
5 let waterTrapped = 0;
6
7 leftMax[0] = arr[0];
8 for (let i = 1; i < n; i++) {
9 leftMax[i] = Math.max(leftMax[i - 1], arr[i]);
10 }
11
12 rightMax[n - 1] = arr[n - 1];
13 for (let i = n - 2; i >= 0; i--) {
14 rightMax[i] = Math.max(rightMax[i + 1], arr[i]);
15 }
16
17 for (let i = 0; i < n; i++) {
18 waterTrapped += Math.min(leftMax[i], rightMax[i]) - arr[i];
19 }
20
21 return waterTrapped;
22}
23
24console.log(totalTrapped([7, 4, 0, 9]));
25console.log(totalTrapped([3, 0, 0, 2, 0, 4]));
26