Problem
Given an array where each element represents the height of a vertical bar, calculate how much water can be trapped after raining.The amount of water trapped above any bar depends on the tallest bar on its left and the tallest bar on its right.
Example(s)
Consider the following example(s) to understand the expected input and output.Input
height = [0,1,0,2,1,0,0,1,3,2,1,2,1]Output
8Solution
A brute-force approach calculates the tallest bar on the left and the tallest bar on the right for every index separately. Since this requires scanning the array for every position, the time complexity isO(nĀ²).
A better approach is to precompute the maximum height on the left and right of every position. This allows the trapped water at each position to be calculated in constant time.
Prefix and Suffix Maximum Arrays
We maintain two arrays:leftMax and rightMax. For every index, leftMax[i] stores the tallest bar strictly to the left of index i, while rightMax[i] stores the tallest bar strictly to the right.
The maximum height to the left can be computed with a left-to-right traversal. Similarly, the maximum height to the right can be computed with a right-to-left traversal.
public int trap(int[] height) {
int n = height.length;
int[] leftMax = new int[n];
int[] rightMax = new int[n];
// Build left maximums
int max = 0;
for (int i = 0; i < n; i++) {
leftMax[i] = max;
max = Math.max(height[i], max);
}
// Build right maximums
max = 0;
for (int i = n - 1; i >= 0; i--) {
rightMax[i] = max;
max = Math.max(height[i], max);
}
int water = 0;
for (int i = 0; i < n; i++) {
water += Math.max(
0,
Math.min(leftMax[i], rightMax[i]) - height[i]
);
}
return water;
}
water = min(leftMax, rightMax) - currentHeightMath.max(0, ...) ensures that no negative amount of water is added.
Complexity
The prefix/suffix maximum approach processes the array a constant number of times, resulting in a time complexity ofO(n).
It uses two additional arrays of size
n, resulting in an extra space complexity of O(n).
Two Pointer Approach
The Two Pointer approach further optimizes the solution by eliminating the two auxiliary arrays.Two pointers are maintained, with
left starting from the beginning of the array and right starting from the end. We also maintain leftMax, the highest bar seen from the left, and rightMax, the highest bar seen from the right.
The key observation is that the water trapped at a position is determined by the smaller boundary:
Water = min(leftMax, rightMax) - currentHeightleft pointer is less than or equal to the height at the right pointer, the left side can be processed because the right side provides a boundary at least as high as the current left boundary. Otherwise, the right side is processed.
By moving the pointer with the smaller boundary, the limiting water level is already known.
public int trap(int[] height) {
int left = 0;
int right = height.length - 1;
int leftMax = 0;
int rightMax = 0;
int 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;
}
Complexity
The Two Pointer approach also processes each element at most once, resulting in a time complexity ofO(n).
However, it maintains only a few variables instead of auxiliary arrays, reducing the extra space complexity to
O(1).