42.Trapping_Rain_Water(Hard).md

42. Trapping Rain Water (Hard)

Date and Time: Jul 8, 2024, 19:01 (EST)

Link: https://leetcode.com/problems/trapping-rain-water/

Question:

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Example 1:

Input: height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]

Output: 6

Explanation: The above elevation map (black section) is represented by array [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]. In this case, 6 units of rain water (blue section) are being trapped.

Example 2:

Input: height = [4, 2, 0, 3, 2, 5]

Output: 9

DP Solution:

The dp solution saves the left, right for each i in height. left finds the maximum from i's left, right finds the maximum from i's right. Then finally we find min(left[i], right[i]) and subtract with height[i], if the subtraction < 0, we don't add it to res, if subtraction > 0, we add it to res.

class Solution:
    def trap(self, height: List[int]) -> int:
        left, right = [0] * len(height), [0] * len(height)
        res = 0
        tmp = height[0]
        for i in range(len(height)):
            left[i] = tmp
            tmp = max(tmp, height[i])
        tmp = height[len(height)-1]
        for i in range(len(height)-1, -1, -1):
            right[i] = tmp
            tmp = max(tmp, height[i])
        for i in range(len(height)):
            if min(left[i], right[i]) - height[i] > 0:
                res += min(left[i], right[i]) - height[i]
        return res

height: [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
left:   [0, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3]
right:  [3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 0]
res:    [0, 0, 1, 0, 1, 2, 1, 0, 0, 1, 0, 0]

Time Complexity: $O(n)$
Space Complexity: $O(n)$

Two Pointers Solution:

The two pointers solution is used to make sure the l, r pointers are the same, if they are not equal, we either increment l when maxleft <= maxright or decrement r when maxleft > maxright. Then we add res by either maxleft - height[l] or maxright - height[r].

Notice that we update maxleft = max(maxleft, height[l]), so res += maxleft - height[l] will either be 0 (If height[l+1] updates maxleft) or the amount of water can be trapped in that index i (maxleft still larger than height[l+1]). Same for maxright.

class Solution:
    def trap(self, height: List[int]) -> int:
        # l, r ptr, advance l ptr if maxLeft <= maxRight
        # Update maxLeft and maxRigth accordingly
        # update res by maxLeft - height[l] or maxRight - height[r]

        # TC: O(n), SC: O(1)
        l, r = 0, len(height)-1
        maxLeft, maxRight = height[l], height[r]
        res = 0
        while l < r:
            if maxLeft <= maxRight:
                l += 1
                maxLeft = max(maxLeft, height[l])
                res += maxLeft - height[l]
            else:
                r -= 1
                maxRight = max(maxRight, height[r])
                res += maxRight - height[r]
        
        return res

Time Complexity: $O(n)$
Space Complexity: $O(1)$

Similar to [11. Contain With Most Water].