Rain Water Trap

Problem Statement : 
Given n non-negative integers representing building heights where the width

of each bar is 1, compute how much water it is able to trap after raining.

Below is the figure depicting the buildings and the gap between the building would trap the water.

Buildings with gaps to trap rain water.

Solution : 

   In this problem, we would calculate left max and right Max for a given bar and subtract the height of the bar from the minimum of L_max and R_max and add the result of each bar to obtain the final answer.

min(LH[i] - RH[i]) - H[i])

where LH[i] means Left Height Max ,

           RH[i] means Right Height Max and 

           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 !!