Trapping Rain Water Problem Python JAVA C++ Solution

One of the most frequently asked software interview questions is the Trapping Rain Water Problem. In this post, I’ll go over the solution to the Trapping Rain Water problem, as well as the algorithm you can use to solve it.

Question:

Calculate how much water can be trapped after raining using n non-negative integers representing an elevation map, with each bar having a width of one.

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

The solution to Trapping Rain Water Problem

On each row, the goal is to find the tallest and shortest bars. When you look at each bar, the amount of water stored on top of it equals the amount of water stored below it minus the amount of water that is now stored below it. This is demonstrated in C, Java, and Python, in that order.

Understanding the Fundamentals:

An array element can store water if the bars on the left and right are higher. The amount of water held in each element can be calculated by comparing the heights of the left and right sidebars. Every element of the array will be examined to determine how much water it can hold.

Method 1: Brute Force Solution for Trapping Rain Water Problem

The best thing you can do in an interview is come up with the Brute Force Solution to any problem you’ve been given. Then go through your Thought process again to arrive at the best solution.

And this method of problem-solving in a specific process gives the interviewer confidence in you and gives them insight into 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++:
// 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). Because we’re using two nested for loops, we’re iterating through all the elements of the array n*n times, where n is the size of the given array or list.
  • Space Complexity: O(1). Because the above solution does not necessitate any additional space to solve the problem.

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

We came up with a brute force solution for the problem above; now we should analyze our existing code to see how we can optimize the above solution to reduce its execution time.

#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). Because we are iterating through the array in a linear fashion. There are also no nested loops.
  • Space Complexity: O(n). Since the above solution makes use of two arrays or lists named leftMaxHeight and rightMaxHeight, these variables can store all of the elements of the original list or array.

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

The two-pointer approach can optimize the above-optimized code. The space complexity, as in the preceding solution, is O(n), which 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). Because we are iterating through the array in a linear fashion. There are also no nested loops.
  • Space Complexity: O(1). We are not using an extra array to store any elements of the existing array or list in the above solution.

Wrap Up:

That concludes the solution to the problem of Trapped Rain Water. I’ve listed every possible solution except one that can be accomplished with Stack. I’d like to keep that question for you in order to solve the above problem with Stack.

Also, please provide us with the code for the stack-based solution you created. Please let us know if the above code contains any errors.

Then please follow us on Facebook, Twitter, and subscribe to our Newsletter to become part of a fantastic community of developers from all over the world. Let us know what questions and answers you’d like to see on this blog.

Further Read:

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

Leave a Comment