Trapping Rain Water: stack en two-pointer
Los trapping-rain-water op met zowel de monotone-stack-aanpak, die horizontale lagen berekent, als de two-pointer-aanpak, die verticale kolommen berekent.
Trapping Rain Water: stack en two-pointer is een gratis DSA Interview Prep-les op CoddyKit. Dit is les 4 van 4. Je kunt 3 lessen uit dit leerpad gratis volledig lezen — daarna ontgrendelt CoddyKit PRO alle lessen, plus praktische oefeningen met een ingebouwde code-editor en een AI-tutor die 24/7 beschikbaar is. Deze les maakt deel uit van het leertraject DSA Interview Prep. Je voortgang wordt gesynchroniseerd op het web en in de CoddyKit-app. De cursus DSA Interview Prep bevat in totaal 4 lessen.
Probleem: regenwater opvangen
Regenwater opvangen (LeetCode 42) is een van de bekendste problemen in sollicitatiegesprekken. Gegeven n niet-negatieve gehele getallen die een hoogtekaart voorstellen, waarbij elke staaf breedte 1 heeft, bereken je hoeveel water er tussen de staven kan worden opgevangen nadat het heeft geregend. Water verzamelt zich in elk dal tussen aan beide kanten hogere staven.
Voor elke positie i is het waterniveau min(max_left[i], max_right[i]) - height[i]. Als dit negatief is, wordt er geen water opgevangen (de staaf is hoger dan ten minste één grens). Er bestaan drie aanpakken: vooraf berekende arrays O(n)/O(n), twee aanwijzers O(n)/O(1) en een monotone stapel 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)Aanpak 1: vooraf berekende maximumarrays
De eenvoudige oplossing met tijd O(n) en ruimte O(n) berekent vooraf twee arrays: max_left[i] = de maximale hoogte van index 0 tot en met i, en max_right[i] = de maximale hoogte van index i tot en met n-1. Het water op positie i is max(0, min(max_left[i], max_right[i]) - height[i]).
Het opbouwen van max_left vereist één doorgang van links naar rechts; voor max_right is een doorgang van rechts naar links nodig. Een laatste doorgang telt het water op. Deze aanpak is overzichtelijk en gemakkelijk uit te leggen, maar gebruikt O(n) extra ruimte.
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])) # 9Aanpak 2: twee aanwijzers (O(1) ruimte)
De methode met twee aanwijzers bereikt tijd O(n) en ruimte O(1). Gebruik een linker- en een rechteraanwijzer die aan de twee uiteinden beginnen. Houd max_left en max_right bij als lopende maxima die je tot dan toe vanaf elke kant hebt gezien.
Verwerk bij elke stap de kant met het kleinste lopende maximum — want die kant is de beperkende factor. Als max_left < max_right, is het water bij de linker aanwijzer max_left - height[left] (de rechterkant is hoog genoeg). Verplaats de linker aanwijzer naar binnen. Verwerk anders op symmetrische wijze de rechterkant. Vooraf berekende arrays zijn niet nodig.
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])) # 3Waarom de methode met twee aanwijzers werkt: de invariant
Het belangrijkste inzicht: wanneer we de linker aanwijzer verwerken omdat height[left] < height[right], weten we dat max_right >= height[right] > height[left]. De effectieve watergrens aan de rechterkant is dus minstens height[right], die al groter is dan max_left. Daarom geldt min(max_left, effective_max_right) = max_left en vereenvoudigt de waterformule tot max_left - height[left].
We hoeven de exacte max_right niet te kennen — het volstaat te weten dat deze minstens height[right] > height[left] is om max_left als waterniveau te gebruiken. Dit is de elegante invariant die ruimte O(1) mogelijk maakt.
# 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)Aanpak 3: Monotone stack (horizontale lagen)
De monotone-stackbenadering berekent water in horizontale lagen tussen aangrenzende staven. Houd een monotone afnemende stack met indices bij. Wanneer staaf i hoger is dan de top j van de stack, ontstaat een dal: de bodem is height[j], de linkerwand is height[stack[-1]] nadat j van de stack is gehaald, en de rechterwand is height[i]. Het water vult het dal tot min(left_wall, right_wall) - floor, met een breedte van i - stack[-1] - 1.
Elk dal wordt berekend wanneer een hogere staaf wordt aangetroffen. Zo verwerk je water in begrensde rechthoekige segmenten. Dat is nuttig wanneer je ook moet bijhouden welke staven bijdragen aan het waterniveau.
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])) # 9De monotone stack doorlopen
Laten we [0,1,0,2,1,0,1,3,...] doorlopen met de stackbenadering. Wanneer we staaf 3 (h=2) tegenkomen op i=3, is de top van de stack i=2 (h=0); haal die van de stack. De linkerwand is i=1 (h=1) en de rechterwand heeft hoogte h=2. De waterhoogte is min(1,2)-0=1, de breedte is 3-1-1=1 en de oppervlakte is 1. Daarna is de top van de stack i=1 (h=1) niet kleiner dan 2, dus stoppen we. Plaats 3 op de stack.
De stackmethode is ingewikkelder om te implementeren dan twee pointers, maar laat zien welke specifieke staven elke watercel vormen. Dit inzicht is nuttig bij vervolgvragen over het reconstrueren van de waterverdeling of het tellen van afzonderlijke dalen.
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)Alle drie de benaderingen vergelijken
Samenvatting van de drie benaderingen voor het opvangen van regenwater:
- Prefix-arrays: O(n) tijd, O(n) ruimte. Het gemakkelijkst te begrijpen en te controleren. Het meest geschikt voor sollicitatiegesprekken waarin duidelijkheid belangrijker is dan ruimte-efficiëntie.
- Twee pointers: O(n) tijd, O(1) ruimte. Optimaal in zowel tijd als ruimte. Het meest geschikt voor vervolgvragen als ‘kun je O(1) extra ruimte gebruiken?’.
- Monotone stack: O(n) tijd, O(n) ruimte. Verwerkt water in horizontale lagen. Het meest geschikt wanneer je moet weten welke staven bijdragen, of wanneer dit probleem als deelprobleem voorkomt in een groter stackgebaseerd algoritme.
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 met het meeste water
Container met het meeste water (LeetCode 11) wordt vaak verward met het opvangen van regenwater. Hierbij kies je precies twee staven en wordt het water alleen door die twee staven begrensd (interne staven doen er niet toe). Maximaliseer de oppervlakte min(height[l], height[r]) × (r - l).
Het twee-pointeralgoritme lost dit hebzuchtig op: begin aan beide uiteinden (maximale breedte). Verplaats de kortere pointer naar binnen — een verplaatsing van de langere pointer kan de oppervlakte alleen maar verkleinen. Dit kost O(n) tijd en O(1) ruimte en is eenvoudiger dan de twee-pointerbenadering voor het opvangen van regenwater, omdat je geen lopend maximum nodig hebt.
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 mapGeavanceerd: Regenwater opvangen II (3D)
Regenwater opvangen II (LeetCode 407) breidt het probleem uit naar een 2D-hoogtematrix. Water kan in alle vier de richtingen stromen en moet over de rand kunnen ontsnappen. De oplossing gebruikt een min-heap: initialiseer de heap met alle cellen aan de rand en voer daarna een BFS-achtige uitbreiding uit. Verwerk de cel met de kleinste hoogte — elke lagere buur moet water bevatten tot minstens het niveau van de huidige cel.
Dit is een fundamenteel ander algoritme dan in het 1D-geval en toetst zowel heapbewerkingen als BFS-doorlopen. De twee-pointertruc voor 1D generaliseert niet naar 2D; de heapbenadering wel.
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)) # 4Wanneer gebruik je elke methode in sollicitatiegesprekken
Beslisgids voor het sollicitatiegesprek over het opvangen van regenwater:
- Begin met: prefix-arrays — gemakkelijk uit te leggen, visueel intuïtief en duidelijk correct
- Vervolgvraag ‘O(1) ruimte?’: twee pointers — leg de invariant uit dat de kleinere kant de beperkende factor is
- Als de interviewer vraagt: ‘een andere aanpak?’: monotone stack — leg uit hoe je horizontale lagen berekent
Definieer altijd eerst duidelijk wat het waterniveau op elke positie bepaalt (het minimum van de hoogste staaf aan elke kant), voordat je naar de code springt. Zo laat je zien dat je het probleem begrijpt en wordt de oplossing gemakkelijker uit te leggen.
# 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()Randgevallen en veelgemaakte fouten
Veelgemaakte fouten bij het opvangen van regenwater:
- Vergeten het minimum te nemen: het waterniveau is
min(max_left, max_right), niet slechts een van beide waarden. Een staaf heeft aan beide kanten hoge wanden nodig. - Negatieve waterhoeveelheid: gebruik
max(0, ...)om negatieve waarden af te kappen op 0 wanneer de hoogte van een positie het waterniveau overschrijdt. - Randposities: de meest linkse en meest rechtse staven kunnen nooit water bevatten, omdat aan één kant een wand ontbreekt. De prefix-arraybenadering handelt dit vanzelf goed af:
max_left[0] = height[0]zorgt ervoor dat de hoeveelheid water op index 0 altijd 0 is. - Lege of zeer kleine arrays: geef 0 terug voor arrays met minder dan 3 elementen.
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 waterSnelle controle
Toets je begrip van de concepten uit deze les in Data Structures & Algorithms — Coding Interview Prep.
Samenvatting van de les
In deze les heb je geleerd: je lost het opvangen van regenwater op door op elke positie het minimum te nemen van de hoogste linker- en rechterwand, de O(1)-ruimtebenadering met twee pointers werkt omdat het lopende maximum aan de kant met de kleinere hoogte altijd de beperkende factor is, en de monotone-stackbenadering berekent water in horizontale lagen, wat nuttig is in combinatie met andere stackgebaseerde logica. Hierna schakelen we over op concepten voor systeemontwerp, te beginnen met het RADIO-raamwerk voor gestructureerde antwoorden in sollicitatiegesprekken.
Leer Python met een AI-tutor — gratis
Schrijf echte code en voer die uit in je browser, krijg direct hulp van een AI-tutor die 24/7 beschikbaar is en ga verder waar je gebleven bent op het web of in de app.
- Cursussen
- 30
- Lessen
- 120
Veelgestelde vragen
Is de les “Trapping Rain Water: stack en two-pointer” gratis?
Ja — je kunt hier op het web alle 3 lessen van het leerpad DSA Interview Prep, waaronder “Trapping Rain Water: stack en two-pointer”, gratis volledig lezen. Daarna ontgrendelt CoddyKit PRO alle lessen, plus interactieve oefeningen met een ingebouwde code-editor en een AI-tutor die 24/7 beschikbaar is. De cursus DSA Interview Prep bevat in totaal 4 lessen.
Wat leer ik in “Trapping Rain Water: stack en two-pointer”?
Los trapping-rain-water op met zowel de monotone-stack-aanpak, die horizontale lagen berekent, als de two-pointer-aanpak, die verticale kolommen berekent. Je oefent met DSA Interview Prep door code rechtstreeks in de browser uit te voeren. Een AI-begeleider die 24/7 beschikbaar is beantwoordt je vragen terwijl je de les doorwerkt.
Heb ik ervaring nodig om met DSA Interview Prep te beginnen?
Ervaring vooraf is niet nodig. DSA Interview Prep op CoddyKit is opgebouwd voor beginners tot gevorderden, zodat je hier of bij het begin kunt starten en in je eigen tempo kunt leren. Dit is les 4 van 4.
Hoe lang duurt de les “Trapping Rain Water: stack en two-pointer”?
De meeste lessen van CoddyKit duren ongeveer 5–10 minuten. Elke les is kort en interactief, zodat je gestaag vooruitgaat en op het web en in de app precies verdergaat waar je was gebleven.
Kan ik code schrijven en uitvoeren in deze les over DSA Interview Prep?
Ja. Elke les over DSA Interview Prep bevat een ingebouwde code-editor, zodat je rechtstreeks in je browser echte code kunt schrijven en uitvoeren en direct feedback van AI krijgt — lokale installatie is niet nodig.
Alle lessen in deze cursus
- Monotone stack: oplopend versus aflopend
- Grootste rechthoek in een histogram
- Maximum in een sliding window met een monotone deque
- Trapping Rain Water: stack en two-pointer