Pattern Recognition Drill
Hard Two Pointers
The Problem
Given n non-negative integers representing an elevation map, compute how much water it can trap.
What approach would you use?
Think about it before scrolling down.
Two pointers from ends. Process the side with smaller max. Water = max - height. O(n) time, O(1) space.
Monotonic stack tracking bars. Pop when current > stack top, compute trapped water. O(n) time, O(n) space.
Common Trap
The prefix/suffix max arrays work but use O(n) space. Two pointers achieve O(1) space.