Ace Trapping Rain Water: LeetCode Prep: A Complete Guide

You just got that email from Google, huh? Or maybe it's Meta, Amazon, Apple—doesn’t matter. The first thing you're probably thinking about is that dreaded LeetCode grind. And if you're like most folks, you've already stumbled across "Trapping Rain Water." It's a classic for a reason: it looks deceptively simple, then it kicks your ass. But you know what? It's also an incredible barometer for how you think, how you optimize, and how you approach problems beyond the trivial. Mastering trapping rain water isn't just about getting that one question right; it’s about internalizing patterns that pop up everywhere.

Why "Trapping Rain Water" Matters So Much

This problem isn't just some random brain-teaser. It's a foundational problem that tests your understanding of arrays, pointers, and dynamic programming – without explicitly asking for DP. It’s a multi-stage problem, meaning there are several viable approaches, each with increasing efficiency. An interviewer isn't just looking for an answer; they're gauging your ability to iterate, to start simple, and then to optimize. If you can clearly articulate the trade-offs between, say, a brute-force approach and a two-pointer solution, you're already miles ahead. It shows you think like an engineer, not just a code-monkey.

Think about it: how often do you need to find maximums or minimums within a range, or track state from both ends of a sequence? All the time. Network routing, stock price analysis, even optimizing database queries—they all touch on similar concepts. Trapping Rain Water forces you to think about local maximums and how they interact to define global capacity. It's a fantastic proxy for problems you'll actually face, just abstracted.

The Brute-Force Mindset: Where to Start

Alright, you're staring at an array of non-negative integers representing an elevation map. Each bar has a width of 1. You need to compute how much water it can trap after raining. If you're stuck, the absolute first step is always to simulate or brute-force. Don't worry about efficiency yet. Just get some solution on paper.

For each bar i, what determines how much water it can hold above it? It's limited by the shortest of the tallest bar to its left and the tallest bar to its right. So, for each i, you'd need to:

1. Find max_left_height: Iterate from 0 to i-1 to find the maximum height.
2. Find max_right_height: Iterate from i+1 to n-1 to find the maximum height.
3. Calculate min(max_left_height, max_right_height). This is the effective "wall" height for bar i.
4. If min(max_left_height, max_right_height) > height[i], then water_trapped_at_i = min(max_left_height, max_right_height) - height[i]. Otherwise, it's 0.
5. Add water_trapped_at_i to your total.

This approach means for every bar, you're potentially scanning the entire array twice. That's O(N) scans for each of N bars, leading to an O(N^2) time complexity. Your space complexity is O(1) if you don't count the input array. It's not great, but it's a start. This is what you'd walk through with an interviewer first, demonstrating you understand the problem before diving into optimizations. Don't skip this step; it shows your thought process.

Optimizing with Precomputed Arrays

An O(N^2) solution is rarely what they're looking for as a final answer. So, how do we speed up finding max_left_height and max_right_height for each bar? We can precompute them.

Imagine two new arrays: left_max and right_max.

• left_max[i] stores the maximum height encountered from the beginning of the array up to index i. You can populate this in a single pass from left to right. left_max[0] = height[0], then left_max[i] = max(left_max[i-1], height[i]) for i > 0.
• right_max[i] stores the maximum height encountered from the end of the array down to index i. You populate this in a single pass from right to left. right_max[n-1] = height[n-1], then right_max[i] = max(right_max[i+1], height[i]) for i < n-1.

Once you have these two arrays, you can iterate through the original height array one more time. For each bar i, the water it traps is max(0, min(left_max[i], right_max[i]) - height[i]). Sum these up.

This approach takes three O(N) passes: one for left_max, one for right_max, and one to calculate the total water. Total time complexity is O(N). Now, what about space? You've introduced two auxiliary arrays, each of size N. So, space complexity is O(N). This is a significant improvement over O(N^2) and is often a perfectly acceptable solution in an interview. Don't underestimate the power of dynamic programming (memoization, in this case) to reduce redundant computation. This is a common pattern: if you're repeatedly calculating the same thing for overlapping subproblems, store it.

