Trapping Rain Water

PROBLEM :

Given n non-negative integers in array representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

For example:

Input: arr[]   = {2, 0, 2}
Output: 2
Structure is like below
|  |
|_|
We can trap 2 units of water in the middle gap.

Input: arr[]   = {3, 0, 0, 2, 0, 4}
Output: 10
Structure is like below
        |
|       |
|    |  |
|__|_|
We can trap "3*2 units" of water between 3 an 2,
"1 unit" on top of bar 2 and "3 units" between 2
and 4.  See below diagram also.

Below is another example.




Input:
The first line of input contains an integer T denoting the number of test cases. The description of T test cases follows.
Each test case contains an integer N followed by N numbers to be stored in array.

Output:
Print trap units of water in the middle gap.

Constraints:
1<=T<=100
3<=N<=100
0<=Arr[i]<10

Example:
Input:
2
4
7 4 0 9
3
6 9 9

Output:
10
 0

--------------------------------------------------------------------------------
SIMPLE c++ IMPLEMENTATION : O(n) Time & Space Compx
--------------------------------------------------------------------------------

#include<iostream>
using namespace std;
int Trapping_Rain_Water(int [],int ) ;
int max(int ,int ) ;
int min(int ,int ) ;

int main()
 {
 int t,arr[100],no,i ;
 cin>>t ;
 while(t--)
 {
     cin>>no ;
     for(i=0;i<no;i++)
         cin>>arr[i] ;
     
     no=Trapping_Rain_Water(arr,no) ;
     cout<<no<<endl ;
 }
 return 0;
}

int Trapping_Rain_Water(int arr[],int no)
{
    int left[no] ;
    int right[no] ;
 
    int i,water ;
 
    left[0]=arr[0] ;
    for(i=1;i<no;i++)
        left[i]=max(left[i-1],arr[i]) ;
     
    right[no-1]=arr[no-1] ;
    for(i=no-2;i>=0;i--)
        right[i]=max(right[i+1],arr[i]) ;
     
    water=0 ;
 
    for(i=0;i<no;i++)
        water=water+min(left[i],right[i])-arr[i] ;
     
    return water ;
}

int max(int a,int b)
{
    return a>b?a:b ;
}

int min(int a,int b)
{
    return a<b?a:b ;
}

--------------------------------------------------------------------------------
SIMPLE c++ IMPLEMENTATION : Better solution O(n) time & O(1) space
--------------------------------------------------------------------------------

#include<iostream>
using namespace std;

int TrappingRainWater(int arr[],int no)
{
int water=0 ;
int lmax=0,rmax=0 ;
int i,j ;
i=0,j=no-1 ;

while(i<=j)
{
if(arr[i]<arr[j])
{
if(arr[i]>lmax)
lmax=arr[i] ;
else
water+=lmax-arr[i] ;
i++ ;
}
else
{
if(arr[j]>rmax)
rmax=arr[j] ;
else
water+=rmax-arr[j] ;
j-- ;
}
}
return water ;
}

int main()
{
int t ;
cin>>t ;
while(t--)
{
   int no ;
   cin>>no ;
   int arr[no] ;
   for(int i=0;i<no;i++)
       cin>>arr[i] ;
   cout<<TrappingRainWater(arr,no)<<endl ;
}
return 0;
}

---------------------------------------------------------------------------------