Python solution with detailed explanation


  • 0
    G

    Solution

    Trapping Rain Water https://leetcode.com/problems/trapping-rain-water/

    1. At height[i], what is the maximum height from [0, i-1] and [i+1, len(height)-1]? Let us call these heights as max_left and max_right.
    2. What is the water trapped at height[i]?
    • if max_left <= height[i] or max_right <= height[i], then water trapped is 0
    • if max_left > height[i] and max_right > height[i], then water_trap += min(max_left, max_right)-height[i]
    1. You can use linear space and precompute max_right. max_left can be computed as we move left to right.
    class Solution(object):
        def trap(self, height):
            """
            :type height: List[int]
            :rtype: int
            """
            if height == []:
                return 0
            max_right = [-1]*len(height)
            for i in range(len(height)-1, -1, -1):
                max_right[i] = max(height[i], max_right[i+1]) if i < len(height)-1 else height[i]
            water_trap, max_left = 0, height[0]
            for i in range(1, len(height)-1):
                h_left, h_right = max_left, max_right[i+1]
                if h_left > height[i] and h_right > height[i]:
                    water_trap += min(h_left,h_right) - height[i]
                max_left = max(max_left, height[i])
            return water_trap
    

Log in to reply
 

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