42 Trapping Rain Water

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.

For example,

Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

The Idea: First we have to understand details about the nature of the problem. The first question we have to answer is: when does a 'tower' was water on top of it? This is only true when their exists a left tower and a right tower that have a greater height that it. Gravity would otherwise flush the water down either end. The second question is: how much water can be stored on top of a tower? The answer to that is the min(maxLeftTower, maxRightTower) - currentTower. We are only interested in the minimum because the amount of water that can be stored will at most be the height of the shortest tower. Then subtract the height of the current tower because it serves as an offset from the floor or ground zero.

We can create a hash table that stores the maxLeftand maxRighttower locations. If there doesn't exist a tower with a greater height, we denote it with -1 (these are include in the ends of the array).

Complexity: O(3n) time and O(2n) extra space

class Solution:
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """

        size = len(height)
        if not height:
            return 0

        max_right = {size - 1: -1}
        max_left = {0: -1}
        cur_max = height[size - 1]

        for i in range(len(height) - 2, -1, -1):
            if height[i] > cur_max:
                cur_max = height[i]
                max_right[i] = -1
            else:
                max_right[i] = cur_max

        cur_max = height[0]
        for i in range(0, size):
            if height[i] > cur_max:
                cur_max = height[i]
                max_left[i] = -1
            else:
                max_left[i] = cur_max

        return sum([min(max_right[i], max_left[i]) - height[i]
                    for i in range(0, size) if max_right[i] != -1 and max_left[i] != -1])

Previous41 First Missing Positive Next43 Multiply Strings

Last updated 5 years ago

class Solution: def trap(self, height): """ :type height: List[int] :rtype: int """ size = len(height) if not height: return 0 max_right = {size - 1: -1} max_left = {0: -1} cur_max = height[size - 1] for i in range(len(height) - 2, -1, -1): if height[i] > cur_max: cur_max = height[i] max_right[i] = -1 else: max_right[i] = cur_max cur_max = height[0] for i in range(0, size): if height[i] > cur_max: cur_max = height[i] max_left[i] = -1 else: max_left[i] = cur_max return sum([min(max_right[i], max_left[i]) - height[i] for i in range(0, size) if max_right[i] != -1 and max_left[i] != -1])