# Trapping Rain Water LeetCode Solution

Difficulty Level Hard
Array Stack Two Pointer

In the Trapping Rain Water LeetCode problem, we have given N non-negative integers representing an elevation map and the width of each bar is 1. We have to find the amount of water that can be trapped in the above structure.

## Example

Let’s understand that by an example

For the above elevation map

Input

[2,1,0,2,2,0,1,4]

Output

6

Let’s look into some more test cases:

Input

[0,1,0,2,1,0,1,3,2,1,2,1]

Output

6

## Approach-1 for finding Trapping Rain Water

### Brute Force

• Traverse every element in the array
• Find the maximum height from the left=L
• Find the maximum height from the right=R
• The maximum amount of water that can be stored=min(L, R)-height of element

Let’s look into the code for the same in Java and C++.

### Java Program for Trapping Rain Water

```class Solution
{
public int trap(int[] height)
{
if(height==null)
return 0;
int ans=0;
for(int i=1;i<height.length-1;i++)
{
int l=Integer.MIN_VALUE;
int r=Integer.MIN_VALUE;
for(int j=0;j<i+1;j++)
l=Math.max(l,height[j]);
for(int j=i;j<height.length;j++)
r=Math.max(r,height[j]);
ans=ans+Math.min(l,r)-height[i];
}
return ans;
}
}```

### C++ Program for Trapping Rain Water

```class Solution
{
public:
int max(int a,int b)
{
if(a>b)
return a;
else
return b;
}
public:
int min(int a,int b)
{
if(b>a)
return a;
else
return b;
}
public:
int trap(vector<int>& height)
{
if(height.size()==0)
return 0;
int ans=0;
int i,j;
for(i=1;i<height.size()-1;i++)
{
int l=-1;
int r=-1;
for(j=0;j<i+1;j++)
l=max(l,height[j]);
for(j=i;j<height.size();j++)
r=max(r,height[j]);
ans=ans+min(l,r)-height[i];
}
return ans;
}
};```
`[2,1,0,2,2,0,1,4]`
`6`

### Complexity Analysis

The time complexity of the above can be computed as O(n^2)

Jump Game

## Approach-2 for finding Trapping Rain Water

### Dynamic Programming

Rather than iterating over the whole parts, again and again, the height of the highest block up to the point can be stored in respective arrays.

Let’s look into the code

### Java Program

```class Solution
{
public int trap(int[] height)
{
if(height.length==0)
return 0;
int ans=0;
//left[i] contains the maximum height of the pillar encountered before the ith pillar
int left[]=new int[height.length];
left[0]=height[0];
//righ[i] contains the maximum height of the pillar encountered after the ith pillar
int righ[]=new int[height.length];
righ[righ.length-1]=height[height.length-1];
for(int i=1;i<height.length;i++)
{
left[i]=Math.max(height[i],left[i-1]);
}
for(int i=height.length-2;i>-1;i--)
{
righ[i]=Math.max(height[i],righ[i+1]);
}
for(int i=1;i<height.length-1;i++)
{
ans=ans+Math.min(left[i],righ[i])-height[i];
}
return ans;
}
}```

### C++ Program

```class Solution
{
public:
int max(int a,int b)
{
if(a>b)
return a;
else
return b;
}
public:
int min(int a,int b)
{
if(b>a)
return a;
else
return b;
}
public:
int trap(vector<int>& height)
{
if(height.size()==0)
return 0;
int ans=0;
int left[height.size()];
left[0]=height[0];
int righ[height.size()];
righ[height.size()-1]=height[height.size()-1];
for(int i=1;i<height.size();i++)
{
left[i]=max(height[i],left[i-1]);
}
for(int i=height.size()-2;i>-1;i--)
{
righ[i]=max(height[i],righ[i+1]);
}
for(int i=1;i<height.size()-1;i++)
{
ans=ans+min(left[i],righ[i])-height[i];
}
return ans;
}
};```
`[0,1,0,2,1,0,1,3,2,1,2,1]`
`6`

## Approach-3 for finding Trapping Rain Water

### Two Pointer Approach

Let’s look into observations from the previous approach

• As long as right_max is greater than left_max we depend on the left_max to find the amount of water trapped
• As long as left_max is greater than right_max we depend on the right_max to find the amount of water trapped.

Thus, instead of maintaining the left and right array, we maintain two pointers.

Let us understand it better with the help of a code.

### Java Program

```class Solution
{
public int trap(int[] height)
{
int left=0;
int righ=height.length-1;
int lmax=Integer.MIN_VALUE;
int rmax=Integer.MIN_VALUE;
int ans=0;
while(righ>left)
{
//We rely on the minimum of the both
if(height[left]<height[righ])
{
//Update left max if the current height is greater
if(height[left]>=lmax)
lmax=height[left];
else
ans=ans+lmax-height[left];
left=left+1;
}
else
{
//If current height is greater than right max update
if(height[righ]>=rmax)
rmax=height[righ];
else
ans=ans+rmax-height[righ];
righ=righ-1;
}
}
return ans;
}
}

```

### C++ Program

```class Solution
{
public:
int max(int a,int b)
{
if(a>b)
return a;
else
return b;
}
public:
int min(int a,int b)
{
if(b>a)
return a;
else
return b;
}
public:
int trap(vector<int>& height)
{
int left=0;
int righ=height.size()-1;
int lmax=-1;
int rmax=-1;
int ans=0;
while(righ>left)
{
//We rely on the minimum of the both
if(height[left]<height[righ])
{ //Update left max if the current height is greater
if(height[left]>=lmax)
lmax=height[left];
else ans=ans+lmax-height[left]; left=left+1;
}
else
{ //If current height is greater than right max update
if(height[righ]>=rmax)
rmax=height[righ];
else
ans=ans+rmax-height[righ];
righ=righ-1;
}
}
return ans;
}
};```
`[ 8, 0, 8 ]`
`8`

### Complexity Analysis

• The time complexity of the above solution=O(n)
• Space complexity=O(1) because we don’t use any auxiliary space here.