top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

Trapping rain water: Compute how much water it is able to trap after raining?

+3 votes
349 views

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?

Examples:

Input: arr[]   = {2, 0, 2}
Output: 2
Structure is like below
| |
|_|
We can trap 2 units of water in the middle gap.

Input: arr[]   = {3, 0, 0, 2, 0, 4}
Output: 10
Structure is like below
     |
|    |
|  | |
|__|_| 
We can trap "3*2 units" of water between 3 an 2,
"1 unit" on top of bar 2 and "3 units" between 2 
and 4.  See below diagram also.

Input: arr[] = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
Output: 6
       | 
   |   || |
_|_||_||||||
Trap "1 unit" between first 1 and 2, "4 units" between
first 2 and 3 and "1 unit" between second last 1 and last 2 
posted Dec 17, 2015 by Shishir Chaudhary

Share this question
Facebook Share Button Twitter Share Button LinkedIn Share Button

2 Answers

+1 vote

For example,
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

#include<cstring>
#include<iostream>
using namespace std;
#define mfor(i,n) for(int i=0;i<n;i++)


int main(){

 int array[10000],n;
 cin>>n;

 mfor(i,n)
 cin>>array[i];

 int maxtillnow = array[0];
 int max_left[10000];
 int max_right[10000];
 max_left[0]=array[0];
 int mx = max_left[0];
// find max element from left
 mfor(i,n){
  if(array[i]>mx)
  {
   max_left[i] = array[i];
   mx = array[i];
  }
  else
  max_left[i] = mx; 
 }
// find max element from right
 mx = max_right[n-1]=array[n-1];
 mfor(i,n){
 if(array[n-1-i]>mx){ 
  mx = array[n-1-i];
  max_right[n-1-i]=array[n-1-i];
 }
 else
 max_right[n-1-i]= mx; 
 }

 int ans=0;
 //calculate answer
 mfor(i,n)
  ans+= min(max_right[i],max_left[i])-array[i]; 


 cout<<ans<<endl;


 return 0;
}
answer Dec 17, 2015 by Shivaranjini
what is role of following statement
 #include<iostream>
using namespace std;
 #define mfor(i,n) for(int i=0;i<n;i++)
briefly explain.....
0 votes

enter image description here

See the image, An element of array can store water if there are higher bars on left and right. We can find amount of water to be stored in every element by finding the heights of bars on left and right sides. The idea is to compute amount of water that can be stored in every element of array. For example, consider the array {3, 0, 0, 2, 0, 4}, we can store two units of water at indexes 1 and 2, and one unit of water at index 2.

A Simple Solution is to traverse every array element and find the highest bars on left and right sides. Take the smaller of two heights. The difference between smaller height and height of current element is the amount of water that can be stored in this array element. Time complexity of this solution is O(n2).

An Efficient Solution is to prre-compute highest bar on left and right of every bar in O(n) time. Then use these pre-computed values to find the amount of water in every array element. Below is C++ implementation of this solution.

// C++ program to find maximum amount of water that can
// be trapped within given set of bars.
#include<bits/stdc++.h>
using namespace std;

int findWater(int arr[], int n)
{
    // left[i] contains height of tallest bar to the
    // left of i'th bar including itself
    int left[n];

    // Right [i] contains height of tallest bar to
    // the right of ith bar including itself
    int right[n];

    // Initialize result
    int water = 0;

    // Fill left array
    left[0] = arr[0];
    for (int i = 1; i < n; i++)
       left[i] = max(left[i-1], arr[i]);

    // Fill right array
    right[n-1] = arr[n-1];
    for (int i = n-2; i >= 0; i--)
       right[i] = max(right[i+1], arr[i]);

    // Calculate the accumulated water element by element
    // consider the amount of water on i'th bar, the
    // amount of water accumulated on this particular
    // bar will be equal to min(left[i], right[i]) - arr[i] .
    for (int i = 0; i < n; i++)
       water += min(left[i],right[i]) - arr[i];

    return water;
}

// Driver program
int main()
{
    int arr[] = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "Maximum water that can be accumulated is "
         << findWater(arr, n);
    return 0;
}

Output:

Maximum water that can be accumulated is 6

Time Complexity: O(n)
Auxiliary Space: O(n)

answer Dec 17, 2015 by Manikandan J
Similar Questions
+5 votes

How to compute modulo power of 10,000 digit number to 10,000 digit number using C language
Eg:-(1234567891111123433434^211222324334343422233)%**********

And how to store and retrieve such a large values

+2 votes

How to find the median of simple linked list and add a node after it? C program would be helpful?

+2 votes

I know of "select()" which works using file descriptors.

However I want similar functionality to "select()" but for a simple function that returns an int.

So suppose, there's "int calculate_magic()" function and I want to allow it to work for 2 seconds, if it takes longer than that I want to move on.

If "calculate_magic()" wrote its answer to a file descriptor I could use "select()" but how to do it for the case I mentioned?

I need something like this for a simple game implementation where the player is allowed a maximum time to make a decision about their next move.
I
was hoping I can get something without having to deal with threads, etc.

...