Day 9 of 250: LeetCode 42 Trapping Rain Water | Prefix Max Array Approach Explained

Coming Off Yesterday: From Tracking One Minimum to Tracking Two Boundaries

On Day 8, we solved Best Time to Buy and Sell Stock by carrying forward a single value: the minimum price seen so far. At every step, we asked "what is the best context I could have arrived at this index with?" and the answer was one number.

Today we face a harder version of that same question. At every index in an elevation map, we need to know two things: the tallest bar anywhere to its left, and the tallest bar anywhere to its right. Water can only pool between walls, and the water level is always limited by the shorter of the two walls. Neither value can be computed in a single forward scan. One requires looking left; the other requires looking right.

So we do both. We build two arrays, one from the left and one from the right, then combine them. That three-phase approach is the heart of today's solution.

Day 9 is LeetCode 42: Trapping Rain Water. It is tagged Hard, and it earns that label not because the code is complicated but because the insight requires you to think about a position in terms of its global context, not its immediate neighbors. This is one of the most frequently asked hard problems in technical interviews at every major company.

Problem Statement

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Example 1:

Input:  height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
Output: 6

Example 2:

Input:  height = [4, 2, 0, 3, 2, 5]
Output: 9

Constraints:

• 1 <= height.length <= 2 × 10^4
• 0 <= height[i] <= 10^5

The Core Insight: Water Is Trapped by Boundaries, Not Neighbors

Here is the single observation that unlocks this problem: the amount of water sitting on top of any bar depends entirely on the tallest bars to its left and right, not on anything adjacent to it.

Think about why. Water fills up to the level of the shortest surrounding wall. If the tallest bar to your left is height 2 and the tallest bar to your right is height 3, water can fill up to height 2 above the floor at your position. Anything above height 2 would spill over the shorter left wall. If your own bar has height 1, the water sitting on top of you is min(2, 3) - 1 = 1. If your bar has height 2, it is min(2, 3) - 2 = 0. No water pools on a bar that is already as tall as its shortest boundary.

This gives us the formula for every index:

water[i] = min(maxLeft[i], maxRight[i]) - height[i]

Where maxLeft[i] is the tallest bar from index 0 to i (inclusive) and maxRight[i] is the tallest bar from index n-1 to i (inclusive). The total trapped water is the sum of water[i] across all indices.

The naive approach loops over every index and scans left and right to find the max on each side. That is O(n) work per index and O(n^2) total, which times out on large inputs. Precomputing maxLeft and maxRight in separate passes reduces the per-index cost to O(1), bringing the whole solution to O(n).

First Instincts vs. Correct Thinking

The first instinct is to process each index independently:

// Brute force: O(n^2) time, O(1) space
var trap = function(height) {
    let total = 0;
    for (let i = 0; i < height.length; i++) {
        let left = 0, right = 0;
        for (let j = 0; j <= i; j++) left = Math.max(left, height[j]);
        for (let j = i; j < height.length; j++) right = Math.max(right, height[j]);
        total += Math.min(left, right) - height[i];
    }
    return total;
};

This is correct. For every index, it scans left to find the max and right to find the max, then applies the formula. But the inner loops each run up to O(n) times, and we run them for every index, making the total cost O(n^2).

The mental shift is to notice that those inner scans are doing redundant work. The max height from the left at index i is just the max height from the left at index i - 1, updated with height[i]. We are recomputing the same running maximum from scratch every time when we could just carry it forward. That realization turns O(n^2) into three O(n) passes.

Understanding the Approach

We process the problem in three distinct phases, each making one pass through the array.

In the first phase, we build left[], a prefix max array. left[i] stores the maximum height encountered from index 0 through index i. We scan left to right, carrying forward the running maximum. This array answers the question: "What is the tallest wall to my left (including my own height) at every position?"

In the second phase, we build right[], a suffix max array. right[i] stores the maximum height encountered from index n-1 through index i. We scan right to left, carrying forward a running maximum in the other direction. This array answers the question: "What is the tallest wall to my right (including my own height) at every position?"

In the third phase, we loop through every index and apply the formula: min(left[i], right[i]) - height[i]. We add the result to a running total. If the formula ever yields a negative number, it means height[i] is taller than one of its boundaries, which cannot hold water. But since both left[i] and right[i] include height[i] itself in their maximums, the formula always yields at least 0. No clamping is needed.

Deep Dry Run: Every Step Explained

We will trace through height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1] completely.

Input reference:

