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***is the size of the array. The second line of each test case contains*

**N***input*

**N***, where*

**arr[i]***represent the height of the building.*

**arr[i]****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

*as there are no other element left of it and*

**left[0]=arr[0]***will be*

**right[n-1]***as there is no other right element. For other elements we will take*

**arr[n-1]***as the sum of water.*

**min(left[i],right[i])-arr[i]****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/

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions

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