O(n) time and O(1) space Python code with comments(beats 86.69% run times)


  • 1
    M
    class Solution(object):
       def trap(self,height):
        # your code here
        if (not height) or len(height) == 0:
            return 0
        total = 0
        potential = 0  # the water may or may not be trapped, depending on whether there is going to be an even higher bar to hold it
        tallest = height[0]
        for i in range(1, len(height)):  # scan from left to right
            if tallest <= height[i]:  # the "potential" watter can actually be trapped, add it to total
                total += potential
                potential = 0
                tallest = height[i]
            else:
                potential += tallest - height[i]  # accumulate the "potential" water
        tallest = height[-1]
        potential = 0
        for i in range(len(height) - 2, -1, -1):  # scan from right to left
            if tallest < height[i]:  # case like [2,0,2] has already been taken care of in scanning from left to right
                total += potential
                potential = 0
                tallest = height[i]
            else:
                potential += tallest - height[i]
        return total

Log in to reply
 

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