Home » Interview coding problems/challenges

Rain Water Trapping Problem

Rain Water Trapping Problem: Here, we are going to learn to find the solution of Rain Water Trapping Problem – which has been featured in coding interviews of many top companies such as Goldman sachs, Amazon, Factset, DE-Shaw etc.
Submitted by Divyansh Jaipuriyar, on May 11, 2020

Problem statement:

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

Input:

The first line of input contains an integer T denoting the number of test cases. The first line of each test case is N, N is the size of the array. The second line of each test case contains N input arr[i], where arr[i] represent the height of the building.

Output:

For each testcase, print the maximum water stored in those building.

Examples:

    Input:	
    T = 1
    N = 6
    [6,2,4,2,4,6]
    
    Output: 
    12, 4, units of water at index 1 and 3 and 2 unit 
    of water at index 2 and 4, hence overall 12 units of water.

    Input:
    T = 1
    N = 3
    [4,4,4,4,4]
    
    Output: 
    0, 
    We cannot store any amount of water in 
    this construction as all are equal.

Solution Approach

1) Brute Force Approach

The idea is to traverse every array element and find the highest bars on the left and right sides. Take the smaller of two heights. The difference between the smaller height and height of the current element is the amount of water that can be stored in this array element.

We will traverse the array from start to end, for every element we will find the maximum value from left and right and then take the minimum value and subtract that from the current height of the building. We will keep summing the values from first to last.

Pseudo Code:

maxwater(int arr[],int n):
    for (int i = 1; i < n-1; i++){ 
        // Find the maximum element on its 
        // left and keep it on left vaiable. 
        int left = arr[i]   
        for (int j=0; j<i; j++) 
            left = max(left, arr[j]); 
          
        // Find the maximum element on its 
        // right and keep it on right variable.   
        int right = arr[i]; 
        for (int j=i+1; j<n; j++) 
            right = max(right, arr[j]);  
         
        // keep updating values in res variable.     
        res = res + (min(left, right) - arr[i]);    
    }
  • Time Complexity for above approach: O(n*n)
  • space Complexity for above approach: O(1)

C++ Implementation:

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

int main()
{
    int t;
    cout << "Enter number of test cases: ";
    cin >> t;

    while (t--) {
        int n;
        cout << "Enter size of array: ";
        cin >> n;

        cout << "Enter number of elements: ";
        int arr[n];
        for (int i = 0; i < n; i++)
            cin >> arr[i];
        
        int sum = 0;
        for (int i = 1; i < n - 1; i++) {
            //initialise left temporary variable.
            int left = arr[i]; 
            //initialise right temporary variable.
            int right = arr[i]; 

            for (int j = 0; j < i; j++)
                left = max(arr[j], left); //find left maximum values.
            //int right=arr[i];
            for (int j = i + 1; j < n; j++)
                right = max(right, arr[j]); //find right maximum values.
            //take the amount of water it can hold and take summation.
            sum += (min(left, right) - arr[i]); 
        }
        cout << sum << "\n";
    }
    
    return 0;
}

Output

Enter number of test cases: 3
Enter size of array: 5
Enter number of elements: 4 5 6 2 3
1
Enter size of array: 6
Enter number of elements: 6 2 4 2 4 6
12
Enter size of array: 4   
Enter number of elements: 1 2 3 4
0

2) Efficient Approach

We will use precomputed values of height in two arrays left and right.

Initially left[0] value will be same as left[0]=arr[0] as there are no other element left of it and right[n-1] will be arr[n-1] as there is no other right element. For other elements we will take min(left[i],right[i])-arr[i] as the sum of water.

Pseudo Code:

maxwater(int arr[],int n):
    //left and right array declaration.
    left[n],right[n]
	
    //left[0]=arr[0] as there are no elements to left of it.
    left[0]=arr[0]
	    
    //right[n-1] =arr[n-1] as there is no elements.
    right[n-1]=arr[n-1]
 
    for(int i=1;i<n;i++)
        //iterate each element from index 1 to n-1 and 
        //keep checking left of it for maximum values.
        left[i]=max(left[i-1],arr[i])  

    for(int j=n-2;j>=0;j--)
        //iterate each element from index n-2 to 0 and 
        //keep checking right of it for maximum values.
        right[i]=max(right[i+1],arr[i])

    for(int i=0;i<n;i++)
        //keep summation of the maximum water values.
        sum+=((left[i]-right[i])-arr[i]) 

    return sum
  • Time Complexity for above approach:  O(n)
  • Space Complexity for above approach: O(n)

C++ Implementation:

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

typedef long long ll;

int main()
{
    ll t;
    cout << "Enter number of test cases: ";
    cin >> t;

    while (t--) {
        ll n;
        cout << "Enter size of array: ";
        cin >> n;

        ll arr[n];

        cout << "Enter array elements: ";
        for (ll i = 0; i < n; i++)
            cin >> arr[i];
        
        //declare array elements left and right.
        ll left[n], right[n]; 
        left[0] = arr[0];
        right[n - 1] = arr[n - 1];
        
        for (int i = 1; i < n; i++) {
            //take max of left values.
            left[i] = max(left[i - 1], arr[i]); 
        }
        for (int i = n - 2; i >= 0; i--)
            //take max of right values.
            right[i] = max(right[i + 1], arr[i]); 

        ll sum = 0;
        for (ll i = 1; i < n - 1; i++) {
            //take summation of maximum water amount of water.
            sum += (min(left[i], right[i]) - arr[i]); 
        }
        
        //print maximum amount of water.
        cout << sum << "\n";
    }
    
    return 0;
}

Output

Enter number of test cases: 3
Enter size of array: 5   
Enter array elements: 1 2 3 4 5
0
Enter size of array: 5
Enter array elements: 5 4 3 2 1
0
Enter size of array: 6
Enter array elements: 9 2 5 2 4 1
5

Problem reference: https://leetcode.com/problems/trapping-rain-water/






Comments and Discussions

Ad: Are you a blogger? Join our Blogging forum.





Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing
» Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates


© https://www.includehelp.com some rights reserved.