Skip to content

Volume ITechnology

4.5.5 — Trapping Rain Water ​

LeetCode 42 · Hard · ★ Blind 75

The problem ​

You are given a list called height. Each number is the height of a bar, and every bar is 1 unit wide. The bars stand side by side, like a skyline seen from the side. Rain falls and fills the dips between the bars. Return the total amount of water trapped.

height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]   →  6
height = [4, 2, 0, 3, 2, 5]                     →  9

There are up to 20,000 bars, and every height is zero or more.

What the problem is really asking ​

The shape of the whole skyline is hard to think about at once. So do not try. Think about one position at a time, and ask how deep the water is directly above that one bar.

Stand on bar i and look both ways. Somewhere to your left is the tallest bar on that side. Call its height leftMax. Somewhere to your right is the tallest bar on that side, rightMax. Water above you can rise only as high as the lower of those two walls. Any higher, and it would spill over the lower side. Your own bar fills the bottom part of that space. So the water above position i is:

\text{water}[i] = \min(\text{leftMax},\, \text{rightMax}) - \text{height}[i]

Read it aloud as "the smaller of the two tallest walls, minus my own height".

Two small facts make this formula safe to use everywhere.

  • We count the bar itself when working out leftMax and rightMax. So if bar i is taller than everything around it, both maxima equal its own height, and the formula gives exactly 0. It never goes negative.
  • The first bar and the last bar always hold 0, because one side has no wall at all.

Think of standing in a valley. To your left is a hill 10 metres tall. To your right is a hill 50 metres tall. When it floods, water fills up to 10 metres and then pours over the shorter hill. The tall hill does not matter. The rest of the problem is only about computing leftMax and rightMax cheaply for every position.

2013water level = min(leftMax 2, rightMax 3) = 2position 1 holds 2 − 0 = 2position 2 holds 2 − 1 = 1The level is set by the shorter wall, which is the 2 on the left.
The water level over a dip is the shorter of the two surrounding peaks, and the bar's own height is subtracted from it.

The brute force, and where it wastes work ​

Use the formula directly. For each bar, scan left to find leftMax and scan right to find rightMax.

python
def trap(height):
    n = len(height)
    total = 0
    for i in range(n):
        left_max = max(height[:i + 1])     # tallest from the start up to i
        right_max = max(height[i:])        # tallest from i to the end
        total += min(left_max, right_max) - height[i]
    return total

Each bar scans up to n bars, so this is O(n^2). For 20,000 bars that is 400 million steps.

The waste in one sentence: the tallest bar to the left of position 6 is just the tallest bar to the left of position 5, compared with one more bar, yet the brute force scans the whole left side again from scratch.

Solution 1 — compute both maxima in advance ​

Fix the waste with two sweeps. Sweep left to right, carrying the tallest bar seen so far. That fills a list left_max. Sweep right to left to fill right_max. Then apply the formula at every position.

python
class Solution:
    def trap(self, height: List[int]) -> int:
        n = len(height)
        if n == 0:
            return 0

        left_max = [0] * n
        left_max[0] = height[0]
        for i in range(1, n):
            left_max[i] = max(left_max[i - 1], height[i])     # one more bar than before

        right_max = [0] * n
        right_max[-1] = height[-1]
        for i in range(n - 2, -1, -1):
            right_max[i] = max(right_max[i + 1], height[i])

        return sum(min(left_max[i], right_max[i]) - height[i] for i in range(n))

This is O(n) time and O(n) extra memory, for the two lists.

It is exactly 4.4.7 Product of Array Except Self with max instead of ×. Two sweeps in opposite directions, each carrying a running value, then combined. Write this version first in an interview. It is easy to get right and easy to explain.

Solution 2 — two pointers, with no extra lists ​

Now the clever part. It rests on one observation:

To fill a position, you do not need to know the exact taller wall. You only need to know which side's wall is lower.

Walk in from both ends with two pointers, l and r. Keep left_max, the tallest bar seen from the left so far, and right_max, the tallest seen from the right so far.

Suppose left_max < right_max. Look at the next bar on the left side. Its true right-hand maximum is at least right_max, because right_max is a bar that really stands somewhere to its right, and there may be taller ones too. That means its true right-hand maximum is bigger than left_max. So the smaller of its two walls is left_max. Its water is settled already, and we can add it without ever looking at the bars in the middle.

The same is true in mirror image when right_max is the smaller one.

So the rule is: always work on the side whose wall is lower, because that side's answer is already decided.

python
class Solution:
    def trap(self, height: List[int]) -> int:
        if not height:                                    # (1)
            return 0

        l, r = 0, len(height) - 1                         # (2)
        left_max, right_max = height[l], height[r]        # (3)
        trapped = 0

        while l < r:                                      # (4)
            if left_max < right_max:                      # (5)
                l += 1                                    # (6)
                if height[l] >= left_max:                 # (7)
                    left_max = height[l]
                else:                                     # (8)
                    trapped += left_max - height[l]
            else:                                         # (9)
                r -= 1
                if height[r] >= right_max:
                    right_max = height[r]
                else:
                    trapped += right_max - height[r]

        return trapped
