Trapping Rainwater

Method 1: Brute Force

The simplest way to find the right_max and left_max for every element is a linear comparison with all other elements. Compare every element on the right side with right_max. The maximum of both is the new right_max. Similarly, left_max is found by comparing left_max to elements present on the left side of the current array element.

Algorithm

• Initialize total_volume = 0.
• Set size = size of heights.
• Iterate through the heights from 0 to size - 1.
  • Initialize left_max = 0.
  • Iterate through the heights from 0 to current element.
    • Set left_max = max(left_max, current element).
  • Initialize right_max = 0.
  • Iterate through the heights from current element to size.
    • Set right_max = max(right_max, current element).
  • Add min(left_max, right_max) - current element to total_volume.
• Return total_volume.

 

Code for Reference

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

int rainWaterVol(vector<int> heights) {
    int total_volume = 0;
    int size = heights.size();

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

          // Find left_max for current element.
          int left_max = heights[current];
          for(int left = 0; left < current; left++) {
		     left_max = max(left_max, heights[left]);
          }
  
          // Find right_max for current element.
          int right_max = heights[current];
          for(int right = current + 1; right < size; right++){
     			right_max = max(right_max, heights[right]);
          }
  
          // Adding trapped rainwater volume to the total volume.
          total_volume += min(left_max, right_max) - heights[current];
    }

    return total_volume;
}

int main() {
    int size;
    cout << "Size of the array: ";
    cin >>  size;
 
      vector<int> heights(size);
      cout << "Enter the elements:\n";
      for (int i = 0; i < size; i++) {
          cin >> heights[i];
      }

      cout << "Volume of trapped rainwater: " << rainWaterVol(heights);
}

 

Input Format

Size of the array: 12
Enter the elements:
0    1    0    2    1    0    1    3    2    1    2    1

 

Output Format

Volume of trapped rainwater: 6

Complexity Analysis

Time Complexity: The code uses two nested linear loops to find the right_max and left_max. So, the time complexity for this method is O(N²)

Space Complexity: Constant space is used. So, the space required is independent of the size of the input given. Space complexity is O(1).

See Data Structures

Method 2: Dynamic Programming

For every element, we need to find right_max and left_max. Avoid iterating the right and left sides for every element. Instead, we can create two lookups for right_max and left_max: right_max_array and left_max_array.

So, the algorithm for this new method can be modified as given below. 

(See Dynamic Programming)

Algorithm

• Initialize total_volume = 0.
• Set size = size of heights.
• Declare vectors right_max_array and left_max_array of lengths equal to size.
• Set right_max_array[0] = heights[0].
• Set left_max_array[size - 1] = heights[size - 1].
• Iterate through the heights from 1 to size for left_max_array.
  • Set left_max_array[i] = max(left_max_array[i - 1], heights[i]).
• Iterate through the heights from size - 2 to 0 for right_max_array.
  • Set right_max_array[i] = max(rightt_max_array[i + 1], heights[i]).
• Iterate through the heights from 1 to size -1 to calculate the total_volume.
  • Add max(right_max_array[i], left_max_array[i]) - height[i] to total_volume.

Code for Reference

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

 
int rainWaterVol(vector<int> heights) {
    int total_volume = 0, size = heights.size();

    // Edge case: if the input is empty
    if(size == 0) {
          return 0;
     }

    // Declaring lookup tables.
    vector<int> right_max_array(size), left_max_array(size);
    left_max_array[0] = heights[0];
    right_max_array[0] = heights[size-1];

    // Filling right_max_array lookup table.
    for(int current = 1; current < size; current++) {
          left_max_array[current] = max(left_max_array[current-1], heights[current]);
    }

    // Filling left_max_array lookup table.
    for(int current = size - 2; current >= 0; current--) {
   right_max_array[current] = max(right_max_array[current+1], heights[current]);
    }

    // Calculating total_volume using lookups.
    for(int current = 1; current < size-1; current++) {
          total_volume += min(left_max_array[current], right_max_array[current])- heights[current];
    }
    return total_volume;
}

 
int main() {
    int size;
    cout << "Size of the array: ";
    cin >>  size;
 
      vector<int> heights(size);
      cout << "Enter the elements:\n";
      for (int i = 0; i < size; i++) {
          cin >> heights[i];
      }

      cout << "Volume of trapped rainwater: " << rainWaterVol(heights);
}

 

Input Format

Size of the array: 12
Enter the elements:
0    1    0    2    1    0    1    3    2    1    2    1

 

Output Format

Volume of trapped rainwater: 6

Complexity Analysis

Time Complexity: Creating lookups is a linear-time operation. Also, calculating total_volume using the lookups requires a one-time iteration through the given input. So, the time complexity is O(N).

Space Complexity: Extra space is required to create lookups. The size of lookups depends linearly on the size of the input. So, the space complexity is O(N).

Method 3: Monotonic Stack

So far we have been calculating the volume of trapped rainwater for every building. For this, we needed to find the right_max and left_max.

How is this avoided in the stack? In a stack, every time there’s an increase in height, the volume of the trapped water between new increase(current height) and old increase(top of the stack) is calculated. So, for heights smaller than the top of the stack, values are pushed in the stack. When heights larger than the top of the stack are encountered, we can assume that water is trapped between the index present at the top of the stack and the current index. Refer to the illustration given below for a better understanding.

Please note that the values stored in the stack are not the heights of buildings but indexes of these heights.

Algorithm

