> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Trapping Rain Water II Python Solution

> Tested Python solution for LeetCode 407 with 15 pytest cases. Generate a practice environment with lcpy.

LeetCode 407, [Hard](/catalog/hard). Topics: [Array](/catalog/topics/array), [Breadth-First Search](/catalog/topics/breadth-first-search), [Heap (Priority Queue)](/catalog/topics/heap-priority-queue), [Matrix](/catalog/topics/matrix). [View on LeetCode](https://leetcode.com/problems/trapping-rain-water-ii/description/).

Generate this problem as a practice environment: tested reference solution, 15 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 407   # by problem number
lcpy gen -s trapping_rain_water_ii   # by problem name
```

## Problem

Given an `m x n` integer matrix `heightMap` representing the height of each unit cell in a 2D elevation map, return *the volume of water it can trap after raining*.

### Examples

![Example 1](https://assets.leetcode.com/uploads/2021/04/08/trap1-3d.jpg)

```
Input: heightMap = [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]]
Output: 4
Explanation: After the rain, water is trapped between the blocks.
We have two small ponds 1 and 3 units trapped.
The total volume of water trapped is 4.
```

![Example 2](https://assets.leetcode.com/uploads/2021/04/08/trap2-3d.jpg)

```
Input: heightMap = [[3,3,3,3,3],[3,2,2,2,3],[3,2,1,2,3],[3,2,2,2,3],[3,3,3,3,3]]
Output: 10
```

### Constraints

* `m == heightMap.length`
* `n == heightMap[i].length`
* `1 <= m, n <= 200`
* `0 <= heightMap[i][j] <= 2 * 10^4`

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/trapping_rain_water_ii/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/trapping_rain_water_ii/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
import heapq


class Solution:
    # Time: O(m*n*log(m*n))
    # Space: O(m*n)
    def trap_rain_water(self, height_map: list[list[int]]) -> int:
        m, n = len(height_map), len(height_map[0])
        if m < 3 or n < 3:
            return 0
        visited = [[False] * n for _ in range(m)]
        heap: list[tuple[int, int, int]] = []
        for i in range(m):
            for j in (0, n - 1):
                heapq.heappush(heap, (height_map[i][j], i, j))
                visited[i][j] = True
        for j in range(n):
            for i in (0, m - 1):
                if not visited[i][j]:
                    heapq.heappush(heap, (height_map[i][j], i, j))
                    visited[i][j] = True
        total = 0
        while heap:
            wall, i, j = heapq.heappop(heap)
            for di, dj in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                ni, nj = i + di, j + dj
                if 0 <= ni < m and 0 <= nj < n and not visited[ni][nj]:
                    visited[ni][nj] = True
                    total += max(0, wall - height_map[ni][nj])
                    heapq.heappush(heap, (max(wall, height_map[ni][nj]), ni, nj))
        return total
```

## Complexity

| Time | Space |
| - | - |
| O(m*n*log(m\*n)) | O(m\*n) |

## Tags

[NeetCode All](/catalog/neetcode).


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.