Trapping Rain Water Problem Python JAVA C++ Solution

Trapping Rain Water Problem is one of the most asked software interview questions. In this post, I will discuss the solution to the Trapping Rain Water problem and the algorithm you can follow to solve it.

Question:

Given n non-negative integers representing an elevation map, with each bar having a width of one, calculate how much water it can trap after raining.

Example 1:

Input: height = [0,1,0,3,2,1,5,7,1,0]
Output: 4

Example 2:

Input: height = [0,3,0,3]
Output: 3

Solution to Trapping Rain Water Problem

The goal is to find the tallest and shortest bars on each row. If you look at each bar, the quantity of water that is stored on top of it equals how much water is stored below it, minus how much water is now stored below it. This is demonstrated in C, Java, and Python, respectively.

Understanding the Fundamentals:

If the bars on the left and right are higher, an array element can store water. The amount of water that will be held in each element can be calculated by comparing the left- and right-sidebar heights. Every element of the array will be analyzed to see how much water can be stored in it.

Method 1: Brute Force Solution for Trapping Rain Water Problem

The best thing in an interview can be coming up with the Brute Force Solution for any problem you have been given. And then go through your Thought process again and come up with the optimized solution.

And this way of solution in a particular process gives the interviewer confidence in you and they get insight related to your problem-solving ability.

Brute Force Algorithm:
  • Initialize totalTrappedWater=0
  • Iterate the array from left to right:
    • Initialize leftMaxHeight = 0 and rightMaxHeight = 0
    • Iterate from the current element to the beginning of array updating:
      • leftMaxHeight =max(leftMaxHeight , currentHeight[j])
    • Iterate from the current element to the end of array updating:
      • rightMaxHeight = max(rightMaxHeight , currentHeight[j])
    • Add min(leftMaxHeight , rightMaxHeight ) − currentHeight[i] to totalTrappedWater
Code:
// C++ implementation of the approach
#include<bits/stdc++.h>
using namespace std;
 
//Function to get the Maximum Water Trapped
int getMaxTrappedWater(vector<int> &towerHeights, int size)
{
     
    // To Store the Max Trapped Water
    int maxTrappedWater = 0;
     
    // Iterate Through Each Elements in Array
    for (int i = 1; i < size-1; i++) {
         
        // Find the maximum element on its left
        int left = towerHeights[i];
        for (int j=0; j<i; j++)
           left = max(left, towerHeights[j]);
         
        // Find the maximum element on its right  
        int right = towerHeights[i];
        for (int j = i+1; j < size; j++)
           right = max(right, towerHeights[j]);
        
       // Get the Update Trapped Water
       maxTrappedWater = maxTrappedWater + (min(left, right) - towerHeights[i]);  

    }
 
    return maxTrappedWater;
}
 
// Driver code to get the Maximum Water Trapped
int main()
{
    vector<int> towerHeights = {1,2,0,3,0,1,5,8,1,0,9};
    int size = towerHeights.size();
     
    cout << getMaxTrappedWater(towerHeights, size);
     
    return 0;
}

Output:

22

Runtime Analysis:

  • Time Complexity: O(n2). As we are using two nested for loop and iterating through all the elements of array n*n times where n is the size of the given array or list.
  • Space Complexity: O(1). Since above solution do not require any additional space to get to the solution of the problem.

Method 2: Optmized Solution for the Trapping the Rain Problem.

Above we came up with the brute force solution for the problem, now we should analyze our existing code to understand how can we optimize the above solution to reduce its time of execution.

#include<bits/stdc++.h>
using namespace std;

int getTrappedWater(vector<int>& towerHeight)
{
    int totalTrappedWater = 0;
    int size = towerHeight.size();

    if(size == 0) return 0;

    vector<int> leftMaxHeight(size), rightMaxHeight (size);

    leftMaxHeight [0] = towerHeight[0];

    for (int i = 1; i < size; i++) {

        leftMaxHeight[i] = max(towerHeight[i], leftMaxHeight[i - 1]);

    }

    rightMaxHeight[size - 1] = towerHeight[size - 1];

    for (int i = size - 2; i >= 0; i--) {

        rightMaxHeight[i] = max(towerHeight[i], rightMaxHeight[i + 1]);

    }
    for (int i = 1; i < size - 1; i++) {

        totalTrappedWater += min(leftMaxHeight[i], rightMaxHeight[i]) - towerHeight[i];

    }
    
    return totalTrappedWater;
}
 
int main(){

    //Drivers Code to get totalTrappedWater.

    //Initializing a Vector
    vector<int> towerHeight = {2,5,7,1,8,9,10,3,4,6};

    int totalTrappedWater = 0;

    totalTrappedWater = getTrappedWater(towerHeight);

    cout<<totalTrappedWater<<endl;

    return 0;         
}

Output:

11

Runtime Analysis:

  • Time Complexity: O(n). As we are iterating through array each time linearly only. And there are no nested loops.
  • Space Complexity: O(n). Since above solution we are using two array or list named leftMaxHeight and rightMaxHeight, as these variable can store all the elements of the list present in the original list or array.

Method 3: Best Optimized Solution for Trapping Rain Water using Two Pointer.

Two pointer approach can reduce the above-optimized code to more optimized. As in the above solution, the space complexity is O(n) that can be further reduced to a constant space-time solution of O(1) using the Two Pointer Approach.

public class Solution {

