The water being trapped inside any bar is determined by the highest left and right bar.
The volume of water trapped = min(left, right) - height
Brute Force Three Pass
We can assign the highest left bars, assign the highest right bars, then compute the rain water.
public int trap(int[] height) {
if (height == null || height.length == 0) {
return 0;
}
int n = height.length;
int[] leftBars = new int[n];
int[] rightBars = new int[n];
// assign left bars
int left = 0;
for (int i = 0; i < n; i++) {
left = Math.max(left, height[i]);
leftBars[i] = left;
}
// assign right bars
int right = 0;
for (int i = n - 1; i >= 0; i--) {
right = Math.max(right, height[i]);
rightBars[i] = right;
}
// compute the rain volume
int rain = 0;
for (int i = 1; i < n - 1; i++) {
int current = Math.min(leftBars[i], rightBars[i]) - height[i];
rain += current > 0 ? current : 0;
}
return rain;
}
Time O(3n) = O(n) Space O(2n) = O(n)
L/R Pointers
Linear time is probably as good as we can get. Unless we can do a binary search on the array. But the space can be further optimized.
We maintain two values leftBar and rightBar. Then use left/right pointers to update on the way.
leftBar
rightBar
left --> <--- right
move left if leftBar is lower than rightBar
move right if rightBar is lower than the leftBar
(so we make sure water can be trapped by the lower end)
public int trap(int[] height) {
if (height == null || height.length < 2) {
return 0;
}
int rain = 0;
int left = 0, right = height.length - 1;
int leftBar = height[left], rightBar = height[right];
while (left < right) {
if (leftBar < rightBar) {
rain += leftBar - height[left];
left++;
leftBar = Math.max(leftBar, height[left]);
} else {
rain += rightBar - height[right];
right--;
rightBar = Math.max(rightBar, height[right]);
}
}
return rain;
}
