Trapping Rain Water

Let’s understand the problem

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

Example 1

Input: height[] = [2, 0, 1, 0, 2], Output: 5
Explanation: 
Trapped water = 2 x 1 + 1 x 1 + 2 x 1 = 5 (Area of the blue region in the following diagram)

Example 2

Input: height[] = [0,1,0,2,1,0,1,3,2,1,2,1], Output: 6
Explanation: 
Trapped water = 1 x 1 + 1 x 1 + 2 x 1 + 1 x 1 + 1 x 1 = 6 (Area of the blue region in the following diagram)

Important Note: Before moving to the solutions, we recommend learners solve this problem. If solved, then well done! We would like to hear your ideas in the comment. Otherwise no problem, this is an opportunity to learn a new pattern in problem-solving. Think and Enjoy :)

Discussed Solution Approaches

1. Brute force solution using nested loops
2. Solution using extra memory: Dynamic Programming
3. Solution using data structure: Stack
4. Efficient solution using single scan: Two pointers

1. Brute force solution using nested loops

Algorithm Idea

One basic idea would be to scan the height[] array and sum the water trapped at each tower. The height of water trapped at any tower height[i] = minimum of maximum height of towers on both the sides minus its height, i.e., min (max tower height in the left, max tower height in the right) — height[i]

Algorithm Steps

• We declare and initialise the variable trappedWater to store the total trapped water.
• Now scan the height[] from from i = 0 to n-1. Inside the loop, we declare and initialise the variable left_maxHeight and right_maxHeight to store the maximum height of the tower on both sides of the current tower.
• For each tower height[i], we calculate the maximum height of the tower from current index i up to the left end. We store this value in the variable left_maxHeight.

for(int k = i; k >= 0; k = k - 1)
{
    left_maxHeight = max(height[k], left_maxHeight)
}

• For each tower height[i], we calculate the maximum height of tower from current index i up to right end. We store this value in the variable right_maxHeight.

for(int j = i; j < n; j = j + 1)
{
    right_maxHeight = max(height[j], right_maxHeight)
}

• Now we update the total amount of water by using the above formula.

trappedWater 
= trappedWater + min(left_MaxHeight, right_maxHeight) - height[i]

• By end of the above loop, we return the value of the variable trappedWater.

Programming Pseudo Code

int rain_water_trapping(int height[], int n)
{
    if(n <= 2)
        return 0
    int trappedWater = 0
    for(int i = 0; i < n; i = i + 1)
    {
        int left_maxHeight = 0 , right_maxHeight = 0
        for(int k = i; k >= 0; k = k - 1)
        {
            left_maxHeight = max(height[k], left_maxHeight)
        } 
        for(int j = i; j < n; j = j + 1)
        {
            right_maxHeight = max(height[j], right_maxHeight)
        }
        trappedWater = trappedWater + 
                   min(left_maxHeight, right_maxHeight) - height[i]
    }
    return trappedWater
}

Time and Space Complexity Analysis

We are using nested loops where the outer loop is scanning the height[] array, and two inner loops are finding right_maxHeight and left_maxHeight. So every iteration of the outer loop, we are traversing each element via inner loops. Time Complexity = O(n * n) = O(n²), Space Complexity = O(1)

2. Solution using extra memory: Dynamic Programming

Algorithm Idea

Can we improve the efficiency further and solve the problem in O(n)? Is it possible to remove the separate inner loop for finding the left_maxHeight and right_maxHeight? Let’s think!

If the values of left_maxHeight and right_maxHeight known for every tower then we can solve this problem in a single scan of the height[i] array. But how can we do this? One idea would be to pre calculate left_maxHeight and right_maxHeight for each tower height[i] and store them in separate extra memory.

Suppose we take left[n] and right[n] to store the values where: left[i] = left_maxHeight of the tower height[i], right[i] = right_maxHeight of the tower height[i]

Can we do the pre-processing and store values in linear time? Here is an idea:

• Suppose we know the value of left[i-1], then we can easily calculate the left[i] in O(1). Here is the formula => left[i] = max (left[i-1], height[i]) (Think)
• Similarly, if we know the value of right[i+1], then we can easily calculate the right[i] in O(1). Here is the formula => right[i] = max (right[i+1], height[i]) (Think)

This is a dynamic programming approach where we are using the stored solution of the smaller problem to get the solution of the larger problem.

Algorithm Steps

• We create two arrays left[n] and right[n]
• Now run a loop from left to right and fill the left[n] array. At every iteration i, we store the maximum element that occurred up to that point in left[i]. (Think!)

left[0] = height[0]
for(int i = 1; i < n; i = i + 1)
{
    left[i] = max(left[i-1], height[i])
}

