Generated by Codex with GPT-5

Quick facts

  • Difficulty: HARD
  • Problem: Trapping Rain Water II
  • Main tags: Array, Breadth-First Search, Heap (Priority Queue), Matrix
  • Frequency in source list: 17.6

What the problem is really asking

This is the 2D version of Trapping Rain Water.

Instead of one row of bars, there is a full grid of elevations. After rain falls, water can sit on low cells, but only if every path from that cell to the outer border is blocked by walls that are high enough.

That last part is the real difficulty. In one dimension, water at an index is controlled by the tallest wall on the left and the tallest wall on the right. In two dimensions, water can escape in many directions, including around corners, so the answer is not determined by just looking up, down, left, and right independently.

The real question is:

“For each cell, what is the lowest boundary height that still blocks every escape path to the edge?”

If the cell is below that boundary, it can hold water up to that level. If not, it cannot trap anything.

Why the obvious extension from 1D fails

A common first idea is to compute something like:

  • tallest wall to the left
  • tallest wall to the right
  • tallest wall above
  • tallest wall below

and then take the minimum of those four values.

That sounds reasonable, but it is wrong because water does not have to leave in a straight line. A cell might look enclosed from the four cardinal directions and still leak through a winding path of lower cells that eventually reaches the border.

So this problem is not about four directional maxima. It is about the best escape path to the outside.

The key insight: flood from the boundary inward

Boundary cells can never hold water because water can always spill off the map there.

That means the outer border should be treated as the initial boundary of the basin. From there, the algorithm works inward.

The crucial rule is this:

always expand from the currently lowest boundary cell first.

Why? Because the lowest boundary is the first place where water would leak out. If that boundary is height h, then any unvisited neighbor next to it can hold at most h units of water level. So:

  • if the neighbor’s ground height is below h, it traps h - neighbor_height
  • whether it trapped water or not, that neighbor now becomes part of the boundary
  • its effective boundary height becomes max(neighbor_height, h)

That last line is the whole algorithm in one sentence. A flooded low cell behaves like a wall at the filled water level, not at its original ground level.

How to derive the optimal solution

  1. Put every perimeter cell into a min-heap and mark it visited.
  2. Repeatedly pop the cell with the smallest current boundary height.
  3. Look at its four neighbors that have not been visited yet.
  4. If a neighbor is lower than the current boundary, add the height difference to the answer.
  5. Push that neighbor into the heap with effective height max(current_boundary_height, neighbor_height).
  6. Continue until every cell has been processed.

This is essentially a multi-source Dijkstra traversal where the “distance” is not sum of edge weights, but the minimum possible boundary level needed to reach a cell from the outside.

Each cell enters the heap once and leaves once, so the complexity is:

  • Time: O(m * n * log(m * n))
  • Extra space: O(m * n)

For the standard interview version, this is the right final answer.

A useful mental model

Imagine pouring water in from above while the whole terrain is surrounded by open air.

The border acts like the rim of a container, except the rim is uneven. The lowest exposed part of that rim determines where water would spill first. Once that lowest point is handled, the next-lowest boundary becomes the limiting factor, and so on.

The min-heap keeps those boundary cells in exactly the order needed.

That is why this problem feels like a shortest-path problem even though no path length is being added. The heap is enforcing the correct leak order.

Python solution

The implementation below keeps the LeetCode wrapper small and moves the core logic into helpers. The important detail is that each neighbor is pushed back with its effective boundary height, not just its raw ground height.

from heapq import heappop, heappush
from typing import Iterator, List, Tuple


Cell = Tuple[int, int, int]


def should_return_zero(height_map: List[List[int]]) -> bool:
    return (
        not height_map
        or not height_map[0]
        or len(height_map) < 3
        or len(height_map[0]) < 3
    )


def neighbor_positions(row: int, col: int) -> Iterator[Tuple[int, int]]:
    yield row - 1, col
    yield row + 1, col
    yield row, col - 1
    yield row, col + 1


def push_perimeter_cells(
    height_map: List[List[int]],
    visited: List[List[bool]],
    boundary_heap: List[Cell],
) -> None:
    total_rows = len(height_map)
    total_cols = len(height_map[0])

    for row in range(total_rows):
        push_cell_if_needed(height_map, visited, boundary_heap, row, 0)
        push_cell_if_needed(height_map, visited, boundary_heap, row, total_cols - 1)

    for col in range(total_cols):
        push_cell_if_needed(height_map, visited, boundary_heap, 0, col)
        push_cell_if_needed(height_map, visited, boundary_heap, total_rows - 1, col)


def push_cell_if_needed(
    height_map: List[List[int]],
    visited: List[List[bool]],
    boundary_heap: List[Cell],
    row: int,
    col: int,
) -> None:
    if visited[row][col]:
        return

    visited[row][col] = True
    heappush(boundary_heap, (height_map[row][col], row, col))


