O(n) time, O(1) space Python just for fun


  • 1

    I polluted the given arguments so that no extra space is used and no need to track left and right boundary by using two variables.

    class Solution:
        def trapRainWater(self, heights):
            # write your code here
            left = 0
            right = len(heights) - 1
            ans = 0
            while left < right:
                if heights[left] >= heights[right]:
                    ans += max(0, heights[right] - heights[right - 1])
                    heights[right - 1] = max(heights[right], heights[right - 1])
                    right -= 1
                else:
                    ans += max(0, heights[left] - heights[left + 1])
                    heights[left + 1] = max(heights[left], heights[left + 1])
                    left += 1
            return ans
    

  • 0
    S

    Thanks for sharing.

    You don't have to polluted the given list indeed. Simply use 2 variables to track left and right highest points. :-P


Log in to reply
 

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