Skip to main content

Trapping Rain Water

Question​

Given an array of non-negative integers representing an elevation map, how many units of trapped rain water can be contained within the elevation map?

Example 1
Input: [0,1,0,2,1,0,1,3,2,1,2,1]

Output: 6

Solution​

all//Trapping Rain Water.py


def trapping_rain_water(arr):

    # total amount of water to be stored in the array
    result = 0

    # maximum height of the left and right wall
    left_max = 0
    right_max = 0

    # traverse array from left to right
    l = 0
    r = len(arr) - 1

    while l < r:

        if arr[l] < arr[r]:
            if arr[l] > left_max:

                # update the maximum height of the left wall
                left_max = arr[l]
            else:

                # water is stored in the current position
                result += left_max - arr[l]
            l += 1

        else:
            if arr[r] > right_max:

                # update the maximum height of the right wall
                right_max = arr[r]
            else:

                # water is stored in the current position
                result += right_max - arr[r]
            r -= 1

    # return the total amount of water stored
    return result

# Driver Code
arr = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
print(trapping_rain_water(arr))