Leetcode 42: Trapping Rain Water

Trapping Rain Water

https://leetcode.com/problems/trapping-rain-water/

 

Naive idea: traverse from left to right. left[i] means the height of the tallest wall on the left of element i (element i itself excluded). right[i] means the height of the tallest wall on the right of element i (element i itself excluded). Then you traverse the `height` list again, determine how high each element can hold water. This idea will take O(N) time and O(N) space.

class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        # Get left[i]
        prev = 0
        left = [0] * len(height)
        for idx, val in enumerate(height):
            left[idx] = prev
            if val > prev:
                prev = val
        
        # Get right[i]
        prev = 0
        right = [0] * len(height)
        for idx, val in enumerate(height[::-1]):
            right[len(height)- 1 - idx] = prev
            if val > prev:
                prev = val
        
        sum = 0
        for i in xrange(0, len(height)):
            diff = min(left[i], right[i]) - height[i]
            if diff > 0:
                sum += diff
        print left
        print right
                
        return sum

 

Another idea takes O(N) time but O(1) space: You have two pointers, left and right. The water that an element can hold is dependent on min height (the tallest wall to its left, the tallest wall to its right).  We use `max_left` and `max_right` to record both heights. You roll out the algorithm from the two ends of the list, every time either moving `left` to one element right or `right` to one element left until they meet somewhere in the central. If the current element has a lower height of the tallest wall to its left than the tallest wall to its right, its vertical water holding amount will be determined by `max_left` as well as the element’s own height. If the current element has a lower height of the tallest wall to its right than the tallest wall to its left, its vertical water holding amount will be determined by `max_right` as well as the element’s own height.

class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        left = 0
        max_left = 0
        right = 0
        max_right = 0
        right = len(height) -1
        
        sum = 0
        while left <= right:
            if max_left < max_right:
                if height[left] > max_left:
                    max_left = height[left]
                else:
                    sum += max_left - height[left]
                left += 1
            else:
                if height[right] > max_right:
                    max_right = height[right]
                else:
                     sum += max_right - height[right]
                right -= 1

        return sum