Trapping Rain Water within given set of bars


Find maximum amount of water that can be trapped within given set of bars. Assume width of each bar is 1 unit.

 

For example,

Input: Array containing height of bars {7, 0, 4, 2, 5, 0, 6, 4, 0, 5}

  rain water trapping bars

Maximum amount of water that can be trapped is 25 as shown below (in blue color).

  rain water trapping


 

The idea is to calculate maximum height bar on the left and right of every bar. Then the amount of water that can be stored on top of each bar is equal to minimum among maximum bar to the left and right minus height of current bar.

 
C++ implementation –
 

Download   Run Code

Output:

Maximum amount of water that can be trapped is 25

 
The time complexity of above solution is O(n) and auxiliary space used by the program is O(n).
 


 

O(1) space solution –

 

Download   Run Code

Output:

Maximum amount of water that can be trapped is 25

 
The time complexity of above solution is O(n) and auxiliary space used by the program is O(1).
 

Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
Sort by:   newest | oldest | most voted
Cliff
Guest
Cliff
Here’s another linear-time, constant space solution. Makes two passes, so it’s perhaps not as elegant as solution number 2 above, but it might be more intuitive to some. Walk from left to right, keeping track of max as you go along. Any time the max changes, walk backward to the… Read more »
dann
Guest
dann

I think it needs three passes. What your algorithm return on {1,0,1}?

Tony
Guest
Tony

It would be interesting to see this problem done an a 2 dimensional array.

wpDiscuz