Trapping Rain Water

Problem Id: 42 Difficulty: Hard Tag: Array Tag: Two Pointers Tag: Stack


Intuition

We could use an additional array to store the heightest from right. And the rain would be trapped in each position should be limited by the left heighest and the right heighest.

Solution


class Solution:
    def trap(self, height: List[int]) -> int:
        n = len(height)
        height_from_right = height[:]
        for i in range(n - 2, -1, -1):
            height_from_right[i] = max(height_from_right[i + 1], height_from_right[i])
        height_from_left = 0
        water = 0
        for i in range(n):
            height_from_left = max(height_from_left, height[i])
            water += min(height_from_left, height_from_right[i]) - height[i]
        return water