• Similarly, run a loop from right to left, and fill the right[n] array. At every iteration i, store the maximum element occurred up to that point in right[i]. (Think!)

right[n-1] = height[n-1]
for(int i = n-2; i >= 0; i = i - 1)
{
    right[i] = max(right[i+1], height[i])
}

• Now, traverse the height[] array and calculate the total amount of water.

int trappeWater = 0
for(int i = 0; i < n; i = i + 1)
{
    trappedWater = trappedWater + min(left[i], right[i]) - height[i]
}

• Return the value stored in the variable trappedWater.

Programming Pseudo Code

int rain_water_trapping(int height[], int n)
{
    if(n <= 2)
        return 0
    int left[n], right[n]
    left[0] = height[0]
    for(int i = 1; i < n; i = i + 1)
    {
        left[i] = max(left[i-1], height[i])
    }
 
    right[n-1] = height[n-1]
    for(int i = n-2; i >= 0; i = i - 1)
    {
        right[i] = max(right[i+1], height[i])
    }
  
    int trappeWater = 0
    for(int i = 0; i < n; i++)
    {
        trappedWater = trappedWater + 
                       min(left[i], right[i]) - height[i]
    }
    return trappedWater
}

Time and Space Complexity Analysis

In the above pseudo code, we are running three independent loops of size n. To find right_maxHeight and left_maxHeight, we used two separate loops. And, to traverse the array, also we used one loop. So, Time Complexity = O(n) + O(n) = O(n).

We used two extra arrays of size n. So Space Complexity = O(n) + O(n) = O(n)

3. Solution using data structure: Stack

Can we solve this problem in a single scan? Let’s explore.

• Area of region 1 = area confined between index 2 and 0
• Area of region 2 = area confined between index 5 and 3
• Area of region 3 = area confined between index 6 and 3
• Area of region 4 = area confined between index 6 and 2
• Area of region 5 = area confined between index 8 and 6
• Area of region 5 = area confined between index 9 and 6

Did we observe some pattern? Idea would be to track the area confined between current tower and all the previous smaller towers in the sequence. We can use a stack to track the indices of the previous smaller towers. (Think!)

Algorithm Steps

• We declare a stack S to store the indices of the towers.
• Now we scan the height[n] using a loop variable curr < n
• If we found a current tower larger than that tower at the top of the stack, we can say that the tower at the top of the stack is confined between the current tower and a previous tower in the stack. Hence, we pop the stack and add water trapped between towers to the total water trapped. We can continue this step in a loop until we find the current tower smaller than the tower at the top of the stack.
• Water trapped between towers = Area of the rectangular region formed by the current tower, popped tower, and tower at the top of the stack

Region length = (current index — index of the top stack element — 1)

Region height = min (height of the current tower, height of tower at top of the stack) — height of the popped tower

Water trapped = Region length x Region height

• If the current tower is smaller than or equal to the tower at the top of the stack, we push the index of the current tower to the stack and move to the next tower. It means current tower is confined with tower at the top of the stack.

Programming Pseudo Code

int rain_water_trapping(int height[], int n)
{
    int trappeWater = 0, curr = 0
    stack S
    while (curr < n)
    {
        while (!S.empty() && height[curr] > height[S.top()])
        {
            int top_tower = S.Pop()
            if (S.empty())
                break
            int region_length = curr - S.top() - 1
            int region_height = min(height[curr], height[S.top()]) 
                                - height[top_tower]
            trappedWater = trappedWater + 
                           region_length * region_height
        }
        S.push(curr)
        curr = curr + 1
    }
    return trappedWater
}

Note: If(height[curr] > height[S.top()]), then tower at the top of the stack is smaller than previous tower in the stack and current tower. In such scenario, it would form a colored rectangular region and trapped water is equal to the area of that region.

Time and Space Complexity Analysis

We are doing single traversal of the height[] array. In the worst case, we are processing each tower twice using stack i.e. one push() and one pop() operation. (Think!) Both push() and pop() operations takes O(1) time in the worst case. So, time Complexity = O(n).

In the worst-case stack can take up to n elements. Space Complexity = O(n)

4. Efficient solution using single scan: Two pointers

Algorithm Idea

In the last two approaches, we are using extra spaces to get the solution. Can we solve this problem in a single scan without using extra space? Let’s explore!

Based on the formula used in the 2nd approach, the water trapped by any tower depends on the minimum of maximum height of towers on both sides. So instead of maintaining two arrays of size n for storing left_maxHeight and a right_maxHeight, can we think to maintain two variables to store the maximum till a given point? Think!

Suppose we search from both the left and right end by maintaining two pointers left and right separately. If there is a larger tower at the right end, then the water trapped would be dependant on the tower’s height in the direction from left to right. Similarly, if the tower at the right end is smaller, then the water trapped would be dependant on the tower’s height in the direction from right to left. (Think!)