height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
index  =  0  1  2  3  4  5  6  7  8  9 10 11

Phase 1: Build the Left Prefix Max Array

We start with left[0] = height[0] = 0 and move rightward, taking the max of the previous value and the current height.

i = 0 : left[0] = height[0]              = 0
i = 1 : left[1] = max(left[0], height[1]) = max(0, 1) = 1
i = 2 : left[2] = max(left[1], height[2]) = max(1, 0) = 1
i = 3 : left[3] = max(left[2], height[3]) = max(1, 2) = 2
i = 4 : left[4] = max(left[3], height[4]) = max(2, 1) = 2
i = 5 : left[5] = max(left[4], height[5]) = max(2, 0) = 2
i = 6 : left[6] = max(left[5], height[6]) = max(2, 1) = 2
i = 7 : left[7] = max(left[6], height[7]) = max(2, 3) = 3
i = 8 : left[8] = max(left[7], height[8]) = max(3, 2) = 3
i = 9 : left[9] = max(left[8], height[9]) = max(3, 1) = 3
i =10 : left[10]= max(left[9], height[10])= max(3, 2) = 3
i =11 : left[11]= max(left[10],height[11])= max(3, 1) = 3

left = [0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3]

Each value tells us the tallest bar from the start of the array up to and including that index.

Phase 2: Build the Right Suffix Max Array

We start with right[11] = height[11] = 1 and move leftward.

i =11 : right[11] = height[11]               = 1
i =10 : right[10] = max(right[11],height[10]) = max(1, 2) = 2
i = 9 : right[9]  = max(right[10],height[9])  = max(2, 1) = 2
i = 8 : right[8]  = max(right[9], height[8])  = max(2, 2) = 2
i = 7 : right[7]  = max(right[8], height[7])  = max(2, 3) = 3
i = 6 : right[6]  = max(right[7], height[6])  = max(3, 1) = 3
i = 5 : right[5]  = max(right[6], height[5])  = max(3, 0) = 3
i = 4 : right[4]  = max(right[5], height[4])  = max(3, 1) = 3
i = 3 : right[3]  = max(right[4], height[3])  = max(3, 2) = 3
i = 2 : right[2]  = max(right[3], height[2])  = max(3, 0) = 3
i = 1 : right[1]  = max(right[2], height[1])  = max(3, 1) = 3
i = 0 : right[0]  = max(right[1], height[0])  = max(3, 0) = 3

right = [3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1]

Each value tells us the tallest bar from the end of the array back to and including that index.

Phase 3: Calculate Trapped Water at Every Index

We now have everything we need. For each index: water = min(left[i], right[i]) - height[i].

left  = [0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3]
right = [3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1]
height= [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]

Stepping through each index:

i = 0 : min(0, 3) - 0 = 0 - 0 = 0
         No left boundary at all. No water.

i = 1 : min(1, 3) - 1 = 1 - 1 = 0
         Bar fills up to its own boundary. No water on top.

i = 2 : min(1, 3) - 0 = 1 - 0 = 1
         Left wall = 1, right wall = 3. Water fills to height 1.
         Bar height is 0. Water trapped = 1. ✓

i = 3 : min(2, 3) - 2 = 2 - 2 = 0
         Bar at height 2 fills up to its own left boundary. No water.

i = 4 : min(2, 3) - 1 = 2 - 1 = 1
         Left wall = 2, right wall = 3. Water level = 2.
         Bar height is 1. Water trapped = 1. ✓

i = 5 : min(2, 3) - 0 = 2 - 0 = 2
         Left wall = 2, right wall = 3. Water level = 2.
         Bar height is 0. Water trapped = 2. ✓

i = 6 : min(2, 3) - 1 = 2 - 1 = 1
         Left wall = 2, right wall = 3. Water level = 2.
         Bar height is 1. Water trapped = 1. ✓

i = 7 : min(3, 3) - 3 = 3 - 3 = 0
         This is the tallest bar. No water sits on top.

i = 8 : min(3, 2) - 2 = 2 - 2 = 0
         Right wall limits to 2. Bar is already at 2. No water.

i = 9 : min(3, 2) - 1 = 2 - 1 = 1
         Right wall = 2, left wall = 3. Water level = 2.
         Bar height is 1. Water trapped = 1. ✓

i =10 : min(3, 2) - 2 = 2 - 2 = 0
         Bar fills up to the right boundary. No water.

