Rain Water Harvesting

Last updated: 29th Aug, 2020

Problem Statment

Apoorvaa has created an elevated roof. She wants to know how much water can she save during rain.
Given n non negative integers representing the elevation map where width of every bar is 1, Find the maximum water that she can save.
First line contains an integer n. Second line contains n space separated integers representing the elevation map.

Example 1:

10
0 2 1 3 0 1 2 1 2 1

>> 5

Approach:

To find the highest bar on the left and right, array traversal is needed which reduces the efficiency of the solution. To make this efficient one must pre-compute the highest bar on the left and right of every bar in linear time. Then use these pre-computed values to find the amount of water in every array element.

Complexity Analysis:
Time Complexity: O(n).
Only one traversal of the array is needed, So time Complexity is O(n).
Space Complexity: O(n).
Two extra array is needed each of size n.

C++ Code

#define ll long long int

int main()
{
	long long int n,i,j;
	cin>>n;
	if(n==0)
	{
	cout<<0<<endl;
	return 0;
	}
	long long int a[n];
	for(i=0;i<n;i++)
	{

		cin>>a[i];
		if(a[i]<0)
		{
			a[i]=a[i]*-1;
		}

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

		}
		for(j=n-2;j>=0;j--)
		{
			right[j]=max(right[j+1],a[j]);

		}
	for(i=0;i<n;i++){

		res+=(min(left[i],right[i])-a[i]);
	}
	cout<<res<<endl;
}