Sponsored
Sponsored
This approach involves creating two auxiliary arrays to store the maximum heights on the left and right of each bar. With these arrays, you can calculate how much water each bar can trap.
The water trapped above a bar is determined by the minimum of the maximum heights on its left and right, minus the bar's height itself.
Time Complexity: O(n) because we traverse the height array three times where n is the length of the array.
Space Complexity: O(n) due to the additional arrays used to store the maximum heights.
1function trap(height) {
2 if (!height.length) return 0;
3 const n = height.length;
4 const leftMax = new Array(n);
5 const rightMax = new Array(n);
6 let water = 0;
7
8 leftMax[0] = height[0];
9 for (let i = 1; i < n; i++) {
10 leftMax[i] = Math.max(height[i], leftMax[i - 1]);
11 }
12
13 rightMax[n - 1] = height[n - 1];
14 for (let i = n - 2; i >= 0; i--) {
15 rightMax[i] = Math.max(height[i], rightMax[i + 1]);
16 }
17
18 for (let i = 0; i < n; i++) {
19 water += Math.min(leftMax[i], rightMax[i]) - height[i];
20 }
21
22 return water;
23}
24
25const height = [0,1,0,2,1,0,1,3,2,1,2,1];
26console.log(`Water trapped: ${trap(height)}`);
27This JavaScript code uses the two auxiliary arrays to track how much space is available for water above each column, similar to other descriptions. After filling out the arrays for both directions, it calculates the total trapped rainwater.
The two-pointer technique optimizes space by keeping track of the left and right bars with two pointers. It uses a single loop and calculates water based on the shorter of the two heights at the current pointers.
Time Complexity: O(n), where n is the length of the input array since we process each bar only once.
Space Complexity: O(1) because we use only constant extra space.
1 public int Trap(int[] height) {
int left = 0, right = height.Length - 1;
int leftMax = 0, rightMax = 0, water = 0;
while (left < right) {
if (height[left] < height[right]) {
if (height[left] >= leftMax) {
leftMax = height[left];
} else {
water += leftMax - height[left];
}
left++;
} else {
if (height[right] >= rightMax) {
rightMax = height[right];
} else {
water += rightMax - height[right];
}
right--;
}
}
return water;
}
public static void Main(string[] args) {
int[] height = {0,1,0,2,1,0,1,3,2,1,2,1};
Solution solution = new Solution();
Console.WriteLine("Water trapped: " + solution.Trap(height));
}
}
In C#, this algorithm applies the two-pointer approach by comparing and processing the boundaries inward, ensuring the highest landmarks are utilized for efficient water trapping computations without additional data structure overhead.