Trapping Rain Water

This is my first blog and from now I will regularly post on some easiest solution of famous problems.

Trapping rainwater is a very famous problem asked by many companies like amazon, facebook, oracle etc. I’m here to tell you the easiest method of doing this problem. My approach of solving this problem is not the best but it's the easiest and once you understand the problem you can try to find the best solution by your own.
Problem statement: you are given an array of non-negative numbers which represents the size of the block/buildings. In this case the given array is {1,0,2,1,0,1,3,2,1,2,1}

In the above image the black color represents the block/building, while grey color represents the space where water can get stored so our aim is to find out the amount of water which can get trapped in it i.e. calculating the total number of grey blocks. In this case it is total grey blocks are 6.

Solution: Water can get trapped only if the block have a higher block on right side as well as left side. Suppose we take first element i.e. 1 it has a higher block on right side but it doesn’t have a higher block on left side, so no water got trapped. Now look at the second element it have higher blocks on both the side so it can contain water.so our first task is to find out the highest block available on right hand side

Similarly we will find out the highest block available on left hand side

Now our left and right array are going to look like this:

Now we are going to choose the minimum from both the left and right array. Why we are choosing a smaller element? Take an example we have three blocks {1,0,3} now the block at second position can contain only 1 unit of water because 1 block can’t stop 3 units of water.
Now we are gone subtract the height of the block from the minimum of left and right array. It might give you a negative number but you have to consider it as 0 because the amount of water can't be negative.

Now you can just print the value of ans1.

The complete code is going to look like this:

Thanks for reading.