My Python Solution of O(n) time and O(1) space.


  • 0
    V

    The original idea is based on that how much water can be trapped by one element is decided by:
    Min ( Max(bars_at_left), Max(bars_at_right) ) - height(current_bar).
    But if we know, saying one bar at right (no necessarily be the longest bar at right side) is larger than Max(bars_at_left), there is no need to know what the Max(bars_at_right) is. And it works the same when some bar at left side larger than Max(bars_at_right).
    Here is my code:

    class Solution(object):
        def trap(self, height):
            #space cost o(1)
            left_max = 0
            right_max = 0
            lo,hi = 0,len(height) - 1
            water = 0
            while(hi >= lo):
                if(left_max <= right_max):
                    if (height[lo] < left_max):
                        water += left_max - height[lo]
                    else:
                        left_max = height[lo]
                    lo += 1
                else:
                    if (height[hi] < right_max):
                        water += right_max - height[hi]
                    else:
                        right_max = height[hi]
                    hi -= 1
            return water
    

Log in to reply
 

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