The Two-Pointer Magic: Space Optimization

Okay, O(N) time and O(N) space is good. But can we do better on space? Yes, with the two-pointer approach—this is the "ace" part. It’s elegant, often surprising, and a favorite among interviewers because it demonstrates a deeper understanding of the problem's constraints.

The core idea here is that the amount of water trapped at any i depends on min(max_left_height, max_right_height). We need to figure out how to update these maximums dynamically without storing entire arrays.

Let's maintain left and right pointers, starting at 0 and n-1 respectively. We also need max_left and max_right variables to keep track of the maximum height seen so far from the left and right sides, respectively.

Here's the crucial insight: if height[left] < height[right], then the water trapped at left (and any point to its left up to max_left) is limited by max_left. Why? Because we know there's at least one bar on the right (height[right]) that is taller than height[left]. So, max_right will eventually be at least height[right], which is greater than height[left]. This means the min(max_left, max_right) for left will definitely be max_left.

Conversely, if height[right] <= height[left], then the water trapped at right is limited by max_right. We know there's at least height[left] on the left side, which is taller than or equal to height[right]. So, max_left will eventually be at least height[left], which is greater than or equal to height[right]. Thus, min(max_left, max_right) for right will be max_right.

Let's walk through the loop:

1. Initialize left = 0, right = n - 1, max_left = 0, max_right = 0, total_water = 0.
2. While left < right:
   • If height[left] < height[right]:
     • If height[left] >= max_left: Update max_left = height[left] (no water trapped, this is a new wall).
     • Else (height[left] < max_left): water_trapped = max_left - height[left]. Add to total_water.
     • Increment left.
   • Else (height[right] <= height[left]):
     • If height[right] >= max_right: Update max_right = height[right].
     • Else (height[right] < max_right): water_trapped = max_right - height[right]. Add to total_water.
     • Decrement right.

This single pass processes each element exactly once. Time complexity is O(N). Crucially, space complexity is O(1) because we're only using a few variables, not auxiliary arrays. This is often the optimal solution for Trapping Rain Water, and what interviewers are usually fishing for. If you can explain this logically and code it cleanly, you've shown mastery.

The Stack Approach: Another O(N) Time, O(N) Space Option

While the two-pointer method is often preferred for its O(1) space, the stack approach is also a valid and sometimes more intuitive way to solve this. It's particularly useful for problems involving "next greater element" or "previous smaller element" type scenarios.

Here’s how it works: You iterate through the height array, maintaining a monotonic decreasing stack of indices.

1. Initialize an empty stack and total_water = 0.
2. Iterate i from 0 to n-1:
   • While the stack is not empty and height[i] is greater than height[stack.peek()]:
     • Pop top_index = stack.pop(). This is a bar that can potentially hold water.
     • If the stack is now empty, it means there's no left boundary for this top_index bar, so no water can be trapped. Break.
     • left_boundary_index = stack.peek().
     • distance = i - left_boundary_index - 1. This is the width of the "well."
     • bounded_height = min(height[i], height[left_boundary_index]) - height[top_index]. This is the effective height of water trapped (limited by the shorter of the two boundaries, minus the bar itself).
     • total_water += distance * bounded_height.
   • Push i onto the stack.

This approach also runs in O(N) time. Each element is pushed and popped from the stack at most once. The space complexity is O(N) in the worst case (e.g., a strictly decreasing array where all elements are pushed onto the stack). It's a solid alternative, and sometimes, depending on the interviewer's style or your personal preference, it feels more natural to reason about. The key is understanding when a stack is useful for maintaining "context" of previous elements.

Common Pitfalls and How to Avoid Them

