Problem:
Given a non-negative integer array. Each element represents an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.For example, given array [1,4,0,1,0,3,1,2,0,1], the elevation map represented by it can trap 10 units of rain water.
Solution:
The brutal force solution is find the water above each of the bars. For a given bar, we can find the max bar height on the left lBound and the max bar height on the right rBound, then the amount of water above the current bar is the min(lBound, rBound) - currentHeight. For each bar, we can search the other n -1 bars to find the lBound and rBound, the total time complexity is O(N^2) and space complexity is O(1).
An improvement on the brutal force is to trade space for time. At index i, if we know the max bar height on the left is lMax[i], at index i+1, we don't have to search again, we just have to use formula lmax[i] = Math.max(lMax[i-1], height[i])
where i from 1 to height.length - 1.
We can say the same to the rMax,
rMax[i] = Math.max(rMax[i], height[i+1])
where i from arr.length - 2 to 0
That way, we get O(N) time complexity, but space complexity is O(N) as well.
With similar approach used in Largest Rectangle in Histogram, we can use a stack to follow the height values' changing trend, once we find the turning point, we take actions accordingly. In this case, we use the stack to store the decreasing sequence of the height. Once the current bar's height increase, we know we just passed a valley. The 2 bars at the stack top and the current bar formed a valley, the water holding capacity of this valley is (Math.min(height[stack(top-1)], height[current])) - height[stack(top)]) * (current - stack(top)).
import java.util.*;
public class Solution {
public static int trap(int[] arr) {
int water = 0;
Stack<Integer> lMax = new Stack<>();
lMax.push(0); //1 5 6
for(int i = 1; i < arr.length; i++) { //5
while(!lMax.isEmpty() && arr[lMax.peek()] <= arr[i]) {
int index = lMax.pop();
if(lMax.isEmpty())
break;
water += (Math.min(arr[lMax.peek()], arr[i]) - arr[index]) * (i - lMax.peek() - 1);
}
lMax.push(i);
}
return water;
}
public static void main(String...args) {
int[] arr = new int[]{1,4,0,1,0,3,1,2,0,1};
System.out.println(trap(arr));
}
}
public class Solution {
public static int trap(int[] arr) {
int water = 0;
Stack<Integer> lMax = new Stack<>();
lMax.push(0); //1 5 6
for(int i = 1; i < arr.length; i++) { //5
while(!lMax.isEmpty() && arr[lMax.peek()] <= arr[i]) {
int index = lMax.pop();
if(lMax.isEmpty())
break;
water += (Math.min(arr[lMax.peek()], arr[i]) - arr[index]) * (i - lMax.peek() - 1);
}
lMax.push(i);
}
return water;
}
public static void main(String...args) {
int[] arr = new int[]{1,4,0,1,0,3,1,2,0,1};
System.out.println(trap(arr));
}
}
The time complexity is O(N) and the space complexity is O(N) due to the stack.
There is a O(N) time complexity and O(1) space complexity solution.
The intuition is: we can use two pointers to mark a water container with left and right edges. The left pointer start at index 0 and the right pointer start at the last index. The two bars pointing by the 2 pointers formed a water container with capacity bottleneck at the shorter one. The 2 pointers move inward searching for the longer bars as the container's edges. If a bar is shorter than the bottleneck, the bar can hold water. If a bar is longer than the shorter container edge, the pointer moves to it thus form a taller but narrower container.
The intuition is: we can use two pointers to mark a water container with left and right edges. The left pointer start at index 0 and the right pointer start at the last index. The two bars pointing by the 2 pointers formed a water container with capacity bottleneck at the shorter one. The 2 pointers move inward searching for the longer bars as the container's edges. If a bar is shorter than the bottleneck, the bar can hold water. If a bar is longer than the shorter container edge, the pointer moves to it thus form a taller but narrower container.
public class Solution {
public static int trap(int[] arr) {
int water = 0;
int lBound = arr[0];
int rBound = arr[arr.length - 1];
int i = 0;
int j = arr.length - 1;
while(i < j) {
if(lBound < rBound) {
while(arr[i] <= lBound) {
water += lBound - arr[i];
i++;
}
lBound = arr[i];
} else {
while(arr[j] <= rBound) {
water += rBound - arr[j];
j--;
}
rBound = arr[j];
}
}
return water;
}
public static void main(String...args) {
int[] arr = new int[]{1,4,0,1,0,3,1,2,0,1};
System.out.println(trap(arr));
}
}
public static int trap(int[] arr) {
int water = 0;
int lBound = arr[0];
int rBound = arr[arr.length - 1];
int i = 0;
int j = arr.length - 1;
while(i < j) {
if(lBound < rBound) {
while(arr[i] <= lBound) {
water += lBound - arr[i];
i++;
}
lBound = arr[i];
} else {
while(arr[j] <= rBound) {
water += rBound - arr[j];
j--;
}
rBound = arr[j];
}
}
return water;
}
public static void main(String...args) {
int[] arr = new int[]{1,4,0,1,0,3,1,2,0,1};
System.out.println(trap(arr));
}
}
