Trapping Rainwater Problem: Three different approaches (brute to optimized)

Trapping rainwater is a very famous problem of arrays and dynamic programming. It is a hard problem on both LeetCode and geeks for geeks. But at the end of this blog, you won’t consider this problem a hard one. :)

In this blog, we will cover the problem starting from the brute force approach to the optimized one.

Problem Statement:

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Example 1:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

Example 2:

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

Constraints:

• n == height.length
• 1 <= n <= 2 * 104
• 0 <= height[i] <= 105

Solution:

Let’s start with the brute force approach first:

Brute Force Approach:

Let’s consider the block in gray color. We can see that it contains one unit of water.

The maximum height of any block on its left is 2. And the maximum height on its right is 3. Thus, the unit of water it contains is:

min(height[left_max],height[right_max]) - height[current_block];
// Thus unit of water stored in the gray block is:
min(2,3)-1;
i.e. 2-1 = 1 units.

Similarly, the block in white, contains 2 units of water because water stored is:

min(height[left_max],height[right_max]) - height[current_block];
i.e. min(2,3)-0;
i.e. 2-0 = 0 units.

I hope you understood the main idea behind the approach.

Analysis:

We will have a loop for traversing the array and covering every element once. At every index, we will find the left and right maximum values. Thus, we will have two nested loops, and the time complexity of this approach will be O(n²). The space complexity will be O(1).

Optimization:

Let’s optimize the brute force a bit.

Instead of traversing the entire array, again and again, we can maintain two different arrays to store the left and right maximum values.

Using this approach, we can solve the question only with one loop.

Thus the time complexity of this approach is O(n).

And since, we have used extra space, the space complexity is also O(n).

We have reduced the time complexity from O(n²) to O(n). We surely deserve a pat on the back. :)

Now, let’s dive deeper and explore a more optimized approach.

Optimized approach:

We will use the concept of two-pointers.

First, declare a left and a right pointer. Initialize the left pointer to 0 and the right one to n-1 (where n is the size of the array) in the beginning. Also, maintain two variables left_max and right_max, and set them to 0.

int n = height.size();
int left=0,right = n-1;
int left_max = 0,right_max = 0;
int result = 0;

Store the water in the result variable.

Now, keeping these variables in mind, let’s observe the following things:

1. The block at the height[left] will store water only if it has a block higher than it on both of its sides. Thus, we have to satisfy two conditions for a block at the height[left] to store some water.

height[left]<=height[right] and height[left]<left_max

Thus, we will update the result to be result + height[left]

2. But, if height[left]≤height[right] and height[left]≥left_max, then we will update left_max to be the height[left].

Then, we will move our left pointer ahead by one position.

3. Similarly, if the block at the height[right] is greater than the height[left], then there are two situations:

if(height[right]>=right_max){
 right_max = height[right];
 }else{
 result += (right_max-height[right]);
 }

We will move our right pointer behind by one position.

The entire code can be written as:

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        int left=0,right = n-1;
        int left_max = 0,right_max = 0;
        int result = 0;
        
        while(left<=right){
            
            if(height[left]<=height[right]){
                if(height[left]>=left_max){
                    left_max = height[left];
                }else{
                    result+= (left_max-height[left]);
                }
                left++;
            }else{
                if(height[right]>=right_max){
                    right_max = height[right];
                }else{
                    result += (right_max-height[right]);
                }
                right--;
            }
        }
     return result;   
    }
};

Analysis:

Since we are traversing the array only once, the time complexity of this approach is o(n).

Also, we haven’t used any extra space keeping the space complexity at its best, i.e. O(1).

Conclusion

We discussed three approaches for the trapping rainwater problem.

The brute force approach used two nested loops and constant space. We found the solution by finding the left and right maximum values of each element.

Then, we used two arrays to store our left and right maximum values and reduced our time complexity to O(n).

In the final approach, we used two-pointers and also reduced our space complexity to O(1).

Now, let’s sip some tea and be proud of us for successfully trapping the maximum water we could with the terrain given to us.