Trapping Rain Water

 Given an array arr[] of N non-negative integers representing the height of blocks. If width of each block is 1, compute how much water can be trapped between the blocks during the rainy season. 

 

Example 1:

Input:
N = 6
arr[] = {3,0,0,2,0,4}
Output:
10
Explanation: 

          ||
||        ||
||    ||  ||  
||    ||  || 
{3 0 0 2 0 4}    

trapped rain water =3+3+1+3=10     
                 

Example 2:

Input:
N = 4
arr[] = {7,4,0,9}
Output:
10
Explanation:
Water trapped by above 
block of height 4 is 3 units and above 
block of height 0 is 7 units. So, the 
total unit of water trapped is 10 units.

Example 3:

Input:
N = 3
arr[] = {6,9,9}
Output:
0
Explanation:
No water will be trapped.

method:

We need to store water.

But water can only be stored if the right wall and left wall are taller than the centre wall.

We can do this by computing 2 arrays, one for all the right walls, and another for all the left walls.

As water can or cannot be stored at a particular index, we will have to compute the right and left arrays for maximum wall heights, that is ,
Compute the right array by taking maximum wall heights from right side, and left array by taking maximum wall heights from left side.

 these array values will show , how much water can be saved due to height of wall on one side.

1. Build the right and left max arrays.
2. Traversing from start, take the minimum of both these maximum arrays, and subtract  the value of current index in original array, and store this value

c++ implementation:

 int trappingWater(int a[], int n){
       int l[n]; l[0]=a[0];
   for(int i=1;i<n;i++)
   {
       l[i]=max(l[i-1],a[i-1]);
   }
   int r[n]; r[n-1]=a[n-1];
   for(int i=n-2;i>=0;i--)
   {
       r[i]=max(r[i+1],a[i+1]);
   }
   
   int t=0;
   for(int i=1;i<n-1;i++)
   {
       if(min(l[i],r[i])-a[i]>0)
       t=t+(min(l[i],r[i])-a[i]);
   }
   return t;
    }

Time Complexity: O(n) 

space Complexity: O(1)