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.
Table of Contents
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)
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 add the water trapped to the answer
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 add to the answer
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 add the water trapped to the answer
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 add to the answer
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.
Thus, it was the trapping rainwater problem and multiple approaches to solving it!