_42. Trapping Rain Water.md

42. Trapping Rain Water

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : March 11, 2025

Last updated : March 11, 2025

---

Related Topics : Array, Two Pointers, Dynamic Programming, Stack, Monotonic Stack

Acceptance Rate : 64.36 %

---

Solutions

• h42 v1 heap.py
• h42 v2 two pointer.py

Python

h42 v1 heap.py

class Solution:
    def trap(self, height: List[int]) -> int:
        output = 0

        vals = [(-x, i) for i, x in enumerate(height)]
        heapify(vals)

        left_max = right_max = heappop(vals)[1]
        while vals and (left_max > 0 or right_max < len(height) - 1):
            val, i = heappop(vals)
            val = -val

            if left_max <= i <= right_max :
                continue

            if i <= left_max :
                minn = min(val, height[left_max])
                output += sum(minn - x for x in height[i + 1:left_max])
                left_max = i
            else :
                minn = min(val, height[right_max])
                output += sum(minn - x for x in height[right_max + 1:i])
                right_max = i
                
        return output

h42 v2 two pointer.py

class Solution:
    def trap(self, height: List[int]) -> int:
        left_max = right_max = output = 0 
        left, right = 0, len(height) - 1

        while left < right :
            if height[left] < height[right] :
                output += (left_max := max(left_max, height[left])) - height[left]
                left += 1
            else :
                output += (right_max := max(right_max, height[right])) - height[right]
                right -= 1

        return output