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.
1#include <stdio.h>
2#include <stdlib.h>
3
4int trap(int* height, int heightSize) {
5 if (heightSize == 0) return 0;
6 int *leftMax = (int*)malloc(heightSize * sizeof(int));
7 int *rightMax = (int*)malloc(heightSize * sizeof(int));
8 int water = 0;
9
10 leftMax[0] = height[0];
11 for (int i = 1; i < heightSize; i++) {
12 leftMax[i] = height[i] > leftMax[i - 1] ? height[i] : leftMax[i - 1];
13 }
14
15 rightMax[heightSize - 1] = height[heightSize - 1];
16 for (int i = heightSize - 2; i >= 0; i--) {
17 rightMax[i] = height[i] > rightMax[i + 1] ? height[i] : rightMax[i + 1];
18 }
19
20 for (int i = 0; i < heightSize; i++) {
21 water += (leftMax[i] < rightMax[i] ? leftMax[i] : rightMax[i]) - height[i];
22 }
23
24 free(leftMax);
25 free(rightMax);
26 return water;
27}
28
29int main() {
30 int height[] = {0,1,0,2,1,0,1,3,2,1,2,1};
31 int heightSize = sizeof(height) / sizeof(height[0]);
32 printf("Water trapped: %d", trap(height, heightSize));
33 return 0;
34}
35This implementation uses two arrays: leftMax and rightMax to keep track of the maximum height encountered from the left and right of each bar respectively. It then calculates the trapped water by iterating through each bar and adding the minimum of these maximum heights minus the bar's height.
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#include <iostream>
#include <vector>
int trap(std::vector<int>& height) {
int left = 0, right = height.size() - 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;
}
int main() {
std::vector<int> height = {0,1,0,2,1,0,1,3,2,1,2,1};
std::cout << "Water trapped: " << trap(height) << std::endl;
return 0;
}
The C++ solution implements a two-pointer approach that avoids using extra arrays. The two pointers track positions starting from each end towards the middle, using a logical comparison between the current elements to update the max height and calculate trapped water.