LC 0042 [H] Trapping Rain Water - ALawliet/algorithms GitHub Wiki

• 2 pointers to track tallest left and tallest right
• if tallest left is less than tallest right, water is trapped on left so add volume from tallest left - current left else tallest right - current right at least 0

---

class Solution:
    def trap(self, height: List[int]) -> int:
        l, r = 0, len(height) - 1
        l_max = r_max = 0
        vol = 0
        while l < r:
            l_max = max(l_max, height[l])
            r_max = max(r_max, height[r])
            if l_max < r_max:
                vol += max(l_max - height[l], 0)
                l += 1
            else:
                vol += max(r_max - height[r], 0)
                r -= 1
        return vol