• Off-by-One Errors: This is classic. When calculating distances or indices, especially with two pointers or stacks, double-check your i - left_boundary_index - 1 type calculations. Trace with a small example.
• Edge Cases: What about an array with 0, 1, or 2 elements? What if the array is [0,0,0,0] or [4,2,0,3,2,5]? What if it's strictly increasing or decreasing? Your code should handle these gracefully. The two-pointer left < right condition generally handles arrays with fewer than 3 elements by simply not running the loop, correctly returning 0.
• Integer Overflow: For this specific problem, the maximum height is 10^5, and the array length is 2 * 10^4. The maximum water trapped could be 2 * 10^4 * 10^5 (roughly, height * width), which is 2 * 10^9. This fits within a standard 32-bit signed integer (max ~2.1 * 10^9). However, if the constraints were higher, you'd need to use long or long long in languages like Java or C++. Always check constraints.
• Premature Optimization: Don't jump straight to the two-pointer solution. Start with the brute force, explain it, then optimize. This shows your thought process and adaptability. Interviewers aren't just looking for a correct answer; they're looking for how you arrive at it.
• Forgetting to Handle max(0, ...): Water can't be negative. If min(left_max, right_max) - height[i] is negative (meaning the current bar is taller than or equal to its boundaries), the water trapped is 0. Explicitly handle this.

When to Use Which Approach

This is where the "it depends on your situation" comes in.

• Brute Force (O(N^2) time, O(1) space): Use this to brainstorm and get a basic understanding. It's your starting point for any difficult problem. Don't spend more than 5-10 minutes on this in an interview unless you're truly stuck.
• Precomputed Arrays (O(N) time, O(N) space): This is a solid, clear, and usually acceptable answer. If you're short on time or struggling with the two-pointers, this is your safe bet. It shows you understand optimization through memoization.
• Two Pointers (O(N) time, O(1) space): This is the ideal solution. It's elegant and demonstrates a deep grasp of the problem's structure. Aim for this one if you have the time and confidence. It's a great "plus" in an interview.
• Stack (O(N) time, O(N) space): A perfectly valid alternative to precomputed arrays. If you're more comfortable with stack-based solutions for similar problems, this might be quicker for you to implement correctly under pressure. It's particularly good if you want to show versatility in data structures.

For a FAANG interview, understanding the O(N) time, O(1) space two-pointer solution is almost a prerequisite. You will be asked to optimize, and optimizing space is often the next step after optimizing time.

Beyond Trapping Rain Water: Related Problems

The concepts you learn from Trapping Rain Water extend to a family of problems. Once you've mastered this one, look into:

• Container With Most Water (LeetCode 11): This is often considered a simpler precursor, also solved effectively with two pointers. It helps build intuition for how two pointers can narrow down a search space.
• Largest Rectangle in Histogram (LeetCode 84): This is significantly harder but uses a monotonic stack in a very similar fashion to one of the Trapping Rain Water solutions. If you nail this, you’re in excellent shape.
• Daily Temperatures (LeetCode 739): Another classic stack problem where you need to find the "next greater element" to the right.
• Next Greater Element I/II (LeetCode 496, 503): More direct applications of the monotonic stack pattern.

Practice these. They reinforce the patterns, making you faster and more confident. The goal isn't just to memorize solutions but to internalize the underlying patterns so you can apply them to novel problems. That's what really impresses senior interviewers—the ability to adapt.

The Mental Grind and Why It's Worth It

Look, interview prep is a grind. There's no way around it. You'll hit walls, you'll bomb mock interviews, and you'll doubt yourself. But for problems like Trapping Rain Water, the struggle is the lesson. Each time you optimize, you're not just writing code; you're building a mental model for problem-solving. You're learning to decompose, to identify redundant work, and to leverage data structures effectively.

This isn't about memorizing 500 LeetCode problems. It's about deeply understanding the core 50 patterns that underpin them. Trapping Rain Water is one of those fundamental 50. Spend time on it. Draw diagrams. Talk through it out loud. Explain it to your rubber duck (or your cat). The clearer you can articulate the logic, the better you'll perform when the pressure is on.

So, next time you see this problem, don't just solve it. Master it. Understand its nuances, its optimizations, and how it connects to other problems. That's how you'll not just pass the interview, but actually become a better engineer.

Ready to Ace Your Next Interview?

Practice with AI-powered mock interviews tailored to your target role and company. Start Practicing for Free | Explore Interview Prep