Recent Posts

Trapping rain water problem

Written by

Anshuman Raina

Trapping rain water problem

Input: [1,0,2,1,0,1,3,2,1,2,1]

Output: 6

Explanation: Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can be trapped after raining.
The above problem statement can be a bit perplexing – so see the below picture for reference.

Each square of water trapped is 1 unit.

Instead of directly aiming for Efficient Solution, we aim for a solution firsthand. To quote Donald Knuth, the great computer scientist “Premature Optimization is the root for all evil”.

This problem has 3 main approaches. But firstly, we see the brute force approach, and then we go on improving some bits and parts of our code.

# Brute Force

Herein, we simply aim for the solution, no matter the cost. So, devising a pseudo code for this:

  1. Maintain two indices, one to iterate on the length of elevation or tower at the index, and other to calculate the water at a particular index.
  2. Iterate till length :
    a. Store the max length of the buildings to the left and to the right of the index.
    b. The shorter of the two is taken as the level till which the water can rise.
    c. Decrease the height of the building at current index
  3. Summation of water collected at all indices gives us the total water.

Code:

#include <iostream>
#include <algorithm>
using namespace std;
void bruteForceRainwater(int buildingArray[], int size)
{
	if (size == 1 || size == 0)
	{
		cout << "Sorry";
		return;
	}
	int index, waterAtCurrent, totalWater = 0;
	for (index = 1; index < size - 1; index++)	// as will iterate till second last, water can never be stored at the first and the last
	{
		int left = buildingArray[index];
		for (int j = 0; j < index; j++)
			left = max(left, buildingArray[j]);

	// Find the maximum element on its right
	int right = buildingArray[index];
	for (int j = index + 1; j &lt; size; j++)
		right = max(right, buildingArray[j]);
	int waterLevel = (min(left, right)) - buildingArray[index];
	if (waterLevel &gt;= 0)
		waterAtCurrent = waterLevel;
	else
		waterAtCurrent = 0;
	totalWater += waterAtCurrent;
}
cout &lt;&lt; "Total Water is :";
cout &lt;&lt; totalWater;



}
int main()
{
int buildings[] = { 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 };
bruteForceRainwater(buildings, 11);
return 0;
}

Time complexity : O(n2).
Space complexity: O(1)

# Improvement on Time Complexity

We try to reduce the time complexity here.

Code:

#include <iostream>
#include <algorithm>
using namespace std;

void reduceTimeRainwater(int buildingArray[], int size)
{
if (size == 1 || size == 0)
{
cout << "Sorry";
return;
}
int index, waterAtCurrent, totalWater = 0;
int leftArray[size], rightArray[size];
leftArray[0] = buildingArray[0];
for (int i = 1; i < size; i++)
leftArray[i] = max(leftArray[i - 1], buildingArray[i]);


rightArray[size - 1] = buildingArray[size - 1];
for (int i = size - 2; i &gt;= 0; i--)
	rightArray[i] = max(rightArray[i + 1], buildingArray[i]);
for (index = 1; index &lt; size; index++)
{
	waterAtCurrent = min(leftArray[index], rightArray[index]) - buildingArray[index];
	totalWater += waterAtCurrent;
}
cout &lt;&lt; "Total Water is :" &lt;&lt; totalWater;



}


int main()
{
int buildings[] = { 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 };
reduceTimeRainwater(buildings, 11);
return 0;
}

Time complexity: O(n)
Space complexity: O(n)

# Decreasing the auxiliary space required

This is the most efficient solution, with us minimizing the spacing required by our program.
Code:

#include <iostream>
using namespace std;
int findWater(int buildingArray[], int n)
{
	int totalWater = 0;
	int left = 0, right = 0;
	int low = 0, high = n - 1;

whighle(low &lt;= high)
{
	if (buildingArray[low] &lt; buildingArray[high])
	{
		if (buildingArray[low] &gt; left)
			// update max in left
			left = buildingArray[low];
		else
			totalWater += left - buildingArray[low];
		low++;
	}
	else
	{
		if (buildingArray[high] &gt; right)
			// update right maximum
			right = buildingArray[high];
		else
			totalWater += right - buildingArray[high];
		high--;
	}
}
cout &lt;&lt; "Total Water is " &lt;&lt; totalWater;



}


int main()
{
int[] buildings = { 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 };


optimizedSpaceRainwater(buildings, 11);



}

Time complexity :O(n)
Space complexity :O(1)

Output :

Total Water is: 6

This is how we solve the trapping rainwater problem.

Trapping rain water problem