Trapping Rain Water  

Difficulty Level Hard
Frequently asked in Adobe Amazon Apple Bloomberg Databricks Expedia Facebook Flipkart Goldman Sachs Google Microsoft Oracle Qualtrics ServiceNow Walmart Labs Yahoo
Array Stack Two Pointer

In Trapping Rain Water 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

Trapping Rain WaterPin

For the above elevation map

Please click Like if you loved this article?

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)

See also
Binary Tree to Binary Search Tree Conversion using STL set

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.

Please click Like if you loved this article?

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.
See also
Sort an array according to the order defined by another array

Thus, it was the trapping rainwater problem and multiple approaches to solving it!

References

Please click Like if you loved this article?