Trapping Rain Water LeetCode 42 Deep Dive

LeetCode 42 gives you an array of non-negative integers where each element represents the height of a bar in a histogram. After it rains, water settles between the bars. Your task is to compute the total volume of water that can be trapped.

The amount of water at each position i is determined by the tallest bars on both sides: water[i] = min(maxLeft[i], maxRight[i]) - height[i]. If this value is negative (the bar is taller than one of the surrounding maxes), no water is trapped there. The total answer is the sum of water[i] across all positions.

This problem has three canonical solutions with different time and space tradeoffs. Prefix max arrays are the most intuitive. Two pointers reduce space to O(1). A monotonic stack handles the problem in a third way that extends to related problems like largest rectangle in histogram.

The prefix max approach precomputes two auxiliary arrays. leftMax[i] holds the maximum bar height from index 0 through i (inclusive). rightMax[i] holds the maximum bar height from index i through n-1 (inclusive). Building both arrays takes O(n) time and O(n) space.

Once you have leftMax and rightMax, a single pass computes the answer: for each index i, add max(0, min(leftMax[i], rightMax[i]) - height[i]) to a running total. This formulation ensures you never add a negative contribution. The total pass is O(n), so the overall complexity is O(n) time and O(n) space.

This approach is the clearest to reason about and the easiest to implement without bugs. It directly encodes the physical intuition: water at position i is bounded by the shorter of the tallest walls on each side.

The two-pointer approach eliminates the need for the leftMax and rightMax arrays. Use two pointers, left starting at 0 and right starting at n-1, and track the running maximum seen from each side: leftMax and rightMax. Process the side with the smaller current max.

If leftMax is less than or equal to rightMax, you know that the water at the left pointer is fully determined by leftMax — because even if the right side has a taller bar than rightMax, it can only increase the minimum and thus not reduce the water. Add leftMax - height[left] to the total and advance left. Otherwise, do the symmetric operation on the right side.

This gives O(n) time and O(1) space. It is the gold-standard answer in interviews: same time complexity as prefix arrays but with constant space. The key insight is that you never need the exact maximum on the far side — only the guarantee that it is at least as tall as the current side.

The correctness of the two-pointer approach rests on a key invariant: when leftMax < rightMax, the water at the left pointer is exactly leftMax - height[left]. Why? Because the actual maximum on the right side is >= rightMax >= leftMax. The minimum of the two sides is leftMax, so water is determined by leftMax regardless of what exact maximum lies to the right.

You process the shorter side because it is the side where the water level is fully determined. The taller side may still grow as the pointers converge, but that does not affect the water computation on the shorter side. This greedy choice is safe and leads to an optimal solution.

The two-pointer approach is essentially computing the same values as the prefix arrays, but lazily and in a single pass. At each step, it knows enough about the current position to commit to the correct water value without needing to look ahead.

The monotonic stack approach maintains a stack of indices in decreasing order of height. Iterate through the array left to right. When you encounter a bar taller than the bar at the top of the stack, you have found a "container" — pop the stack and compute the water trapped in the horizontal layer between the popped bar, the current bar, and the new stack top.

After popping an index mid, if the stack is non-empty, the trapped water for this layer is: width = (current index - stack.top - 1), bounded_height = min(height[current], height[stack.top]) - height[mid], contribution = width * bounded_height. Sum these contributions as you continue popping while the current bar remains taller than the stack top.

The monotonic stack processes water horizontally, layer by layer, rather than vertically column by column like the prefix-max and two-pointer methods. This makes it useful for understanding how water fills in terraced or step-shaped histograms. Time complexity is O(n) amortized since each index is pushed and popped at most once; space is O(n) in the worst case.

In Python, the prefix max approach is straightforward: compute leftMax and rightMax with two list comprehensions or forward/backward passes, then zip them with the heights and sum. The two-pointer version is equally clean — a while loop with two integer variables for the running maxes and two pointer indices, no extra arrays needed.

In Java, both approaches use the same logic. The two-pointer implementation is particularly compact: a single while loop with four integer variables (left, right, leftMax, rightMax) and a running total. There is no overflow risk here since all heights are bounded by 10^5 and the array length by 2*10^4, so the maximum answer fits easily in a 32-bit int.

The two-pointer approach is the interview gold standard: O(n) time O(1) space and short enough to write in under 10 lines. The monotonic stack is O(n) time O(n) space and useful when the interviewer asks for an approach that processes water horizontally. The prefix arrays approach is O(n) time O(n) space and the best for explaining the intuition step by step.

Container With Most Water (LeetCode 11) is a close relative — also an array of heights with two pointers, but it is a maximization problem rather than a total-sum problem. The greedy choice is different: always move the shorter pointer inward because it is the limiting factor for water width times height.

Largest Rectangle in Histogram (LeetCode 84) uses a monotonic stack in a very similar way — maintain a stack of bars in increasing height order, and when a shorter bar arrives, pop and compute the rectangle area. Understanding the monotonic stack on Trapping Rain Water makes Largest Rectangle in Histogram significantly more approachable.

Trapping Rain Water II (LeetCode 407) extends the problem to a 3D grid and requires a min-heap (priority queue) instead of a simple stack or two pointers. The Two Sum and 4Sum family uses two pointers in a completely different context — exact target matching rather than area computation — but the pointer-movement intuition transfers.