Trapping Rain Water: Stack and Two-Pointer
Solve trapping-rain-water using both the monotonic-stack approach that computes horizontal layers and the two-pointer approach that computes vertical columns.
Trapping Rain Water: Stack and Two-Pointer is a free DSA Interview Prep lesson on CoddyKit — lesson 4 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the DSA Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
Problem: Trapping Rain Water
Trapping Rain Water (LeetCode 42) is one of the most iconic interview problems. Given n non-negative integers representing an elevation map where each bar has width 1, compute how much water can be trapped between the bars after it rains. Water fills in any valley between taller bars on both sides.
For each position i, the water level is min(max_left[i], max_right[i]) - height[i]. If this is negative, no water is trapped (the bar is taller than at least one boundary). Three approaches exist: precomputed arrays O(n)/O(n), two pointers O(n)/O(1), and monotonic stack O(n)/O(n).
height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
# Water trapped at each position:
# pos 2: min(1,3)-0=1
# pos 4: min(2,3)-1=1
# pos 5: min(2,3)-0=2
# pos 6: min(2,3)-1=1
# pos 9: min(3,2)-1=1
# Total = 6
print('height:', height)
print('Expected trapped water: 6')
# Visualise
max_h = max(height)
for row in range(max_h, 0, -1):
line = ''
for h in height:
line += '#' if h >= row else ' '
print(line)Approach 1: Precomputed Max Arrays
The straightforward O(n) time, O(n) space solution precomputes two arrays: max_left[i] = maximum height from index 0 to i, and max_right[i] = maximum height from index i to n-1. The water at position i is max(0, min(max_left[i], max_right[i]) - height[i]).
Building max_left requires a single left-to-right pass; max_right requires a right-to-left pass. A final pass sums up the water. This approach is clean and easy to explain but uses O(n) extra space.
def trap_prefix(height):
n = len(height)
if n < 3:
return 0
max_left = [0] * n
max_right = [0] * n
max_left[0] = height[0]
for i in range(1, n):
max_left[i] = max(max_left[i-1], height[i])
max_right[-1] = height[-1]
for i in range(n-2, -1, -1):
max_right[i] = max(max_right[i+1], height[i])
water = 0
for i in range(n):
water += max(0, min(max_left[i], max_right[i]) - height[i])
return water
print(trap_prefix([0,1,0,2,1,0,1,3,2,1,2,1])) # 6
print(trap_prefix([4,2,0,3,2,5])) # 9Approach 2: Two Pointers (O(1) Space)
The two-pointer approach achieves O(n) time and O(1) space. Use left and right pointers starting at the two ends. Maintain max_left and max_right as running maximums seen so far from each side.
At each step, process the side with the smaller running maximum — because that side is the limiting factor. If max_left < max_right, the water at the left pointer is max_left - height[left] (the right side is tall enough). Move the left pointer inward. Otherwise process the right pointer symmetrically. No precomputed arrays needed.
def trap_two_pointer(height):
left, right = 0, len(height) - 1
max_left = max_right = 0
water = 0
while left < right:
if height[left] < height[right]:
if height[left] >= max_left:
max_left = height[left] # new max on the left
else:
water += max_left - height[left] # trapped by max_left
left += 1
else:
if height[right] >= max_right:
max_right = height[right]
else:
water += max_right - height[right]
right -= 1
return water
print(trap_two_pointer([0,1,0,2,1,0,1,3,2,1,2,1])) # 6
print(trap_two_pointer([4,2,0,3,2,5])) # 9
print(trap_two_pointer([3,0,3])) # 3Why Two Pointers Works: The Invariant
The key insight: when we process the left pointer because height[left] < height[right], we know max_right >= height[right] > height[left]. Therefore, the effective water boundary on the right is at least height[right], which is already greater than max_left. So min(max_left, effective_max_right) = max_left, and the water formula simplifies to max_left - height[left].
We do not need to know the exact max_right — just knowing it is at least height[right] > height[left] is sufficient to use max_left as the water level. This is the elegant invariant that makes O(1) space possible.
# Trace two-pointer on [4, 2, 0, 3, 2, 5]
height = [4, 2, 0, 3, 2, 5]
left, right = 0, len(height) - 1
max_l = max_r = water = 0
print('height:', height)
print(f'{'Step':5} {'L':3} {'R':3} {'maxL':5} {'maxR':5} {'water':6} {'total':6}')
step = 0
while left < right:
side = 'L' if height[left] < height[right] else 'R'
if side == 'L':
if height[left] >= max_l: max_l = height[left]
else:
w = max_l - height[left]; water += w
left += 1
else:
if height[right] >= max_r: max_r = height[right]
else:
w = max_r - height[right]; water += w
right -= 1
step += 1
print(f'{step:5} {left:3} {right:3} {max_l:5} {max_r:5} {water:6}')
print('Total trapped:', water)Approach 3: Monotonic Stack (Horizontal Layers)
The monotonic stack approach computes water in horizontal layers between adjacent bars. Maintain a monotonic decreasing stack of indices. When bar i is taller than the stack top j, a valley forms: the floor is height[j], the left wall is height[stack[-1]] after popping j, and the right wall is height[i]. Water fills the valley up to min(left_wall, right_wall) - floor, with width i - stack[-1] - 1.
Each 'valley' is computed when a taller bar is encountered. This processes water in bounded rectangular segments, which is useful when you also need to track which bars contribute to the water level.
def trap_stack(height):
stack = [] # monotonic decreasing indices
water = 0
for i in range(len(height)):
while stack and height[stack[-1]] < height[i]:
bottom_idx = stack.pop() # the floor of the valley
if not stack:
break # no left wall, no water
left_idx = stack[-1]
floor = height[bottom_idx]
water_height = min(height[left_idx], height[i]) - floor
width = i - left_idx - 1
water += water_height * width
stack.append(i)
return water
print(trap_stack([0,1,0,2,1,0,1,3,2,1,2,1])) # 6
print(trap_stack([4,2,0,3,2,5])) # 9Tracing the Monotonic Stack
Let us trace [0,1,0,2,1,0,1,3,...] with the stack approach. When we encounter bar 3 (h=2) at i=3: stack top is i=2 (h=0), pop it. Left wall is i=1 (h=1), right wall is h=2. Water height = min(1,2)-0=1, width=3-1-1=1, area=1. Continue: stack top i=1 (h=1) is not less than 2, stop. Push 3.
The stack method is more complex to implement than two pointers but reveals which specific bars form each water cell. This insight is useful in follow-up questions about reconstructing the water layout or counting distinct valleys.
def trap_stack_trace(height):
stack = []
water = 0
for i in range(len(height)):
print(f'i={i} h={height[i]}: stack={[height[s] for s in stack]}')
while stack and height[stack[-1]] < height[i]:
bot = stack.pop()
if not stack:
print(f' Pop {height[bot]}: no left wall, skip')
break
left = stack[-1]
h = min(height[left], height[i]) - height[bot]
w = i - left - 1
water += h * w
print(f' Pop {height[bot]}: floor={height[bot]}, left_wall={height[left]}, right_wall={height[i]}, h={h}, w={w}, +{h*w}')
stack.append(i)
return water
result = trap_stack_trace([0,1,0,2,1,0,1,3,2,1,2,1])
print('Total:', result)Comparing All Three Approaches
Summary of the three trapping rain water approaches:
- Prefix arrays: O(n) time, O(n) space. Easiest to understand and verify. Best for interviews where clarity is valued over space efficiency.
- Two pointers: O(n) time, O(1) space. Optimal in both time and space. Best for follow-up 'can you do O(1) space?' questions.
- Monotonic stack: O(n) time, O(n) space. Processes water in horizontal layers. Best when you need to know which bars contribute or when this problem appears as a sub-problem in a larger stack-based algorithm.
height = [0,1,0,2,1,0,1,3,2,1,2,1]
# All three methods — verify they agree
def trap_prefix(h):
n = len(h)
ml = [0]*n; mr = [0]*n; ml[0]=h[0]; mr[-1]=h[-1]
for i in range(1,n): ml[i]=max(ml[i-1],h[i])
for i in range(n-2,-1,-1): mr[i]=max(mr[i+1],h[i])
return sum(max(0,min(ml[i],mr[i])-h[i]) for i in range(n))
def trap_two_ptr(h):
l,r,ml,mr,w = 0,len(h)-1,0,0,0
while l<r:
if h[l]<h[r]:
ml=max(ml,h[l]); w+=ml-h[l]; l+=1
else:
mr=max(mr,h[r]); w+=mr-h[r]; r-=1
return w
def trap_stk(h):
stk,w = [],[]
for i in range(len(h)):
while stk and h[stk[-1]]<h[i]:
b=stk.pop()
if not stk: break
w.append(max(0,min(h[stk[-1]],h[i])-h[b])*(i-stk[-1]-1))
stk.append(i)
return sum(w)
for h in [height, [4,2,0,3,2,5], [3,0,3], [1,0,1]]:
p=trap_prefix(h); t=trap_two_ptr(h); s=trap_stk(h)
print(f'{h}: prefix={p}, two-ptr={t}, stack={s}, match={p==t==s}')Container with Most Water
Container With Most Water (LeetCode 11) is often confused with trapping rain water. Here, you choose exactly two bars and the water is bounded only by those two bars (no internal bars matter). Maximise the area min(height[l], height[r]) × (r - l).
Two pointers solve this greedily: start at both ends (maximum width). Move the shorter pointer inward — moving the taller one can only decrease the area. This is O(n) time and O(1) space, simpler than the trapping rain water two-pointer because no running max is needed.
def max_water_container(height):
left, right = 0, len(height) - 1
max_area = 0
while left < right:
area = min(height[left], height[right]) * (right - left)
max_area = max(max_area, area)
# Move the shorter bar: moving taller bar can only reduce min
if height[left] < height[right]:
left += 1
else:
right -= 1
return max_area
print(max_water_container([1,8,6,2,5,4,8,3,7])) # 49: bars 8 and 7
print(max_water_container([1,1])) # 1
print(max_water_container([4,3,2,1,4])) # 16
# Key difference from trapping rain water:
# Container: choose 2 bars, water fills freely between them (no internal barriers)
# Trapping: water fills ALL valleys in the full elevation mapAdvanced: Trapping Rain Water II (3D)
Trapping Rain Water II (LeetCode 407) extends to a 2D height matrix. Water can flow in all four directions and must escape over the border. The solution uses a min-heap: initialize the heap with all border cells, then perform BFS-like expansion. Process the cell with the smallest height — any lower neighbour must hold water at least at the current cell's level.
This is a fundamentally different algorithm from the 1D case and tests both heap operations and BFS traversal. The 1D two-pointer trick does not generalise to 2D; the heap approach does.
import heapq
def trap_rain_water_2d(heightMap):
if not heightMap or not heightMap[0]:
return 0
m, n = len(heightMap), len(heightMap[0])
visited = [[False]*n for _ in range(m)]
heap = [] # (height, row, col)
# Add all border cells to the heap
for i in range(m):
for j in [0, n-1]:
heapq.heappush(heap, (heightMap[i][j], i, j))
visited[i][j] = True
for j in range(n):
for i in [0, m-1]:
if not visited[i][j]:
heapq.heappush(heap, (heightMap[i][j], i, j))
visited[i][j] = True
total = 0
max_h = 0
while heap:
h, r, c = heapq.heappop(heap)
max_h = max(max_h, h)
for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
nr, nc = r+dr, c+dc
if 0<=nr<m and 0<=nc<n and not visited[nr][nc]:
visited[nr][nc] = True
total += max(0, max_h - heightMap[nr][nc])
heapq.heappush(heap, (max(max_h, heightMap[nr][nc]), nr, nc))
return total
map2d = [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]]
print(trap_rain_water_2d(map2d)) # 4When to Use Each Method in Interviews
Decision guide for the trapping rain water interview:
- Start with: prefix arrays — easy to explain, visually intuitive, clearly correct
- Follow-up 'O(1) space?': two pointers — explain the invariant that the smaller side is the bottleneck
- If interviewer asks 'another approach?': monotonic stack — explain horizontal layer computation
Always start by clearly defining what determines the water level at each position (the minimum of the tallest bar on each side) before jumping into code. This shows problem comprehension and makes the solution easier to explain.
# Quick summary of all three approaches
approaches = [
{
'name': 'Prefix max arrays',
'time': 'O(n)', 'space': 'O(n)',
'description': '3 passes: build max_left, max_right, sum water column-by-column',
},
{
'name': 'Two pointers',
'time': 'O(n)', 'space': 'O(1)',
'description': 'Process smaller side: its max is the limiting wall, no array needed',
},
{
'name': 'Monotonic stack',
'time': 'O(n)', 'space': 'O(n)',
'description': 'Compute water in horizontal layers when a taller bar is encountered',
},
]
for a in approaches:
print(f'{a["name"]} [{a["time"]} / {a["space"]}]')
print(f' {a["description"]}')
print()Edge Cases and Common Mistakes
Common mistakes on trapping rain water:
- Forgetting min: the water level is
min(max_left, max_right), not just one of them. A bar needs tall walls on both sides. - Negative water: use
max(0, ...)to clamp negative values to 0 when a position's height exceeds the water level. - Edge positions: the leftmost and rightmost bars can never hold water (no wall on one side). The prefix array approach handles this naturally since
max_left[0] = height[0]makes the water always 0 at index 0. - Empty or tiny arrays: return 0 for arrays with fewer than 3 elements.
def trap(height):
n = len(height)
if n < 3:
return 0 # need at least 3 bars to trap anything
left, right = 0, n - 1
max_l = max_r = water = 0
while left < right:
if height[left] <= height[right]:
if height[left] >= max_l:
max_l = height[left]
else:
water += max_l - height[left] # never negative: max_l > height[left]
left += 1
else:
if height[right] >= max_r:
max_r = height[right]
else:
water += max_r - height[right]
right -= 1
return water
# Edge cases
print(trap([])) # 0: empty
print(trap([1])) # 0: single bar
print(trap([1,2])) # 0: two bars
print(trap([3,0,3])) # 3: simple valley
print(trap([3,3,3])) # 0: flat top, no waterQuick Check
Test your understanding of Data Structures & Algorithms — Coding Interview Prep concepts from this lesson.
Lesson Recap
In this lesson you learned: trapping rain water is solved by finding the minimum of the tallest left and right walls at each position, the two-pointer O(1)-space approach works because the smaller-side running maximum is always the binding constraint, and the monotonic stack approach computes water in horizontal layers, useful when combined with other stack-based logic. Next up we switch to system design concepts, starting with the RADIO framework for structured interview answers.
Frequently asked questions
Is the “Trapping Rain Water: Stack and Two-Pointer” lesson free?
Yes — the full text of “Trapping Rain Water: Stack and Two-Pointer” is free to read here on the web, and the DSA Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the DSA Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “Trapping Rain Water: Stack and Two-Pointer”?
Solve trapping-rain-water using both the monotonic-stack approach that computes horizontal layers and the two-pointer approach that computes vertical columns. You practise DSA Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start DSA Interview Prep?
No prior experience is required. DSA Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 4 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Trapping Rain Water: Stack and Two-Pointer” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this DSA Interview Prep lesson?
Yes. Every DSA Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- Monotonic Stack: Increasing vs Decreasing
- Largest Rectangle in Histogram
- Sliding Window Maximum with Monotonic Deque
- Trapping Rain Water: Stack and Two-Pointer