Trapping Rain Water

Trapping Rain Water

Problem Statement

Given an integer array A[] consisting of N non-negative integers representing an elevation map, where the width of each bar is 1. The task is to compute the total volume of water that can be trapped after rain.

Examples :

Input: A[] = { 0 , 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 }
Output: 6
Explanation:

Confused about your next job?

In 3 simple steps you can find your personalised career roadmap in Software development for FREE



Expand in New Tab 

 

The rain water trapped is represented by the blue region.

  • Trap 1 unit of water between the first and third block
  • Trap 4 units of water between the second and third blocks.

Therefore, the total volume of water is – 1 + 4 + 1 = 6 units.

Algorithm

The key idea to solve this problem is to understand that rainwater can only be trapped if there exists a block of greater height, both on the left and the right side than the current block. Then rainwater can be trapped on top of the block.

So, it can be easily inferred that the amount of water a block can hold is equal to the minimum of the maximum height present on both the left and right half minus the height of the current block.

i.e.

Vol_of_A[i] = min(right_max, left_max) – A[i]

Bruteforce Approach


Since our task is to find the maximum height on left and right for each element of the array, simply traverse each element of the array A[]. For each element, find the maximum height on the left and maximum height on the right. At last, add min(right_max, left_max) – A[i] to answer.

Below are the steps:

  • Initialise a variable res to 0, to store the final answer.
  • Traverse the array A[] from 1 to N and for each element:
    • Initialise left_max = 0 and right_max = 0
    • Traverse from A[i] till the beginning and update:
      • left_max = max(left_max, A[i])
    • Similarly, traverse from A[i] till the end of the array and update:
      • right_max = max(right_max, A[i])

Add min(left_max, right_max) – A[i]  to res.

C++ Implementation of Bruteforce Approach

class Solution {
public:
    int trapping_rain_water(vector<int>& A) {
         
        int res = 0;
        for (int i = 1; i < A.size() - 1; i++) {
            
            //Find left_max
            int left_max = INT_MIN;
            for (int j = i - 1; j >= 0; j--) {
                left_max = max(left_max, A[j]);
            }
			//Find right_max
            int right_max = INT_MIN;
            for (int k = i + 1; k < A.size(); k++) {
                right_max = max(right_max, A[k]);
            }
			//Find volume
            int maxW = min (left_max,right_max);
            res += maxW - A[i];
        }
        return res;
    }
};

Java Implementation of Bruteforce Approach

public static int trapping_rain_water(int[] A, int N)
{
    int res = 0;
    for(int i = 0; i < N ; i++)
    { 
        int left_max= arr[i];
        for(int j = i - 1; j >= 0; j--)
        {
            left_max = Math.max(left_max, A[j]);
        }
        int right_max = A[i];
        for(int j = i + 1; j < n; j++)
        {
            right_max = Math.max(right_max, A[j]);
        }
        res += Math.min(left_max, right_max) - A[i];
    }
    return res;
}

Python Implementation of Bruteforce Approach

def trapping_rain_water(A, N) :
    res = 0;
    for i in range(1, N - 1) :
        left_max = A[i];
        for j in range(i) :
            left_max = max(left_max, A[j]);
         
        right_max = A[i];
         
        for j in range(i + 1 , n) :
            right_max = max(right_max, A[j]);
        res = res + (min(left_max, right_max) - A[i]);
 
    return res;

Time Complexity: O(N^2). For each element, the left and right half are traversed.
Space Complexity: O(1)


Dynamic Programming Approach – Trapping Rain Water

Can we improve the efficiency from O(N^2) to O(N)? Remember, in brute force, we are traversing left and right for each element. What if we store this information, then the problem can be solved using a single traversal, essentially reducing the time complexity to O(N).

The idea is to consider two arrays left_max[] and right_max[], where left_max[i] will store the maximum height on the left until index i. Similarly,  right_max[i] will store the maximum height on the right until index i.