def is_inside(height_map: List[List[int]], row: int, col: int) -> bool:
    return 0 <= row < len(height_map) and 0 <= col < len(height_map[0])


def compute_trapped_water(height_map: List[List[int]]) -> int:
    if should_return_zero(height_map):
        return 0

    total_rows = len(height_map)
    total_cols = len(height_map[0])
    visited = [[False] * total_cols for _ in range(total_rows)]
    boundary_heap: List[Cell] = []

    push_perimeter_cells(height_map, visited, boundary_heap)

    total_trapped_water = 0

    while boundary_heap:
        current_boundary_height, row, col = heappop(boundary_heap)

        for neighbor_row, neighbor_col in neighbor_positions(row, col):
            if not is_inside(height_map, neighbor_row, neighbor_col):
                continue

            if visited[neighbor_row][neighbor_col]:
                continue

            visited[neighbor_row][neighbor_col] = True

            neighbor_ground_height = height_map[neighbor_row][neighbor_col]
            trapped_here = max(0, current_boundary_height - neighbor_ground_height)
            total_trapped_water += trapped_here

            # Once flooded, the neighbor becomes part of the surrounding boundary.
            effective_neighbor_height = max(
                neighbor_ground_height,
                current_boundary_height,
            )
            heappush(
                boundary_heap,
                (effective_neighbor_height, neighbor_row, neighbor_col),
            )

    return total_trapped_water


class Solution:
    def trapRainWater(self, heightMap: List[List[int]]) -> int:
        return compute_trapped_water(heightMap)

Why this works

At any moment, the heap contains the current frontier between processed cells and unprocessed cells.

Because the heap always removes the lowest frontier cell first, the algorithm never skips over a cheaper escape boundary in favor of a taller one. So when a neighbor is first reached, the current popped height is the smallest possible boundary level through which the outside world can reach that neighbor.

That is exactly the level that determines how much water the neighbor can hold.

If the neighbor is lower, the difference is trapped water. If it is higher, no water is trapped there, but the higher ground now becomes the new local wall. Either way, pushing max(neighbor_height, current_boundary_height) preserves the correct frontier for later cells.

This is the same correctness pattern as Dijkstra’s algorithm:

  • process states in the safest order
  • finalize a state the first time it is popped
  • propagate the best known constraint to neighbors

The only difference is that the propagated value is a water boundary level instead of a path sum.

Interview follow-ups

Why is a min-heap necessary? Why not use a normal queue or DFS?

A plain queue or DFS does not respect boundary height order. That matters because the amount of water above a cell is determined by the lowest escape boundary, not by whichever boundary path happens to be explored first. If a taller wall is explored before a shorter leak path, the algorithm can overcount.

A min-heap fixes that by always expanding the smallest current boundary first. That guarantees each cell is first visited using the correct limiting boundary level. The tradeoff is the log(m * n) heap factor, but that is exactly what makes the solution correct and standard for this problem.

Could the algorithm return the water trapped at each cell, not just the total?

Yes. The traversal stays the same. The only extra step is to maintain another matrix, for example water_depth[row][col], and when a neighbor is visited store max(0, current_boundary_height - neighbor_ground_height) there before pushing the neighbor into the heap.

That works because the first time a cell is visited, its limiting outside boundary is already finalized. So the per-cell trapped depth is finalized at the same moment. The complexity stays O(m * n * log(m * n)) time, with one more O(m * n) matrix of storage.

Why is it safe to mark a cell visited as soon as it is pushed?

It is safe because a cell is pushed from the smallest boundary that could possibly reach it first. Any later attempt to reach that same cell would come from an equal or higher frontier cell, since the heap processes frontier heights in ascending order.

So there is no better boundary level waiting to discover that cell later. Marking visited on push avoids duplicate heap entries and keeps the implementation simpler. The reasoning is the same as saying that once the minimum feasible outside boundary for a cell has been determined, extra rediscoveries cannot improve it.

Can the log factor be removed?

In the standard comparison-based version, the heap-based solution is the accepted optimal answer. The algorithm needs an ordered frontier so it can always expand the lowest current boundary next, and a binary heap gives that cleanly.

There are specialized cases where the constant factors or even the ordering structure can change. For example, if heights are known to come from a very small bounded integer range, a bucketed priority queue can sometimes replace the binary heap. But for the normal interview problem, O(m * n * log(m * n)) with a min-heap is the right answer to defend.

Practical takeaway

This problem becomes much easier once it is viewed as “water escapes through the lowest boundary first.”

From there, the solution is systematic:

  • start from the perimeter
  • process the lowest boundary cell first
  • flood lower neighbors up to that boundary
  • turn each visited neighbor into a new boundary cell

That outside-in heap traversal is the main pattern worth remembering.