Trapping Rain Water

Given non-negative heights of bars, compute the total volume of water that can be trapped between them after rain. The single most recurring Goldman coding question — featured on its own tagged LeetCode list. 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.