ts
function trap(height: number[]): number {
  if (height.length === 0) return 0;                      // (1)

  let l = 0, r = height.length - 1;                       // (2)
  let leftMax = height[l], rightMax = height[r];          // (3)
  let trapped = 0;

  while (l < r) {                                         // (4)
    if (leftMax < rightMax) {                             // (5)
      l++;                                                // (6)
      if (height[l] >= leftMax) leftMax = height[l];      // (7)
      else trapped += leftMax - height[l];                // (8)
    } else {                                              // (9)
      r--;
      if (height[r] >= rightMax) rightMax = height[r];
      else trapped += rightMax - height[r];
    }
  }

  return trapped;
}

Line by line ​

(1) Empty input. No bars means no water.

(2) One pointer at each end.

(3) The walls so far. At the start, the only bar seen from the left is height[0], and the only bar seen from the right is the last one. So those are the starting maxima.

(4) Keep going until the pointers meet. Every bar strictly between the two ends gets handled exactly once along the way.

(5) Which side is lower? If the left wall is lower, the next left bar's water is settled by left_max, as argued above.

(6) Move the pointer first, then look at the bar. This order is on purpose. It means the very first bar, position 0, is never examined for water, and neither is the last bar. Those are exactly the two bars that can never hold water. So no special boundary check is needed.

(7) A new, taller wall. If the bar is at least as tall as left_max, water cannot sit on top of it, because it sticks up past the wall. Instead it becomes the new left_max for the bars further in.

(8) A dip. The bar is shorter than left_max. Water fills it up to left_max, so we add left_max - height[l]. This can never be negative, because this branch only runs when height[l] is below left_max. That is why there is no max(..., 0) anywhere.

(9) The mirror case. If the right wall is lower (or equal), we do the same thing from the right side. When the two walls are equal, either side is settled, so choosing the right is fine.

Trace ​

Take height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1], positions 0 to 11. The answer should be 6.

lrleft_maxright_maxSide worked onBar examinedWater added
01101left (0 < 1)height[1] = 1, new wall0
11111right (equal)height[10] = 2, new wall0
11012leftheight[2] = 0, dip+1
21012leftheight[3] = 2, new wall0
31022right (equal)height[9] = 1, dip+1
3922rightheight[8] = 2, new wall0
3822rightheight[7] = 3, new wall0
3723leftheight[4] = 1, dip+1
4723leftheight[5] = 0, dip+2
5723leftheight[6] = 1, dip+1
67pointers meet, stop

Total: 1 + 1 + 1 + 2 + 1 = 6. ✓

Complexity, derived ​

Time. Every turn of the loop moves exactly one pointer one step inward, and neither pointer ever moves back. They start n - 1 apart and stop when they meet, so there are at most n - 1 turns. Each turn does one comparison, one move, and one update. So the time is O(n).

Space. Five numbers: l, r, left_max, right_max and trapped. No lists. So the extra memory is O(1), compared with O(n) for Solution 1.

Solution 3 — a monotonic stack, for completeness ​

There is a third way that fills the water in horizontal layers instead of vertical columns. You keep a stack of bars whose heights go down as you move right. A stack is a pile where you can only add or remove at the top. When a taller bar arrives, it closes off a dip. You work out that dip's water from the bar you remove, the new bar, and the bar now on top of the stack.

That is O(n) time but O(n) memory, so it is worse than Solution 2 here. It still matters, because the same machinery solves Largest Rectangle in Histogram, which is built properly in 4.8.7.

Edge cases ​

  • Empty list, or one bar, or two bars. No dip is possible, so the answer is 0.
  • Heights that only go up, like [1, 2, 3], or only go down. One side never has a wall, so the answer is 0.
  • All bars equal. No dips, so the answer is 0.
  • One deep pit, like [5, 0, 5]. The middle holds 5.

What the interviewer will push on ​

"Why can you use left_max without knowing the real tallest bar on the right?" This is the question the problem exists to ask. When left_max < right_max, the real right-hand maximum is at least right_max, which is already bigger. So the smaller wall is left_max, whatever else is out there.

"Show me the version with two lists first." Do this even if they don't ask. Explain the two-list version, then say you can drop the lists by always working on the lower side. Building up to the clever version is far better than jumping to it and getting lost.

"What if the ground were a 2-D grid, not a row of bars?" That is Trapping Rain Water II, and it really is a different problem. In two dimensions, water escapes through the lowest point of the whole rim around it, not the lower of two sides. You work inward from the lowest edge cell using a min-heap, which is a structure that always hands you the smallest item next. See 4.17.

One thing to volunteer: say the per-position formula out loud before writing any code. "The water above position i is the smaller of the two tallest walls, minus height[i]." Everything else follows from that sentence. People who start coding without it usually get lost.

Next: 4.6 Sliding Window. Two pointers again, but now both move forward only, with a rule for when the back one catches up. It is the pattern for every "longest or shortest stretch that satisfies a condition" problem.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet