Trapping Rain Water

Task: Given an array of size N non-negative integers represents the blocks heights and every block width is 1 unit. Find how much rain water trapped in between blocks after raining.

Example:

Input:

1

6

3 0 0 2 0 4

Output:

10 // 3 + 3 + 1+ 3.

---

Here is the Code:

Program in C++:

1. #include <iostream>
2. using namespace std;
3. int trappingRainWater(int n,int *a)
4. {
5.     int i=0,j=n-1,k,trw=0;
6.     int left_max=a[i],right_max=a[j];
7.     while(i!=j)
8.     {
9.         if(left_max>right_max)
10.         {
11.             k=j-1;
12.             if(a[k]<right_max)
13.             {
14.                 trw+=right_max-a[k];
15.             }
16.             else
17.             {
18.                 right_max=a[k];
19.             }
20.             j--;
21.         }
22.         else
23.         {
24.             k=i+1;
25.             if(a[k]<left_max)
26.             {
27.                 trw+=left_max-a[k];
28.             }
29.             else
30.             {
31.                 left_max=a[k];
32.             }
33.             i++;
34.         }
35.     }
36.     return trw;
37. }
38. int main() {
39. int t;
40. cin>>t;
41. while(t--)
42. {
43.     int n;
44.     cin>>n;
45.     int a[n];
46.     for(int i=0;i<n;i++)
47.     {
48.         cin>>a[i];
49.     }
50.     cout<<trappingRainWater(n,a)<<endl;
51. }
52. return 0;
53. }

---

Here is the Video: