Trapping Rain Water

Problem

Given elevation heights, compute how many units of water are trapped between the bars after raining.

Use two pointers from both ends while maintaining the maximum height seen on each side; the lower side determines the water above the current bar. Return 0 for empty or strictly monotonic input.

Hint

Water above a bar equals min(left_max, right_max) - height, and the smaller side is always safe to settle.

Test cases

case 1

in: [[0,1,0,2,1,0,1,3,2,1,2,1]]

expected: 6

case 2

in: [[]]

expected: 0

case 3

in: [[1,2,3]]

expected: 0

case 4

in: [[3,2,1]]

expected: 0

case 5

in: [[4,2,0,3,2,5]]

expected: 9

Starter codePython

def trap(height):
    # Your code here
    pass

5 test cases · run your code against them in the editor