42.Trapping Rain Water

Tags: [heap], [two_pointer]

Com: {g}

Link: https://leetcode.com/problems/trapping-rain-water/#/description

Givennnon-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], return6.

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!

Solution: Heap

import heapq

class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        if not height or len(height) < 2:
            return 0

        size = len(height)
        min_heap = [(height[0], 0), (height[-1], size - 1)]
        heapq.heapify(min_heap)
        visited = [False for _ in xrange(size)]
        visited[0] = visited[-1] = True

        amount = 0

        while min_heap:
            border_h, index = heapq.heappop(min_heap)

            # check its neighbors
            for d in (-1, 1):
                i = index + d
                if 0 <= i < size and not visited[i]:
                    if height[i] < border_h:
                        amount += border_h - height[i]
                        height[i] = border_h
                    heapq.heappush(min_heap, (height[i], i))
                    visited[i] = True

        return amount

Revelation:

• Do not forget to put the real borders into visited map.

Note:

• Time complexity = O(n*lg(n/2)) = O(nlgn), the reason why there is (n/2), is because each time we pop up one element from heap, and at most push into two elements, think about there are totally n elements, each time we at least pop up one, at most push two elements, so the max size of heap should be n/2.

Faster Solution: Two Pointer

class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        if not height or len(height) < 2:
            return 0

        size = len(height)
        l = 0
        r = size - 1

        # find left most edge
        while l < r and height[l] <= height[l + 1]:
            l += 1
        # find right most edge
        while l < r and height[r - 1] >= height[r]:
            r -= 1

        amount = 0
        while l < r:
            left = height[l]
            right = height[r]
            if left <= right:
                while l < r and height[l] <= left:
                    amount += left - height[l]
                    l += 1
            else:
                while l < r and height[r] <= right:
                    amount += right - height[r]
                    r -= 1

        return amount

Note:

• Time complexity = O(n), n is the num of elements in height.