• Create an empty stack currentStack.
• Loop current from 0 to size of heights array.
  • While currentStack is not empty and height[current] > height[top element of currentStack]:
    • Initialize top = height[top element of currentStack].
    • Pop the top element of the stack.
    • Initialise distance = current - new top element of currentStack - 1.
    • Initialise height_difference = min(height[current], height[new top element in currentStack]) - heights[top].
    • Set volume = distance * height_difference.
    • Add volume to total_volume.
  • Push current to the stack.
• Return total_volume.

Code for Reference

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

 
int rainWaterVol(vector<int> heights) {
    int total_volume = 0, size = heights.size();
    stack<int> currentStack;

    for(int current = 0; current < size; current++) {

 
          /* Calculating the volume of rainwater trapped water trapped
             between the index present at the top of the stack 
             and the current index. */
          while(!currentStack.empty() && heights[current] > heights[currentStack.top()]) {
       
          int top = currentStack.top();
          currentStack.pop();
       
          if(currentStack.empty())
              break;

          int distance = current - currentStack.top() -1;
          int height_difference = min(heights[current],           heights[currentStack.top()]) - heights[top];

          int volume = distance * height_difference;
          total_volume += volume;
   
     }

 
     /* Pushing the current index if it is smaller than 
     the index present on the top of the stack.*/ 
    currentStack.push(current);
}

    return total_volume;
}

int main() {
    int size;
    cout << "Size of the array: ";
    cin >>  size;
 
      vector<int> heights(size);
      cout << "Enter the elements:\n";
      for (int i = 0; i < size; i++) {
          cin >> heights[i];
      }

      cout << "Volume of trapped rainwater: " << rainWaterVol(heights);
}

 

Input Format

Size of the array: 12
Enter the elements:
0    1    0    2    1    0    1    3    2    1    2    1

 

Output Format

Volume of trapped rainwater: 6

Complexity Analysis

Time Complexity: Every element is pushed exactly once in a stack. So, the time complexity is O(n).

Space Complexity: In the worst-case scenario, the stack may need to store all the indexes of the heights vector. So, the space complexity is O(n).

Method 4: Two Pointers Technique

Do you remember how we calculated the volume of trapped rainwater in methods 1 and 2? We used the formula min(right-max, left-max) - heights[current]. This means the calculation requires a minimum of the extremes to calculate the volume. This is our basis for a two-pointers approach.

It’s evident that right_max and left_max will be found on the right and left sides of a building, respectively. We use left pointer to keep track of elements for which min(right-max, left-max) =current left-max . Similarly, the right pointer is used so that we don’t have to calculate min(right-max, left-max) for every building. So, left and right are the two pointers of our two-pointers approach. Please note, the left will always be smaller than the right. 

 

Refer to the following algorithm for better understanding.

Algorithm

• Initialize left = 0 (Index of current where min(right-max, left-max) =left-max ).
• Initialize right = heights.size() - 1(Index of current where min(right-max, left-max) =right-max).
• Set right_max and left_max equal to 0.
• While left < right, do:
  • If heights[left] < heights[right], then:
    • Set left_max = max(left_max, heights[left]).
    • Add left_max - heights[left] to volume.
    • Increment left.
  • Else:
    • Set right_max = max(right_max, heights[right]).
    • Add right_max - heights[right] to volume.
    • Decrement right.

Code for Reference

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

 
int rainWaterVol(vector<int> heights) {
     int total_volume = 0;

    // left and right pointer to track current left_max and right_max.
    int left = 0 , right = heights.size() - 1;
    int right_max = 0, left_max = 0;

    while(left < right) {

          /* If current left_max is less than current right_max,
            water level depends on left_max.*/
          if(heights[left] < heights[right]) {
              left_max = max(heights[left], left_max);
              total_volume += left_max - heights[left];
              left++;
          }
          else {
          
              /* If current right_max is less than current left_max. 
              Water level depends on right_max.*/
              right_max = max(heights[right], right_max);
              total_volume += right_max - heights[right];
              right--;
          }

    }
    return total_volume;
}

 
int main() {
    int size;
    cout << "Size of the array: ";
    cin >>  size;
 
    vector<int> heights(size);
    cout << "Enter the elements:\n";
    for (int i = 0; i < size; i++) {
          cin >> heights[i];
    }

    cout << "Volume of trapped rainwater: " << rainWaterVol(heights);
}

 

Input Format

Size of the array: 12
Enter the elements:
0    1    0    2    1    0    1    3    2    1    2    1

 

Output Format

Volume of trapped rainwater: 6

Complexity Analysis

Time Complexity: Both the pointers start the iteration from the extremes and iterate till they meet. So, a linear loop is completed. Time complexity is O(N).

Space Complexity: Constant space is used. So, the space complexity is O(1)

Check out this problem - Minimum Coin Change Problem 

Frequently Asked Questions

Which is the most optimal approach to the above Trapping Rain Water Problem?

The above Approach 4 - involving the use of two-pointers and utilizing constant space is the most optimal solution to this problem.

What is a Monotonic Stack?

A Monotonic Stack is a Stack whose elements are constantly increasing or decreasing.

Conclusion

There’s usually more than one approach to a solution. Yes, it feels sluggish to solve the same problem again and again. But, we should always try to look for more ways to solve a problem. After all, it’s an excellent way to practice more than one algorithm or technique from a single problem.

Try to memonize the code if some value is computed again and again. If the memoization is in a particular order, go for the monotonic stacks. You can practice memonization and many more cool techniques using our free practice platform Coding Ninjas Studio. So, keep practicing. That’s what good coders do.

Recommended Articles

Coin Change: Minimum Number Of Coins

Count pairs with given sum

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Happy Coding!!