Array Sorting Two Pointers
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) = 12
Return:
(int) 6
Example 2
Input:
height (int[]) = [4,2,0,3,2,5]
size (int) = 6
Return:
(int) 9
Example 3
Input:
height (int[]) = [1,2,3]
size (int) = 3
Return:
(int) 0

Use 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 water
Run your code to see the result.