42. Trapping Rain Water (Python)

Related Topic

Stack.

Description

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.

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!

Sample I/O

Example 1

Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

Methodology

To trap the water, for each unit of the elevation map’s width, we can use min(left_bar, right_bar) - the current height to get the current area of the water.

    def trap(self, height: List[int]) -> int:
        if not height: return 0
        size = len(height)
        area = 0
        left_max, right_max = [0] * size, [0] * size
        
        left_max[0] = height[0]
        for i in range(1, size):
            left_max[i] = max(height[i], left_max[i - 1])
            
        right_max[size - 1] = height[size - 1]
        for i in range(size-2, -1, -1):
            right_max[i] = max(height[i], right_max[i + 1])
        
        for i in range(1, size-1):
            area = area + (min(left_max[i], right_max[i]) - height[i])
        return area

BigO

Iterate the elevation map three times so total cost will be O(3n) where n is the width of the elevation map.