Trapping Rainwater- Important Question For Interviews

The question which can be asked for this interview question is as follows:
Given "n" non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after running.

Let's take an example:

In the above image, the height of these blocks is given in the form of array like, height = [4,2,0,6,3,2,5]

• The height means from the ground till the top.

• To calculate the trapped rainwater, the below formula we consider.
  trapped rainwater = (w - x) * width of the bar
  Where,
  x = height of the block
  w = water level

• To construct the graph for trapping rainwater we consider some test cases. Below are some test cases to consider.

Case 1: Single Bar

In this case the water level will be 0 as water cannot get trapped.

Case 2: Two Bars

In this case the water level will be 0 as water cannot get trapped.

Case 3: Ascending Bars

In this case the water level will be 0 as water cannot get trapped.

Case 4: Descending Bars

In this case the water level will be 0 as water cannot get trapped.

Hence, considering all the test cases we come to a conclusion that:

• Minimum number of bars > 2 to trap the water.

• A bar should have unequal numbers of height of bars to trap the water.

Let's see one more example!

In such cases we have to count the height of the block which is minimum.
Hence the formula will be like:
Trapped Water = (Water Level - Height)
Where,
In Water level we count maxleft boundary and maxright boundary.

Let's see the code for trapping rainwater!

public class trappingrainwater { public static int trappedWater(int height[]) { //calculate left max boundary- array int n = height.length; int leftmax[] = new int [n]; leftmax[0] = height[0]; for(int i=1;i<n;i++) { leftmax[i] = Math.max(height[i], leftmax[i-1]); } //calculate right max boundary- array int rightmax[] = new int[n]; rightmax[n-1] = height[n-1]; for(int i=n-2;i>=0;i--) { rightmax[i] = Math.max(height[i], rightmax[i+1]); } int trappedWater = 0; //loop for(int i=0;i<n;i++) { //waterlevel = min(leftmax boundary, rightmax boundary) int waterlevel = Math.min(leftmax[i], rightmax[i]); //trapped water = waterlevel - height[i] trappedWater += waterlevel - height[i]; } return trappedWater; } public static void main(String[] args) { int height[] = {4,2,0,6,3,2,5}; System.out.println(trappedWater(height)); } }