Trapping Rain Water LeetCode Solution: 3 Approaches Explained

Trapping Rain Water (#42) is one of the most famous Hard problems on LeetCode — and for good reason. It consistently appears in coding interviews at Google, Amazon, Meta, and Microsoft because it tests whether you can move beyond a naive solution and optimize step by step.

What makes this trapping rain water leetcode problem special is that it has three progressively better solutions, each building on the insight of the last. Interviewers love watching candidates walk through this optimization journey in real time.

In this walkthrough, you will learn all three approaches — brute force, prefix max arrays, and the optimal two-pointer technique. By the end, you will understand not just how each solution works, but why each optimization is possible and how to arrive at it during an interview.

You are given an array of non-negative integers representing an elevation map where the width of each bar is 1. Your task is to compute how much water can be trapped after raining. The water fills the gaps between taller bars, and at each position the water level is determined by the surrounding heights.

The key insight is simple: the water trapped at any single position equals min(maxLeft, maxRight) - height[i]. The water level at each bar is constrained by the shorter of the two tallest walls on either side. If the bar itself is taller than that water level, no water is trapped there.

For example, given heights [0,1,0,2,1,0,1,3,2,1,2,1], the answer is 6 units of water. Visualizing this as a bar chart makes the trapped water between the bars immediately clear.

This formula — min(maxLeft, maxRight) - height[i] — is the foundation for every solution. The three approaches differ only in how efficiently they compute maxLeft and maxRight for each position.

The most straightforward leetcode 42 solution applies the formula directly. For each bar at index i, scan left to find the maximum height, scan right to find the maximum height, then compute the trapped water at that position.

This approach is correct and easy to understand, but it repeats a lot of work. For each of the n positions, you scan up to n elements left and n elements right. That gives you O(n^2) time complexity with O(1) extra space.

In an interview, start here. It shows you understand the problem completely and can translate the water formula into working code. Then explain why it is slow — the repeated scanning — and use that as motivation for the next optimization.

The brute force repeats work because it recomputes maxLeft and maxRight from scratch for every position. The fix is precomputation. Build a leftMax array where leftMax[i] stores the tallest bar from index 0 to i, and a rightMax array where rightMax[i] stores the tallest bar from index i to n-1.

Building each array takes a single O(n) pass. leftMax is built left-to-right, and rightMax is built right-to-left. Once you have both arrays, computing the water at each position is a single O(n) scan using the same formula: water += min(leftMax[i], rightMax[i]) - height[i].

This is the "aha" moment in the trapping rain water explained walkthrough. You have eliminated the nested loop entirely. Time drops from O(n^2) to O(n), but you now use O(n) extra space for the two prefix arrays.

Many candidates stop here in interviews and it is a perfectly acceptable solution. But if the interviewer asks "can you do it in O(1) space?", you need the two-pointer approach.

The trapping rain water two pointers approach is the interview gold standard. It achieves O(n) time with O(1) space by recognizing that you do not need the entire prefix arrays — you only need the running maximums from each side.

Place a left pointer at the start and a right pointer at the end. Maintain two variables: maxLeft (the tallest bar seen from the left) and maxRight (the tallest bar seen from the right). At each step, move the pointer that has the smaller max value.

Why does this work? The water at any position depends on min(maxLeft, maxRight). If maxLeft < maxRight, then the left side is the bottleneck and you know the water at the left pointer is determined by maxLeft — regardless of what the right side looks like further in. So you can safely process the left pointer and advance it.

This is why the trapping rain water O(1) space solution is so elegant. By always processing the side with the smaller constraint, you guarantee you have enough information to compute the exact water at that position without needing the full prefix array.

Before submitting, make sure your solution handles these edge cases. An empty array or an array with fewer than 3 elements cannot trap any water — return 0. An array with all the same heights traps nothing. A strictly increasing or strictly decreasing array also traps zero water because there is no "bowl" to hold it.

A common follow-up is comparing Trapping Rain Water (#42) with Container With Most Water (#11). While both involve bars and water, they solve fundamentally different problems. Problem #42 fills water between all bars simultaneously, while #11 finds the single pair of bars that forms the largest rectangle.

Advanced follow-ups include the 3D version of trapping rain water (LeetCode #407, Trapping Rain Water II) which uses a min-heap BFS approach on a 2D grid, and variations where bars have different widths. These test whether your understanding of the core principle extends beyond the original problem.

This problem is a masterclass in optimization thinking. You start with a correct but slow brute force, identify the repeated work (scanning for maxes), eliminate it with prefix arrays, then realize you can replace those arrays with two running variables and a two-pointer scan. Each step has a clear "why."

The prefix max technique is not unique to this problem — it appears in problems like Product of Array Except Self (#238), Best Time to Buy and Sell Stock (#121), and any scenario where you need running aggregates from both directions. Recognizing this pattern unlocks a whole category of problems.

The two-pointer insight — that processing from the constrained side gives you enough information — also applies broadly. Problems like Container With Most Water (#11) and Valid Palindrome (#125) use similar reasoning. When you master these patterns through spaced repetition with YeetCode, you stop memorizing solutions and start recognizing the underlying technique.

If you can walk an interviewer through all three approaches to Trapping Rain Water, explaining the time-space tradeoffs at each step, you have demonstrated exactly the kind of systematic problem-solving that top tech companies are looking for.