0042.Trapping Rain Water

• Link: 42. Trapping Rain Water - Hard
• Track: NeetCode150

Question

Restate the problem

• Given an integer array, means the bar heights
• The water level is determined by min(left_max, right_max)
• max(0, min(highest_left, highest_right) - height[i])
• Return the total trapped water

Edge Case

• [2,0,2] → return 2
• Too short to trap water: n < 3 → return 0

---

Method	Approach	Time Complexity	Space Complexity
Method 1 ⭐	Two Pointers	$O(n)$	$O(1)$

Method 1 - Two Pointers

Key Idea: Keep left/right max boundaries; move the pointer with the smaller boundary because that side determines how much water can be trapped.

Approach

• Use two pointers: left = 0, right = n - 1
• Maintain two running maximum boundaries:
  • left_max: maximum height seen so far from the left
  • right_max: maximum height seen so far from the right
• While left <= right:
  • If left_max <= right_max, the left side is the limiting boundary, so water at left is:
    • max(left_max - height[left], 0)
    • Update left_max = max(left_max, height[left])
    • Move left += 1
  • Else, the right side is the limiting boundary, so water at right is:
    • max(right_max - height[right], 0)
    • Update right_max = max(right_max, height[right])
    • Move right -= 1
• Accumulate all trapped water and return water

Why it works

The smaller boundary determines the water level, so we can safely process the side with smaller max.

Complexity

• Time complexity: $O(n)$
• Space complexity: $O(1)$

Code

class Solution:
    def trap(self, height: List[int]) -> int:
        left, right = 0, len(height) - 1
        left_max = right_max = 0
        water = 0
 
        while left <= right:
            if left_max <= right_max:
                left_max = max(left_max, height[left])
                water += left_max - height[left]
                left += 1
            else:
                right_max = max(right_max, height[right])
                water += right_max - height[right]
                right -= 1
 
        return water

---

Mistake

• Initial left_max and right_max, confusing current height with boundary max