# 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.

- Build the right and left max arrays.
- 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)