Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Water can escape through the map's boundary, so an interior cell's capacity depends on the lowest barrier connecting it to that boundary. Imagine flooding inward from all boundary cells, always expanding the lowest available frontier. The greatest frontier height crossed so far is the current water level; newly reached lower terrain can hold the difference.

Approach

Insert every boundary cell into a min-heap and mark it visited by replacing its input height with -1, which cannot be an original height.
Pop the lowest frontier cell and raise the running level to the maximum of its height and the previous level.
For each unvisited in-bounds neighbor, add max(0, level - neighborHeight) to the trapped volume. Push its original height into the heap and mark it immediately, preventing duplicate counting.
Continue until the frontier is empty. Low cells behind a crossed barrier are filled at that barrier's level before expansion can cross a higher one. This implementation stores raw heights in the heap and a separate running level, and it mutates the grid to record visits.

class Solution:
    def trapRainWater(self, heightMap: List[List[int]]) -> int:
        n = len(heightMap)
        m = len(heightMap[0])
        h = []

        for i in range(n):
            for j in range(m):
                if i == 0 or j == 0 or i == n - 1 or j == m - 1:
                    heapq.heappush(h, (heightMap[i][j], i, j))
                    heightMap[i][j] = -1

        res = 0
        level = 0

        while h:
            height, i, j = heapq.heappop(h)
            level = max(level, height)
            for ni, nj in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
                if ni < 0 or ni >= n or nj < 0 or nj >= m:
                    continue # out of bounds
                curr = heightMap[ni][nj]
                if curr == -1:
                    continue # already seen
                if level > curr:
                    res += level - curr
                heapq.heappush(h, (curr, ni, nj))
                heightMap[ni][nj] = -1

        return res

Complexity analysis

Let N = R × C be the number of grid cells. Every cell is inserted into and removed from the heap once, giving O(N log N) time and O(N) auxiliary space.