Sunday, March 2, 2014

Trapping Rain Water (Java + Python)

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.
For example, 
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.
The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

Solution: DP 
 To calculate the total volume is to calculate volumes can hold at each position.
 To calculate how many volumes can hold at each position is to calculate it's right bound height  and right bound height 
Current position can hold water only at the situation when the low side among both sides higher than the height at current position
If so,  use the lower one minus current height as height to multiply the width 1 is how many volumes can hold at current position
How to calculate the height of both sides for each position? We can apply DP theory to record  highest height bound can get from left to current and highest height bound can get from right to current  
HigehstLeftSideHeight so far from giving example, should be  0,1,1,2,2,2,2,3,3,3,3,3
HighestRightSideHeight so far for given example is 1,2,2,2,3,3,3,3,3,3,3,3
Then loop through giving array for each position to calculate how many volumes can hold there and update the total volume it can hold