42. Trapping Rain Water
Asked at Google, Meta, Amazon, Oracle and 6 more
Difficulty
Hard
Time
O(n)
Space
O(1)
Pattern
Array
Companies
10
Problem
You are given an array height of non-negative integers. Each number is the height of a wall of width 1, standing side by side. Imagine it rains and water fills the gaps between the walls. Return the total number of water units that stay trapped.
Water sits on top of a position only if there are taller (or equal) walls somewhere to its left and somewhere to its right. The water level above position i is min(tallest wall on the left, tallest wall on the right) - height[i]. If that value is negative, no water stays there, so you add 0.
The walls at the two ends cannot hold water on their outer side, so they never trap anything by themselves. Return a single integer: the sum of trapped water over all positions.
Where the water sits
Constraints
- ●
n == height.length - ●
1 <= n <= 2 * 10^4 - ●
0 <= height[i] <= 10^5
Examples
height = [0,1,0,2,1,0,1,3,2,1,2,1]6height = [4,2,0,3,2,5]9Asked At
10 companies| Company | Difficulty | |
|---|---|---|
| Hard | View all Google questions → | |
| Meta | Hard | View all Meta questions → |
| Amazon | Hard | View all Amazon questions → |
| Oracle | Hard | View all Oracle questions → |
| Salesforce | Hard | View all Salesforce questions → |
| OpenAI | Hard | View all OpenAI questions → |
| Walmart | Hard | View all Walmart questions → |
| Bloomberg | Hard | View all Bloomberg questions → |
| Goldman Sachs | Hard | View all Goldman Sachs questions → |
| Snowflake | Hard | View all Snowflake questions → |
How to Think About It
Brute force: for each position i, scan left to find max_left and scan right to find max_right. Water at i = min(max_left, max_right) - height[i]. O(n²) time because each position requires two scans.
Better: precompute two arrays. left_max[i] = max height from 0 to i. right_max[i] = max height from i to n-1. Water at i = min(left_max[i], right_max[i]) - height[i]. O(n) time, O(n) space.
Optimal: two pointers from both ends. Track left_max and right_max as you go. At each step, move the pointer with the smaller max. The key insight: if left_max < right_max, everything to the right of left is at least right_max tall — so left_max is the bottleneck. Water at left = left_max - height[left].
Why the two-pointer invariant works: when height[lo] < height[hi], we know right_max >= height[hi] > height[lo]. So left_max is guaranteed to be the minimum of the two maximums. We can safely calculate water at lo without scanning the right side.
Optimal Approach
Two pointers from both ends. Track left_max and right_max.
At each step:
- If
height[lo]<height[hi]:- If height[lo] >= left_max: update left_max- Else: water += left_max - height[lo]- Move lo right
- Else:
- If height[hi] >= right_max: update right_max- Else: water += right_max - height[hi]- Move hi left
The invariant: left_max is always the max height from 0 to lo. right_max is always the max height from hi to n-1. When height[lo] < height[hi], we know right_max >= height[hi] > height[lo], so left_max is the bottleneck for water at lo.
Time: O(n) — single pass. Space: O(1).
Two pointers, smaller side moves
What Trips People Up in Real Interviews
Confusing this with "container with most water." This problem asks for total water trapped across the entire array, not the maximum single container.
Trying to calculate water at each position without knowing the max height to the left and right. Pre-compute leftMax and rightMax arrays, or use two pointers.
Forgetting that water at position i = min(leftMax[i], rightMax[i]) - height[i]. If this is negative (height[i] is taller than both maxes), water is 0.
Not handling edge cases: empty array (return 0), single element (return 0), array with no dips (return 0).
Subtracting the bar's height from only one of the two maximums. The correct formula is min(leftMax, rightMax) - height[i]. Using just leftMax or just rightMax overestimates the trapped water.
Solution Code
O(n) timedef trap(height):
lo, hi = 0, len(height) - 1
left_max = right_max = water = 0
while lo < hi:
if height[lo] < height[hi]:
if height[lo] >= left_max:
left_max = height[lo]
else:
water += left_max - height[lo]
lo += 1
else:
if height[hi] >= right_max:
right_max = height[hi]
else:
water += right_max - height[hi]
hi -= 1
return waterFrequently Asked Questions
What is the Trapping Rain Water problem?
Given n non-negative integers representing an elevation map, compute how much water it can trap after raining. This is a classic hard problem that tests your ability to reason about left and right maximums.
How do you solve Trapping Rain Water?
The optimal approach runs in O(n) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Trapping Rain Water?
Trapping Rain Water is asked at Google, Meta, Amazon, Oracle, Salesforce, OpenAI, Walmart, Bloomberg, Goldman Sachs, Snowflake. It is a hard difficulty problem.
What are common mistakes on Trapping Rain Water?
- Confusing this with "container with most water." This problem asks for total water trapped across the entire array, not the maximum single container.
- Trying to calculate water at each position without knowing the max height to the left and right. Pre-compute `leftMax` and `rightMax` arrays, or use two pointers.
- Forgetting that water at position i = min(`leftMax[i]`, `rightMax[i]`) - `height[i]`. If this is negative (`height[i]` is taller than both maxes), water is 0.
- Not handling edge cases: empty array (return 0), single element (return 0), array with no dips (return 0).
- Subtracting the bar's height from only one of the two maximums. The correct formula is min(`leftMax`, `rightMax`) - `height[i]`. Using just leftMax or just rightMax overestimates the trapped water.