H[i] means Height of building 'i'.
This is a simple gist of the problem, we will discuss the various approach to solve this problem.
Approach 1 :
The Brute Force, this is the father of all solutions and every developer is the master of it, this is always the first answer but never accepted by the interviewer, anyways we still discuss this to optimize our solution further.
In this approach, we will traverse the elements and every element will have two pointers `left` and `right`, left pointer will move towards left until a bigger number is found for i-th element and the right pointer will move towards right until the bigger element is found for the i-th element.
so water stored at i-th element = Min(L_max , R_max) - height[i].
I hope you will be able to code for this, if not you can find the code
here.
Time Complexity: O(n^2)
Space Complexity: O(1)
Approach 2 :
The Dynamic Programming(DP) approach, in this approach we will use two most important properties of DP, a. Overlapping subproblem and Optimal Substructure.
On every bar, the water collected is calculated by itself as well as a portion of it is also calculated by other bars, this is a depiction of
Overlapping subproblem.
Optimal Substructure, we can represent the calculation of water on a bar that is subproblem and it is contributed by other bars as well this can be represented by the below equation.
min(LH[i] - RH[i]) - H[i])
So here we will take two arrays left[] and right[] which will store the left_max and right_max for every bar respectively at the corresponding index of the bar. Thereafter we calculate the water level stored on each bar by
Min(Lmax - Rmax) - bar_height. Summation of the previous value would give us the trapped water.
Code below:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| //Dynamic Programming Apporach to Trap rain water problem solution
static int trapWaterUsingDP(int[] bars) {
if(bars == null || bars.length < 3)
return 0;
int len = bars.length, trappedWater = 0;
int[] left = new int[len];
int[] right = new int[len];
//NB. for left most bar lmax would be 0, so counter is stated with 1,
for(int i=1;i<len;i++)
left[i] = Math.max(left[i-1], bars[i-1]);
// similarly for right most bar rmax would be 0 at len-1.
for(int i= len -2 ;i >= 0;i--)
right[i] = Math.max(right[i+1], bars[i+1]);
for(int i=0;i<len;i++)
trappedWater += Math.max(0, Math.min(left[i], right[i]) - bars[i]);
return trappedWater;
}
|
Time Complexity : O(n)
Space Complexity : O(n) , since we have used n + n which is 2n, removings constants gives us O(n) complexity
Approach 3:
The Stack-based approach, we will now solve the above problem with the stack-based approach, in the last approach, we improved on Time Complexity but deteriorated Space complexity compared to approach 1.
This approach will give us both improved Time and Space complexity.
Algorithm below :
1. Iterate over each tower
a. while stack is not empy and stack.peek() > current
i. top = stack.pop()
ii. dist = current - stack.peek() -1
iii height = min(current, stack.peek()) - height[top]
iv. water += dist * height
b. push
c. next tower
Code below.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| //Stack based Approach to Trap rain water problem solution
static int trapWaterUsingStack(int[] bars) {
if(bars == null || bars.length < 3)
return 0;
Stack<Integer> stack = new Stack<>();
stack.push(0);
int len = bars.length, waterTrapped = 0;
for(int i=1; i < len ; i++)
{
while(!stack.isEmpty() && bars[stack.peek()] < bars[i]) {
int top = stack.pop();
if(!stack.isEmpty()) {
int dist = stack.isEmpty() ? 0 : i - stack.peek() - 1 ;
int effectiveHeight = Math.min(bars[i], bars[stack.peek()]) - bars[top];
waterTrapped += dist * effectiveHeight;
}
}
stack.push(i);
}
return waterTrapped;
}
|
Time Complexity: O(n)
Space Complexity: O(n)
Approach 4:
Two Pointer Approach :
In this approach, we will use two-pointers and switch between left and right pointer for the movement.
Extreme bars will not store any water.
We will continue to move from left until left is smaller than right, as soon as right becomes smaller than left we will start move from right.
For complete code use this link (
Code)
Please post your suggestions and comments.
Happy Coding !!