   public static int getTotalTrappedWater(int[] towerHeight) {

      if (towerHeight == null || towerHeight.length == 0) {
          return 0;
      }
      int left = 0; 
      int right = towerHeight.length - 1; // Pointers to both ends of the array.
      int maxLeft = 0; int maxRight = 0;
      
      int totalWater = 0;
      while (left < right) {
          // Water could, potentially, fill everything from left to right, 
         // if there is nothing in between.
          if (towerHeight[left] < towerHeight[right]) {
              // If the current elevation is greater than the previous maximum, 
             //  water cannot occupy that point at all.
              // However, we do know that everything from maxLeft to 
             //  the current index, has been optimally filled, as we've
              // been adding water to the brim of the last maxLeft.
              if (towerHeight[left] >= maxLeft) { 
                  // So, we say we've found a new maximum, and 
                 // look to see how much water we can fill from this point on.
                  maxLeft = towerHeight[left]; 
              // If we've yet to find a maximum, we know that 
              // we can fill the current point with water up to the previous
              // maximum, as any more will overflow it. 
              //We also subtract the current height, as that is the elevation the
              // ground will be at.
              } else { 
                  totalWater += maxLeft - towerHeight[left]; 
              }
              // Increment left, we'll now look at the next point.
              left++;
          // If the height at the left is NOT greater than height at the right, 
          // we cannot fill from left to right without over-
          // flowing; however, we do know that we could 
          // potentially fill from right to left, if there is nothing in between.
          } else {
              // Similarly to above, we see that we've found 
             // a height greater than the max, and cannot fill it whatsoever, but
              // everything before is optimally filled
              if (towerHeight[right] >= maxRight) { 
                  // We can say we've found a new maximum and move on.  
                  maxRight = towerHeight[right]; 
              // If we haven't found a greater elevation, 
             // we can fill the current elevation with maxRight - height[right]
              // water.
              } else {
                  totalWater += maxRight - towerHeight[right]; 
              }
              // Decrement left, we'll look at the next point.
              right--;
          }
      }
      // Return the sum we've been adding to.
      return totalWater;
  }

   public static void main(String args[]) {
      int[] towerHeight = {1,2,3,0,5,1,0,6,0,7};

      int totalTrappedWater = 0;

      totalTrappedWater = getTotalTrappedWater(towerHeight);

      System.out.println(totalTrappedWater);
   }
}
def getMaxTrappedWater(towerHeight):
    # The concept here is water that is going to get stored above any building would depenf upon largest height of building to it's left
    # and also the largest height of building to it's right. You take the minimum of it as only till that height the water would accumulate
    # Now just subtract of height of the building you are currently at so you get the heeight of water above it.

    # Array that stores largest element to itself in left
    LeftMaxIncludingCurrent = [0] * len(towerHeight)
    # Array that stores largest element to itself in right
    RightMaxIncludingCurrent = [0] * len(towerHeight)
    # This is just for simplicity, you actually don't need it, just take some counter over here
    Water = [0] * len(towerHeight)

    maxLeft = 0
    maxRight = 0
    # Fill up the LeftMaxIncludingCurrent Array
    for index in range(len(towerHeight)):
        maxLeft = max(maxLeft, towerHeight[index])
        LeftMaxIncludingCurrent[index] = maxLeft
    # Fill up the RightMaxIncludingCurrent Array
    for index in range(len(towerHeight)-1, -1, -1):
        maxRight = max(maxRight, towerHeight[index])
        RightMaxIncludingCurrent[index] = maxRight

    # Find the height of the water as discussed above in the concept
    for index in range(len(towerHeight)):
        Water[index] = min(LeftMaxIncludingCurrent[index],
                               RightMaxIncludingCurrent[index]) - towerHeight[index]
    # Take the sum of water that accumulated above every other building to get total water that got accumulated.
    return sum(Water)

#Driver Code to get the Answer
towerHeight = [1,2,3,0,5,1,0,6,0,7]

maxTrappedWater = getMaxTrappedWater(towerHeight)

print(maxTrappedWater)
// C++ implementation of the approach
#include<bits/stdc++.h>
using namespace std;
 
//Function to get the Maximum Water Trapped
int getMaxTrappedWater(vector<int> &towerHeights, int size)
{
     
    int left = 0; 
    int right = size - 1;
    int totalTrappedWater = 0;
    int maxleft=0, maxright=0;

    while(left<=right){

         if(towerHeights[left] <= towerHeights[right]){

            if(towerHeights[left] >= maxleft) maxleft = towerHeights[left];
            else totalTrappedWater += maxleft - towerHeights[left];
            left++;

        }
        else{

            if(towerHeights[right] >= maxright) maxright= towerHeights[right];
            else totalTrappedWater += maxright - towerHeights[right];
            right--;

        }
    }
    return totalTrappedWater;
}
 
// Driver code to get the Maximum Water Trapped
int main()
{
    vector<int> towerHeights = {1,2,3,0,5,1,0,6,0,7};
    int size = towerHeights.size();
     
    cout << getMaxTrappedWater(towerHeights, size);
     
    return 0;
}

Output:

18
Trapping Rain Water Problem Python JAVA C++ Solution

Runtime Analysis:

  • Time Complexity: O(n). As we are iterating through array each time linearly only. And there are no nested loops.
  • Space Complexity: O(1). Since above solution wwe are not using any extra array to store any elements of the existing array or list.

Wrap Up:

That is all for the solution for the Trapped Rain Water problem. I have listed all the possible solutions apart from one that can be done using Stack. I would like to keep that question to you to solve the above problem using Stack.

And let us know your code for the solution that you created using stack. Let us know if there are any issues in the above code.

Then please follow us on Facebook, Twitter and Subscribe to our Newsletter to join a great community of developers around the world. Let us know the questions and answer you want to cover in this blog.

Further Read:

  1. How to Write Enhanced For Loop in Java With Examples

Leave a Reply

Your email address will not be published. Required fields are marked *