Trapping Rain Water

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


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.


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