Compute how much rain water an elevation map traps using two pointers with running left/right maxima in O(n) time and O(1) space. Classic FAANG hard.
The problem
heights is an elevation map of bars of width 1. Return how many units of water it traps after rain.
Examples
Example 1
Input
trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1])
Expected output
6
Example 2
Input
trap([4, 2, 0, 3, 2, 5])
Expected output
9
+ 4 hidden tests on Submit — descending: nothing trapped.
Edge cases to ask about
- Monotonic heights
- Fewer than 3 bars
- Plateaus
Hints
0/3How an interviewer scores this
0/9Your code runs in real CPython inside your browser — nothing is sent anywhere. The first run downloads the interpreter (about 6 MB, once). Your code is saved on this device as you type.
Complexity Lab
What does this cost as n grows?
Interviewers score the analysis as much as the code. Commit to an answer first — then check it, and measure your code against the optimal one at growing input sizes.
Pick both to reveal the answer.
Measure it
Runs the function on inputs of size 250 up to 16,000 and records the time and peak memory. Slow solutions stop early — a short curve is itself the answer.
From brute force to optimal
The progression an interviewer wants to hear, one step at a time.
| Approach | Time | Space | Idea |
|---|---|---|---|
| Scan left and right for every bar | O(n²) | O(1) | |
| Prefix-max and suffix-max arrays | O(n) | O(n) | water[i] = min(L[i], R[i]) − h[i]. |
| bestTwo pointers | O(n) | O(1) | Process the side with the smaller max — its bound is already known. |
Walkthrough of the optimal approach (try it yourself first)
Water above bar i is min(max_left, max_right) − h[i]. Precomputing prefix and suffix maxima gives an O(n)-space solution.
Two pointers remove the arrays. If h[lo] < h[hi], the right side has a bar at least as tall as anything that limits lo, so lo's water level is decided by left_max alone. Add left_max − h[lo] and move lo. Do the mirror on the other side.
Complexity: O(n) time, O(1) space. Each pointer only moves inward, so the loop runs n − 1 times with a few variables.
Reveal the reference solution
def trap(heights): lo, hi = 0, len(heights) - 1 left_max = right_max = 0 water = 0 while lo < hi: if heights[lo] < heights[hi]: left_max = max(left_max, heights[lo]) water += left_max - heights[lo] lo += 1 else: right_max = max(right_max, heights[hi]) water += right_max - heights[hi] hi -= 1 return water
The brute force, for comparison
def trap(heights): water = 0 for i in range(len(heights)): left = max(heights[:i + 1]) right = max(heights[i:]) water += min(left, right) - heights[i] return water
Follow-ups interviewers ask
- Trapping rain water II (2-D, heap + BFS).
Frequently asked interview questions
Core interview concepts, complexities, and follow-ups scored by hiring teams.
What is the time complexity of Trapping Rain Water in Python?
The optimal solution runs in O(n) time and O(1) auxiliary space. Each pointer only moves inward, so the loop runs n − 1 times with a few variables.
What is the brute-force approach, and how do you optimise it?
Scan left and right for every bar: O(n²) time, O(1) space. Prefix-max and suffix-max arrays: O(n) time, O(n) space. water[i] = min(L[i], R[i]) − h[i]. Two pointers: O(n) time, O(1) space. Process the side with the smaller max — its bound is already known.
What follow-up questions do interviewers ask about Trapping Rain Water?
Trapping rain water II (2-D, heap + BFS).