> ## 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.

# Walls And Gates Python Solution with Tests

> Tested Python solution for LeetCode 286 with 17 pytest cases. Generate a practice environment with lcpy.

LeetCode 286, Medium. Topics: Array, Breadth-First Search, Matrix. [View on LeetCode](https://leetcode.com/problems/walls-and-gates/description/).

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

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

## Problem

You are given a `m × n` 2D grid initialized with these three possible values:

* `-1` - A wall or obstacle that can not be traversed.
* `0` - A gate.
* `INF` - Infinity an empty room. We use the value `2^31 - 1 = 2147483647` to represent `INF`.

Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled with `INF`.

**Follow up:** Can you solve it in-place and in O(m × n) time complexity?

### Examples

```
Input: rooms = [[2147483647,-1,0,2147483647],[2147483647,2147483647,2147483647,-1],[2147483647,-1,2147483647,-1],[0,-1,2147483647,2147483647]]
Output: [[3,-1,0,1],[2,2,1,-1],[1,-1,2,-1],[0,-1,3,4]]
```

**Explanation:** the 2D grid is:

```
INF  -1   0   INF
INF  INF  INF  -1
INF  -1   INF  -1
  0  -1   INF  INF
```

the result is:

```
 3  -1   0   1
 2   2   1  -1
 1  -1   2  -1
 0  -1   3   4
```

explanation: the gate is located at (0,2), (3,0), (3,3). the room at (0,0) is distance 3 from the nearest gate at (3,0).

```
Input: rooms = [[0,-1],[2147483647,2147483647]]
Output: [[0,-1],[1,2]]
```

### Constraints

* `m == rooms.length`
* `n == rooms[i].length`
* `1 <= m, n <= 100`
* `rooms[i][j]` is one of `-1`, `0`, or `2147483647`.

## Solution

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

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
from collections import deque


class Solution:
    # Time: O(m * n)
    # Space: O(m * n)
    def walls_and_gates(self, rooms: list[list[int]]) -> None:
        if not rooms or not rooms[0]:
            return

        rows, cols = len(rooms), len(rooms[0])
        queue: deque[tuple[int, int]] = deque()
        for r in range(rows):
            for c in range(cols):
                if rooms[r][c] == 0:
                    queue.append((r, c))

        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        while queue:
            r, c = queue.popleft()
            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and rooms[nr][nc] == 2147483647:
                    rooms[nr][nc] = rooms[r][c] + 1
                    queue.append((nr, nc))
```

## Complexity

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

## Tags

[NeetCode 150](/catalog/neetcode-150), [NeetCode 250](/catalog/neetcode-250), [NeetCode All](/catalog/neetcode).