Requirements
- Input: an array
height[]of non-negative integers representing the elevation map. - Return: the total units of water that can be trapped between the bars after rain.
public int trap(int[] height)
Examples
height = [0,1,0,2,1,0,1,3,2,1,2,1] → 6
height = [4,2,0,3,2,5] → 9
Notes
- Three canonical solutions, in increasing sophistication:
- Precomputed left-max / right-max arrays — O(n) time, O(n) space. Easiest to derive at the whiteboard.
- Two pointers — O(n) time, O(1) space. Walk in from both ends; the side with the smaller max determines the trapped water at the current step.
- Monotonic stack — O(n) time, O(n) space. Process "valleys" as they close; mostly used to motivate the harder "Largest Rectangle in Histogram" follow-up.
- Goldman interviewers typically want you to derive the precomputed-arrays form, then refactor to the two-pointer form. Both should land in the same session.
- Edge cases: arrays shorter than 3 trap 0 water; flat plateaus trap 0; descending-then-ascending shapes are where the off-by-one bugs hide.
Preparation
- Drill the two-pointer derivation on paper: explain why the side with the smaller boundary max is the one to step inward.
- LC 42 is the canonical equivalent and is one of the headline problems on Goldman's tagged LeetCode list — practice it until you can produce both the O(n) space and O(1) space solutions cold.
- Common follow-up: "Trapping Rain Water II" (LC 407, the 2-D version) — be ready to sketch the priority-queue / BFS-from-boundary approach even if you don't fully code it.