Trapping Rain Water
Compute how much rain water can be trapped between bars.
Pattern fit
Two pointers work because water on the shorter-side boundary is determined without waiting for a higher bar on the same side once the opposite side is taller.
Key observation
The smaller of leftMax and rightMax determines water at the current side, so move the side with the smaller boundary.
Target complexity
O(n) / O(1)
How to break down the solution cleanly
Two pointers work because water on the shorter-side boundary is determined without waiting for a higher bar on the same side once the opposite side is taller.
The smaller of leftMax and rightMax determines water at the current side, so move the side with the smaller boundary.
Write down what each pointer means before you move them.
Use the current comparison to prove which side can be safely discarded.
Reference implementation
Python# Generic pattern template
# Opposite-direction pointers on a sorted array
left, right = 0, len(nums) - 1
while left < right:
if good(nums[left], nums[right]):
return answer
if should_move_left(nums[left], nums[right]):
left += 1
else:
right -= 1
# Fast/slow pointers
slow = 0
for fast in range(len(nums)):
if keep(nums[fast]):
nums[slow] = nums[fast]
slow += 1
Common pitfalls
Moving the wrong pointer and breaking the boundary proof.
Updating trapped water before refreshing leftMax or rightMax.
Common follow-ups
How does the stack solution compare conceptually?
Why is the smaller boundary enough to decide the current water?
Continue with related problems
Build repeatable depth inside the Two Pointers cluster before moving on.