We first calculate the water trapped on smaller elements out of height[left] and height[right], then move the pointer associated with the smaller element. We move the pointers till the left doesn’t cross right. In terms of analogy, we can think of height[left] and height[right] as a wall of a partial container where we fix the higher one and flow water from the lower part.

Algorithm Steps

• We declare and Initialise left and right pointers.
• Also declare and Initialise variables trappedWater, left_maxHeight and right_maxHeight.

int trappedWater = 0
int left_maxHeight = 0, right_maxHeight = 0
int left = 0, right = n - 1

• Now run a loop to scan the array i.e. while (left <= right)

If (height[left] < height[right]) and (height[left] < left_maxHeight), then we calculate the trapped water stored by the both towers and increase the left pointer. But if (height[left] > left_maxHeight), then we update value of left_maxHeight and increase the left pointer.

if (height[left] < height[right])
{
    if (height[left] > left_maxHeight)
        left_maxHeight = height[left]
    else
        trappedWater = trappedWater + left_maxHeight - height[left]
    left = left + 1
}

If (height[left] > height[right]) and height[right] < right_maxHeight) then we calculate the trapped water stored by the both towers and decrease the right pointer. But if (height[right] > right_maxHeight), then we update value of right_maxHeight and decrease the right pointer.

if (height[left] > height[right])
{
    if (height[right] > right_maxHeight)
        right_maxHeight = height[right]
    else
        trappedWater = trappedWater + right_maxHeight 
                                    - height[right]
    right = right - 1
}

• When left > right, then we exit the loop and return the value stored in the trappedWater.

Programming Pseudo code

int rain_water_trapping(int height[], int n)
{
    int trappedWater = 0
    int left_maxHeight = 0, right_maxHeight = 0
    int left = 0, right = n - 1
    while (left <= right)
    {
        if (height[left] < height[right])
        {
            if (height[left] > left_maxHeight)
                left_maxHeight = height[left]
            else
                trappedWater = trappedWater + left_maxHeight 
                                            - height[left]
            left = left + 1
        }
        else
        {
            if (height[right] > right_maxHeight)
                right_maxHeight = height[right]
            else
                trappedWater = trappedWater + right_maxHeight 
                                            - height[right]
            right = right - 1
        }
    }
    return trappedWater
}

Important Note: We recommend learners transform the above pseudo codes into a favorite programming language (C, C++, Java, Python, etc.) and verify all the test cases. Please let us know if you find any errors or bugs; we would be highly grateful. Enjoy programming!

Time and Space Complexity Analysis

We are doing single scan to traverse the array from both ends. After each comparison, we are moving either left pointer or right pointer. So in the worst case, we need to do O(n) operations.

Time Complexity = O(n), Space Complexity = O(1), only constant space required for variables and pointers.

Possible question by the interviewer: Ideas to think!

• Can we find some other approach to solve this problem in O(n) time and O(1) space? Here is a hint: We first search the maximal tower in height [] and split the array into two halves around it. Now we do two traversals: one from the leftmost tower to the highest tower and another one from the rightmost to the highest tower.
• In the dynamic programming approach, can we save one pass? Here is a hint: Use one array to keep track of maximum height on one side, i.e., left or right. For the other side, we can use a variable to keep track of maximum height so far and process it on the fly during the process when we calculate the volume of water in each tower.
• In the stack-based approach, what would be the best and worst-case scenario?
• In the 4th approach, can we compare left_maxHeight and right_maxHeight to decide which pointer to move?

Comparisons of Time and Space Complexities

• Brute force approach: Time Complexity = O(n²), Space Complexity = O(1)
• Using dynamic programming: Time Complexity = O(n), Space Complexity = O(n)
• Using stack data structure : Time Complexity = O(n), Space Complexity = O(n)
• Using two pointers: Time Complexity = O(n), Space Complexity = O(1)

Key takeaway from this coding problem

• A famous interview problem that can be solved using multiple approaches.
• One of the best coding problem to learn time and space complexity optimization
• Two pointers and stack based solutions are highly intuitive. We can use a similar idea to solve other coding problems.

Similar coding questions to practice

You can find some of these problems on leetcode or other coding platforms. Explore and Practice!

• Container with Most Water
• Product of Array Except Self
• Trapping rainwater in a 2D elevation map
• Move zeroes to an end
• Merge two sorted arrays
• maximum j — i such that A[j] > A[i]
• The intersection of two sorted array
• Count the number of possible triangles

Reviewer: Shubham Gautam (https://shubhamsuper30.medium.com)

If you have any ideas/queries/doubts/feedback, please comment below or write us at contact@enjoyalgorithms.com. Enjoy learning, Enjoy coding, Enjoy algorithms!