Proficient Level
Implement the trappingRainWaterAmount method that calculates how much rain water can be trapped between bars.
The input contains an elevation array height and its length size. Each value represents the height of a bar.
Your task is to calculate how much rain water can be trapped between the bars after raining.
Water above a position depends on the tallest bar to its left and the tallest bar to its right. For example, the input [0,1,0,2,1,0,1,3,2,1,2,1] can trap 6 units of water.
Example 1
Input
height (int[]) =
[0,1,0,2,1,0,1,3,2,1,2,1]size (int) =
12Returns (int)
6Example 2
Input
height (int[]) =
[4,2,0,3,2,5]size (int) =
6Returns (int)
9Example 3
Input
height (int[]) =
[1,2,3]size (int) =
3Returns (int)
0Use two pointers with running maximum heights from both sides.
The amount of water at a position is limited by the smaller side. If the left maximum is smaller than the right maximum, process the left pointer. Otherwise, process the right pointer.
For each processed bar, add the difference between the current side maximum and the bar height.
Pseudocode:
function trappingRainWaterAmount(height, size):
left = 0
right = size - 1
leftMax = 0
rightMax = 0
water = 0
while left < right:
if height[left] < height[right]:
if height[left] >= leftMax:
leftMax = height[left]
else:
water = water + (leftMax - height[left])
left++
else:
if height[right] >= rightMax:
rightMax = height[right]
else:
water = water + (rightMax - height[right])
right--
return waterReady to test your solutionRun Code checks your solution against the test cases.Shift + Enter to run