Python code in O(n)


  • 0
    H
    class Solution(object):
        def trap(self, height):
            """
            :type height: List[int]
            :rtype: int
            """
            n = len(height)
            if n == 0:
                return 0
            total = 0
            # in order to fullfill O(n), we first record the max of left part and right part at each position
            max_left, max_right = [0]*n, [0]*n  # we would like max_left[i]=max(height[:i+1]) and max_right[i]=max(height[i:]) 
            max_left[0], max_right[n-1] = height[0], height[n-1]
            # traverse the list and fill max_left and max_right
            for i in range(1, n, 1):
                max_left[i], max_right[n-1-i] = max(height[i], max_left[i-1]), max(height[n-1-i], max_right[n-i])
            # traverse the list and accumulate water at each position
            for i in range(n):
                total += min(max_left[i], max_right[i]) - height[i]
            return total
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.