i =11 : min(3, 1) - 1 = 1 - 1 = 0
         Rightmost bar. Right boundary is itself. No water.

Running total:

0 + 0 + 1 + 0 + 1 + 2 + 1 + 0 + 0 + 1 + 0 + 0 = 6

Final output: 6. Correct.

Bonus trace for Example 2: height = [4, 2, 0, 3, 2, 5]

left  = [4, 4, 4, 4, 4, 5]
right = [5, 5, 5, 5, 5, 5]

i=0: min(4,5)-4 = 0
i=1: min(4,5)-2 = 2
i=2: min(4,5)-0 = 4
i=3: min(4,5)-3 = 1
i=4: min(4,5)-2 = 2
i=5: min(5,5)-5 = 0

Total = 0 + 2 + 4 + 1 + 2 + 0 = 9

Output: 9. Correct.

What Made It Work: The Deeper Why

1. Water at each index depends only on global boundaries. The water level at position i is determined by the tallest bar anywhere to the left and the tallest bar anywhere to the right. Nothing in between matters. A tall bar somewhere in the middle between i and the right boundary does not affect how much water sits at i, because water would fill the valley up to the shorter of the two outermost walls.

2. Prefix max arrays encode global context in O(1) per query. Once left[] and right[] are built, answering "what is the tallest bar to the left of index i?" costs a single array lookup. Without precomputation, that same question costs O(n). Building both arrays takes O(n) time total, and we query them n times each at O(1). That is the computational win.

3. Including height[i] in both left[i] and right[i] prevents negative water values. Both prefix and suffix max arrays include the bar's own height. So left[i] >= height[i] and right[i] >= height[i] always. This guarantees min(left[i], right[i]) - height[i] >= 0 for every index. There is no need for a max-with-zero clamp.

4. The three-phase structure separates concerns cleanly. Building left max, building right max, and computing water are three independent steps. Each one is easy to reason about on its own. This separation also makes the code easy to debug: if your output is wrong, you can inspect left[] and right[] independently before looking at the final sum.

The Code

var trap = function(height) {
    let trap = 0;
    let n = height.length;

    let left = new Array(n);
    let right = new Array(n);

    left[0] = height[0];
    for (let i = 1; i < n; i++) {
        left[i] = Math.max(left[i - 1], height[i]);
    }

    right[n - 1] = height[n - 1];
    for (let i = n - 2; i >= 0; i--) {
        right[i] = Math.max(right[i + 1], height[i]);
    }

    for (let i = 0; i < n; i++) {
        trap += Math.min(left[i], right[i]) - height[i];
    }

    return trap;
};

We declare trap to accumulate the total water and n to avoid repeatedly querying height.length. We then allocate two arrays of length n.

The first loop builds left[] by scanning from index 1 to n - 1, taking the max of the previous entry and the current height. left[0] is initialized to height[0] as the base case since there is nothing to the left of the first element.

The second loop builds right[] by scanning from index n - 2 down to 0, taking the max of the next entry and the current height. right[n-1] is initialized to height[n-1] for the same reason.

The third loop applies the water formula at every index, adding the result to trap. Because left[i] and right[i] both include height[i], the formula is always non-negative and no bounds checking is needed.

Finally we return trap, which now holds the total units of water trapped across the entire elevation map.

Complexity Analysis

Common Mistakes

Mistake 1: Scanning inside the main loop instead of precomputing.

The most common version of this mistake looks like this:

// Wrong: O(n^2) due to inner scans
for (let i = 0; i < height.length; i++) {
    let maxL = Math.max(...height.slice(0, i + 1));
    let maxR = Math.max(...height.slice(i));
    trap += Math.min(maxL, maxR) - height[i];
}

This recomputes the max from scratch for every index. It produces the correct answer but times out on large inputs. Always precompute prefix arrays for problems that require repeated range max or range min queries.

Mistake 2: Forgetting to include height[i] itself in the prefix max.

Some implementations compute left[i] as the max of all bars strictly to the left of i, excluding i itself. This breaks the formula: if height[i] is the tallest bar in the array, left[i] would be smaller than height[i], and the formula would yield a negative water amount.

By including height[i] in both left[i] and right[i], we guarantee the result is always non-negative.

Mistake 3: Initializing the right array loop with the wrong starting index.

A common off-by-one is starting the right array loop at n - 1 instead of n - 2:

// Wrong: overwrites right[n-1] which was already set
right[n - 1] = height[n - 1];
for (let i = n - 1; i >= 0; i--) { // should start at n - 2
    right[i] = Math.max(right[i + 1], height[i]);
}

