Introduction

The usual "trapping rain water" problem becomes more interesting in 3D terrain because water can leak out in multiple directions. In the common algorithmic version, you are given a 2D grid of heights, and the goal is to compute how much water can be held above the cells after rainfall. The correct solution is not based on local neighbors alone; it depends on the lowest boundary that water can escape through.

Model the Terrain Correctly

Even though the title says 3D, the input is normally a 2D height map where each cell value represents elevation in the third dimension. Water is trapped on top of that surface, so the total trapped volume is the sum of water units above all cells.

For example, this terrain:

1 4 3 1 3 2
3 2 1 3 2 4
2 3 3 2 3 1

can trap water in some interior cells because the outer boundary is high enough to contain it.

The core insight is that the water level of a cell is determined by the minimum boundary height that can reach it from the outside. That is why a simple "compare to four neighbors" rule is not sufficient.

Use a Boundary-First Min-Heap Algorithm

The standard solution uses a min-heap seeded with all boundary cells. From there, you repeatedly expand inward from the currently lowest boundary. This works because the lowest boundary seen so far determines the maximum water level reachable without spilling.

The steps are:

1. push all outer cells into a min-heap
2. mark them as visited
3. pop the lowest boundary cell
4. inspect its four neighbors
5. if a neighbor is lower, trap the height difference as water
6. push the neighbor back with effective height max(current_boundary, neighbor_height)

Here is a runnable Python implementation:

1import heapq
2
3
4def trap_rain_water(height_map):
5    if not height_map or not height_map[0]:
6        return 0
7
8    rows = len(height_map)
9    cols = len(height_map[0])
10
11    if rows < 3 or cols < 3:
12        return 0
13
14    visited = [[False] * cols for _ in range(rows)]
15    heap = []
16
17    for r in range(rows):
18        for c in (0, cols - 1):
19            heapq.heappush(heap, (height_map[r][c], r, c))
20            visited[r][c] = True
21
22    for c in range(1, cols - 1):
23        for r in (0, rows - 1):
24            heapq.heappush(heap, (height_map[r][c], r, c))
25            visited[r][c] = True
26
27    trapped = 0
28    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
29
30    while heap:
31        height, r, c = heapq.heappop(heap)
32
33        for dr, dc in directions:
34            nr, nc = r + dr, c + dc
35            if nr < 0 or nr >= rows or nc < 0 or nc >= cols:
36                continue
37            if visited[nr][nc]:
38                continue
39
40            visited[nr][nc] = True
41            neighbor_height = height_map[nr][nc]
42            trapped += max(0, height - neighbor_height)
43            heapq.heappush(heap, (max(height, neighbor_height), nr, nc))
44
45    return trapped
46
47
48grid = [
49    [1, 4, 3, 1, 3, 2],
50    [3, 2, 1, 3, 2, 4],
51    [2, 3, 3, 2, 3, 1],
52]
53
54print(trap_rain_water(grid))

This prints 4, which is the trapped water volume for that sample.

Why the Heap Approach Works

The algorithm works for the same reason Dijkstra-style frontier expansion works in shortest path problems: you always process the next most restrictive boundary first. When a low wall is reached, it limits water level for any connected interior region.

If you tried to compute water using only local maxima around each cell, you would overestimate in cases where water can escape through a distant low boundary. The heap prevents that by building the reachable basin from the outside inward.

Time complexity is O(m * n * log(m * n)) because each cell enters the heap once, and each heap operation costs logarithmic time. Space complexity is O(m * n) for the heap and visited grid.

Test with Edge Cases

Before trusting the implementation, run small edge cases:

1print(trap_rain_water([[1]]))  # 0
2print(trap_rain_water([[1, 2], [3, 4]]))  # 0
3print(trap_rain_water([
4    [5, 5, 5],
5    [5, 1, 5],
6    [5, 5, 5],
7]))  # 4

These checks catch two common mistakes:

• forgetting that grids smaller than 3 x 3 cannot trap water
• pushing cells with the wrong effective height back into the heap

For production code, unit tests should include irregular basins, multiple compartments, and flat boundaries.

When This Model Does Not Apply

This algorithm is for axis-aligned grid terrain. It does not directly solve continuous mesh simulation, fluid dynamics, or real-world hydrology with evaporation, flow speed, or porous materials. It is an algorithmic volume computation over a discrete height map.

That distinction matters. If the real problem is physical simulation, this heap-based method is a useful abstraction, not a physics engine.

Common Pitfalls

• Treating the problem like the 1D rainwater problem and comparing only local neighbors.
• Forgetting to seed the heap with every boundary cell before exploring inward.
• Pushing the neighbor's raw height instead of the effective boundary height max(current, neighbor).
• Failing to mark visited cells at the right time and processing cells more than once.
• Expecting this discrete algorithm to model full real-world fluid simulation behavior.

Summary

• The 3D rainwater volume problem is usually a 2D height map with water trapped above it.
• The correct solution is boundary-driven, not purely local.
• A min-heap over boundary cells gives the standard efficient algorithm.
• Each interior cell is evaluated against the lowest escape boundary discovered so far.
• Test edge cases carefully because small mistakes in heap updates lead to large overcounts.