Trapping Rainwater- Important Question For Interviews
Tags: java, beginners, programming, github
Published: 2023-01-03 06:11:53

**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:

![Example for trapping rainwater](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/apxwijndzbhxsnv760xz.jpg)
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**

![Case 1- Single Bar](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/5wlropx461e6vrxzm77e.jpg)
In this case the water level will be 0 as water cannot get trapped. 

**Case 2: Two Bars**

![Case 2- Two Bars](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/my7dm7pkm84eai2dqelz.jpg)
In this case the water level will be 0 as water cannot get trapped. 

**Case 3: Ascending Bars**

![Case 5- Ascending Bar](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/iobt2reaki5h1w46r2f9.jpg)
In this case the water level will be 0 as water cannot get trapped. 

**Case 4: Descending Bars**

![Case 4- Descending Bar](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/utvj1dt5tyjxezxrwumf.jpg)
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!

![Example 2](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/njwp4e9lzkh84b1c3i1l.jpg)
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));
    }
}
```