← all entries
A-014● Day 142026.05.16hardleetcode #42neetcode150

Trapping Rain Water

#array#two-pointers#dynamic-programming#stack#monotonic-stack
↗ leetcode #42 · trapping-rain-water
01

Problem

· problem
P.014

Trapping Rain Water

↗ leetcode #42

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

constraints
  • · n == height.length
  • · 1 ≤ n ≤ 2 × 10⁴
  • · 0 ≤ height[i] ≤ 10⁵
// paraphrased summary — see source for full text
examples
example 1input → output
[0,1,0,2,1,0,1,3,2,1,2,1]
6
example 2input → output
[4,2,0,3,2,5]
9
02

Pre-solve

· pre-solve
● 1list shown→● 2select→● 3reveal
  • ☐
    What determines the amount of water trapped at each position?
  • ☐
    Why move the left pointer when leftMax < rightMax?
  • ☐
    What are the time and space complexity?
  • ☐
    Could you solve this by sorting the array?
  • ☐
    Is water level at position i equal to height[i]?
  • ☐
    Do you need to precompute leftMax and rightMax arrays?
  • ☐
    Can you solve this with a monotonic stack?
  • ☐
    Why iterate until pointers meet?
check the items you would ask, then press confirm
// session-only state — refresh resets (repeatable practice)
03

Logic Structure

· logic
● 1slots shown→● 2pick per slot→● 3reveal
// pick one code line per slot to assemble the algorithm flow. no typing — just the logic skeleton.
step 1· Handle empty input
○
if not height:
○
if len(height) == 0:
○
if height is None:
step 2· Initialize two pointers
○
l, r = 0, len(height) - 1
○
l, r = 0, len(height)
○
l, r = 1, len(height) - 2
step 3· Initialize max heights from boundaries
○
leftMax, rightMax = height[l], height[r]
○
leftMax, rightMax = 0, 0
○
leftMax, rightMax = height[0], height[len(height)-1]
step 4· Main loop: two-pointer iteration
○
while l < r:
○
while l <= r:
○
for i in range(len(height)):
step 5· Process left side: update left max│ nested
○
leftMax = max(leftMax, height[l])
○
leftMax = height[l]
○
leftMax = leftMax + height[l]
step 6· Accumulate water on left side│ │ nested
○
res += leftMax - height[l]
○
res += height[l] - leftMax
○
res = leftMax - height[l]
step 7· Process right side: update right max│ nested
○
rightMax = max(rightMax, height[r])
○
rightMax = height[r]
○
rightMax = rightMax + height[r]
pick one option per slot
// format: slot — recursive / DP patterns use ordering / state-first formats. ADR-08 follow-up.
04

Solve · Trace

· solve
solution.py
1
class Solution:
2
    def trap(self, height: List[int]) -> int:
3
        if not height:
4
            return 0
5
6
        l, r = 0, len(height) - 1
7
        leftMax, rightMax = height[l], height[r]
8
        res = 0
9
        while l < r:
10
            if leftMax < rightMax:
11
                l += 1
12
                leftMax = max(leftMax, height[l])
13
                res += leftMax - height[l]
14
            else:
15
                r -= 1
16
                rightMax = max(rightMax, height[r])
17
                res += rightMax - height[r]
18
        return res
mental dry-run cases
// walk each case in your head; expand the worked example below if stuck.
case 1
[0,1,0,2,1,0,1,3,2,1,2,1]
→
6
case 2
[4,2,0,3,2,5]
→
9
// UI does not walk-through — you do the dry-run mentally. Expand the worked example if stuck.