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++:
- #include <iostream>
- using namespace std;
- int trappingRainWater(int n,int *a)
- {
- int i=0,j=n-1,k,trw=0;
- int left_max=a[i],right_max=a[j];
- while(i!=j)
- {
- if(left_max>right_max)
- {
- k=j-1;
- if(a[k]<right_max)
- {
- trw+=right_max-a[k];
- }
- else
- {
- right_max=a[k];
- }
- j--;
- }
- else
- {
- k=i+1;
- if(a[k]<left_max)
- {
- trw+=left_max-a[k];
- }
- else
- {
- left_max=a[k];
- }
- i++;
- }
- }
- return trw;
- }
- int main() {
- int t;
- cin>>t;
- while(t--)
- {
- int n;
- cin>>n;
- int a[n];
- for(int i=0;i<n;i++)
- {
- cin>>a[i];
- }
- cout<<trappingRainWater(n,a)<<endl;
- }
- return 0;
- }
Here is the Video: