42. Trapping Rain Water

[fockspaces]

the containing water: (the minimun height of wall from left and right side) - cur_wall height if the value is negative, means the cur_water is higer than the either side, water will flow through that side. so we take 0 for this.

The tricky point is to find out the max height from both side, in simplify our logic, we can maintain the two array in advanced, so we can access the inforamtion without extra operation.

class Solution:
    def trap(self, height: List[int]) -> int:
        n = len(height)
        max_h_from_l, max_h_from_r = [0] * n, [0] * n
        ans = 0
        for i in range(n):
            prev_h = max_h_from_l[i - 1] if i - 1 >= 0 else 0
            max_h_from_l[i] = max(prev_h, height[i])
        for i in reversed(list(range(n))):
            next_h = max_h_from_r[i + 1] if i + 1 < n else 0
            max_h_from_r[i] = max(next_h, height[i])
        for i in range(n):
            left_h = max_h_from_l[i - 1] if i - 1 >= 0 else 0
            right_h = max_h_from_r[i + 1] if i + 1 < n else 0
            h = max(0, min(left_h, right_h) - height[i])
            ans += h
        return ans

[fockspaces]

O(1) solution, too tricky so I'll not diving too deep into it.

The height of water is only determined by the shorter side, so we can update the ans with two pointers, keep operate on current cell, then moving toward by the shorter side

class Solution:
    def trap(self, height: List[int]) -> int:
        n = len(height)
        l, r = 0, n - 1
        left_h, right_h = height[l], height[r]
        ans = 0

        while l < r:
            if left_h <= right_h:
                l += 1
                left_h = max(left_h, height[l])
                ans += left_h - height[l]
            else:
                r -= 1
                right_h = max(right_h, height[r])
                ans += right_h - height[r]
        return ans