At i = n - 1, accessing right[i + 1] is out of bounds. The loop must start at i = n - 2.

Mistake 4: Using + instead of accumulating with +=.

In the third loop, forgetting to accumulate with += and instead assigning with = means only the last index's water value is returned. This is a typo-level bug but worth flagging because it produces an answer that looks plausible for certain inputs.

Mistake 5: Confusing this problem with the two-pointer variant.

There is a well-known O(1) space two-pointer approach to this problem. It is correct and more space-efficient. However, it is harder to explain and reason about in an interview setting without practice. The prefix max array approach is easier to derive from first principles and is the recommended starting point when explaining your thought process to an interviewer.

Interview Tips

Step 1: State the formula before anything else. Say: "At any index i, the water trapped is min(maxLeft, maxRight) - height[i]. The water level is bounded by the shorter of the two walls, and anything above the bar's own height is water."

Step 2: Explain why naive is O(n^2) and what changes. Say: "If I scan left and right for every index to find those maxes, that is O(n^2). But the left max at index i is just the left max at i - 1 updated with height[i]. I can precompute both directions in two passes."

Step 3: Walk through building one of the arrays on the example. Trace left[] for the first four elements of [0, 1, 0, 2, ...] before writing any code. This shows you understand the prefix max construction, not just the final formula.

Step 4: Be explicit about why the result is always non-negative. Say: "Both left[i] and right[i] include height[i] itself in the max, so min(left[i], right[i]) is always at least height[i]. The subtraction is always zero or positive."

Step 5: Mention the two-pointer optimization as a follow-up. Say: "If the interviewer wants O(1) space, there is a two-pointer approach where we track maxLeft and maxRight as single variables and process from both ends. But the prefix max approach is easier to derive and explain."

Where This Pattern Appears Next

LeetCode 84: Largest Rectangle in Histogram requires knowing the nearest shorter bar to the left and right of every bar. That is the same "precompute boundaries" instinct applied to a different formula, and it is often the follow-up problem mentioned alongside Trapping Rain Water.

LeetCode 238: Product of Array Except Self builds a prefix product from the left and a suffix product from the right, then combines them. The three-phase structure (left pass, right pass, combine) is structurally identical to today's solution.

LeetCode 11: Container with Most Water is a simpler version of the boundary-thinking intuition. Two walls, the water level is the shorter one, and we use two pointers from both ends. It is a good warmup before tackling today's problem.

LeetCode 407: Trapping Rain Water II extends the same problem to a 2D grid. The boundary-max logic generalizes, but the implementation requires a min-heap. Understanding the 1D version deeply is a prerequisite.

Key Takeaways

Water is trapped by boundaries, not by neighbors. The height of adjacent bars is irrelevant. Only the tallest bar anywhere to the left and the tallest bar anywhere to the right determine how much water a position can hold. Building intuition around global context rather than local context is the skill this problem develops.

Precomputing prefix and suffix arrays converts O(n^2) re-scanning into O(n) lookup. Whenever a problem requires knowing the max, min, sum, or product of all elements before or after each index, prefix and suffix arrays are the right tool. They are one of the most broadly applicable techniques in array problems.

Three-phase solutions are easier to debug than single-phase solutions. By separating the left pass, the right pass, and the combination step, you can inspect intermediate arrays and verify each phase independently. This is a real advantage during both development and interviews.

This problem tests explanation more than code. The formula is short. The code is short. What separates a good answer from a great answer is the ability to explain why the formula is correct, why the ordering of the boundary includes the bar itself, and why no clamping is needed. Invest time in the reasoning, not just the implementation.

Closing

Day 9 is done. We took one of the most intimidating Hard problems on LeetCode and broke it down to three clean passes and one formula. The difficulty was never in the code; it was in seeing that water depends on global walls, not local heights, and that two prefix scans can encode those walls efficiently.

On Day 10, we step into a new problem and a new pattern. The toolkit keeps growing, and the instincts we are building now, prefix arrays, greedy decisions, boundary thinking, will show up repeatedly as we climb toward harder problems.

If the three-phase structure clicked for you, or if you want to see the O(1) space two-pointer variant explained in the same depth, drop a comment below. Your questions shape the direction of future posts.

See you on Day 10. 🚀

This post is part of my 250 Days DSA Challenge, solving one problem every day with a focus on intuition, patterns, and interview ready thinking.