Algorithm:

  • Initialise two arrays left_max[] and right_max[] of size N.
  • Consider a variable mx = 0.
  • Traverse from left to right and for each index i, update mx = max(mx, A[i[) and assign left_max = mx.
  • Similarly, traverse a loop, N to 1 and for each index i, update mx = max(mx, A[i[) and assign right_max = mx.
  • Initialise a variable res = 0 and traverse from 0 to N – 1. For each index i, add min(left_max[i], right_max[i]) – A[i] to res.

C++ Implementation of DP Approach

class Solution {
public:
   
	int trapping_rain_water(vector<int>& A)
	{
		int res = 0;
		int N = A.size();
		int left_max[N], right_max[N];
		int mx = INT_MIN;
		for (int i = 0; i < N; i++) {
			mx = max(mx, A[i]);
			left_max[i] = mx;
		}
		mx = INT_MIN
		for (int i = N - 1; i >= 0; i--) {
			mx = max(mx, height[i]);
			right_max[i] = mx
		}
		for (int i = 0; i < N ; i++) {
			res += min(left_max[i], right_max[i]) - A[i];
		}
		return res;
	}
};

Java Implementation of DP Approach

public int trapping_rain_water(int[] A) {
 int res = 0;
 if (A.length == 0) {
   return 0;
 }
 int[] leftMax = new int[A.length];

 int[] rightMax = new int[A.length];

 leftMax[0] = A[0];

 for (int i = 1; i < leftMax.length; i++) {
   leftMax[i] = Math.max(leftMax[i - 1], A[i]);
 }

 rightMax[A.length - 1] = A[A.length - 1];

 for (int j = rightMax.length - 2; j >= 0; j--) {
   rightMax[j] = Math.max(rightMax[j + 1], A[j]);
 }
 for (int x = 0; x < A.length; x++) {
   res += Math.min(leftMax[x], rightMax[x]) - A[x];
 }
 return res;
}

Python Implementation of DP Approach

def trapping_rain_water(self, A: List[int]) -> int:
       N = len(A)
       left_max = N * [0]
       right_max = N * [0]
       ans = 0
       for i in range(N):
           if i == 0:
               left_max[i] = Z[i]
               right_max[N-1-i] = A[n-1-i]
           else:
               left_max[i] = max(left_max[i-1], A[i])
               right_max[n-1-i] = max(right_max[n-i], A[N-1-i])
              
       for i in range(N):
           ans += (min(left_max[i], right_max[i]) - A[i])
      
       return ans

Time Complexity: O(N) + O(N) + O(N) = O(N), since the array is traversed thrice.
Space Complexity: O(N), since two arrays are needed.


Approach 3: Using stacks

In DP, the arrays were traversed twice. Can we improve the approach to a single scan? The idea is to keep track of the area between the current block A[i] and all the previous blocks with smaller heights in the array. We can simply use a stack to track the index of the previous smaller blocks.

Algorithm:

  • Declare a stack S.
  • Traverse the array from left to right:
    • If the current block A[i] is larger than the top of the stack i.e. S.top(), it can be inferred that the block at the top of the stack is confined between the current block and the previous block in the stack.
    • Therefore, perform S.pop() and add the water that can be stored.
  • The total volume of water can be calculated as follows:
    • Length = Current index i  – S.top() – 1
    • Width =  min(A[i] – A[S.top()] – A[top]
    • Add the total volume to res = Length X Width

C++ Implementation – Using Stacks

class Solution {
public:
   
	int trapping_rain_water(vector<int>& A)
	{
		//Final answer
		int res = 0;
		int N = A.size();
		
		//Stack to store indices
		stack<int>S;
		
		int i = 0;
		
		//Traverse through each block
		while(i < N){
		  
		  while(!S.empty() and A[i] > A[S.top()]){
			  
			  //Store the height of the top
			  int top = A[S.top()];
			  S.pop();
			  
			  
			  if(S.empty()){
				  break;
			  }
			  
			  //Find distance between the left and right height
			  int length = i - S.top() - 1;
			  //Finding width 
			  int width = min(A[i], A[S.top()]) - A[top];
			  
			  //Total volume of water added
			  res += length * width;  	
		  }
		  
		  S.push(i);
		  i = i + 1;
		}
		
		return res;
	}
};

Java Implementation – Using Stacks

public int trapping_rain_water(int[] A) {
       int N = A.length;
       int res = 0;
       Stack<Integer> stack = new Stack<Integer>();
       int i = 0;
       while(i < N){
           while (!stack.isEmpty() && A[i] > A[stack.peek()]) {
             
               int top = A[stack.peek()];
               stack.pop();
               if(stack.isEmpty()){
                   break;
               }
               int length =  i - stack.peek() - 1;
               int width = Math.min(A[i], A[stack.peek()]) - A[top];
               res += length * width;
               if (height[leftIndex] <=  height[i]) {
                   stack.pop();
               }
           }
           stack.push(i);
           i = i + 1;
       }
       return res;
   }

Python Implementation – Using Stacks

def trapping_rain_water(A):
       stack = []
      
       res = 0
       for i in range(len(A)):
           while stack and A[i] > A[stack[-1]]:
               pop = stack.pop()
               if stack:
                   left = A[stack[-1]]
                   right = A[i]
                   res += (min(right, left) - A[pop])*(i-stack[-1]-1)
                  
           stack.append(i)
      
       return res

Time Complexity: O(N), since the array is traversed once.
Space Complexity: O(N). Stack takes O(N) space.


Two Pointers Approach

In the last approach, though it is solved using a single traversal, it uses an extra space. Can it be improved to O(1) space?

According to Approach 2, the total volume of water trapped is dependent upon the minimum-maximum of height on the left and right half of the current block. Therefore, instead of considering two arrays to store the heights, we can simply use two variables to store the maximum for the given index. But how?

Take two points, once on the left side of the array and another on the right side. If there is a block on the left, then the total water trapped would be dependent in the direction right to left and vice versa.

Algorithm:

  • Initialise two pointer left = 0 and right = N – 1 and res = 0.
  • Initialise two variables left_max = 0 and right_max = 0, denoting the maximum height on the left and maximum height on the right.
  • Traverse the array, i.e. while(left <= right)
    • If A[left] < A[right] and left_max > A[left]
      • Then, add left_max – A[left] to res
      • Else if left_max < A[left]
        • Update left_max to A[left]
      • Increment left pointer
    • Similarly, if If A[left] > A[right] and right_max > A[right]
      • Then, add right_max – A[right] to res
      • Else if right_max < A[right]
        • Update right_max to A[right]
      • Increment right pointer
  • Print res

C++ Implementation Using Two Pointers

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

Java Implementation Using Two Pointers

public int trapping_rain_water(int[] A) {
           int res =0;
           int left_max = 0;
           int right_max = 0;
           int i = 0;
           int j = A.length -1;
           while(i< j){
               left_max = Math.max(left_max, A[i]);
               right_max = Math.max(right_max, A[j]);
               if(left_max < right_max){
                   res += left_max-A[i];
                   i++;
               }
               else{
                   res += right_max - A[j];
                   j--;
               }
           }
           return res;
       }

Python Implementation Using Two Pointers

def trapping_rain_water(A):
      
       i, j = 0, len(A) - 1
       lMax, rMax = A[i], A[j]
       res = 0
       while i < j:
           left_max = max(left_max, A[i])
           right_max = max(right_max, A[j])
           if left_max < right_max:
               res += left_max - A[i]
               i += 1
           else:
               res += right_max - A[j]
               j -= 1
       return res

Time Complexity: O(N), since the array is traversed once.
Space Complexity: O(1).


Practice Problem

Container With Most Water


Frequently Asked Questions

How many methods are there to solve the trapping rainwater problem?
There are mainly 4 methods to solve the problem, all are mentioned above.

Which is the best approach with respect to the time and space complexity.
The two-pointer approach is the best approach, it has O(N) time complexity and O(1) space complexity.

Previous Post
Subset Sum Problem

Subset Sum Problem

Next Post
Python vs R

Python Vs R: Know The Difference

Total
0
Share