Core Insight Use ordering or symmetry to decide which boundary can move without discarding a valid answer.
Common Pitfall Move the pointer justified by the comparison; moving both can skip a valid pair.
Description
Compute how much water it is able to trap after raining.
Constraints
- Time Complexity:
O(n) - Space Complexity:
O(1)
Tags
arraytwo-pointersdynamic-programmingstack
Implementation Plan Translate the invariant into these small, testable moves.
- Place pointers at the relevant boundaries.
- Evaluate the pair or window.
- Use the comparison to move exactly one boundary.
- Stop when the pointers cross or the target is found.
def trap(height):
if not height: return 0
l, r = 0, len(height) - 1
leftMax, rightMax = height[l], height[r]
res = 0
while l < r:
if leftMax < rightMax:
l += 1
leftMax = max(leftMax, height[l])
res += leftMax - height[l]
else:
r -= 1
rightMax = max(rightMax, height[r])
res += rightMax - height[r]
return res