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

# Rotting Oranges Python Solution with Tests

> Tested Python solution for LeetCode 994 with 11 pytest cases. Generate a practice environment with lcpy.

LeetCode 994, Medium. Topics: Array, Breadth-First Search, Matrix. [View on LeetCode](https://leetcode.com/problems/rotting-oranges/description/).

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

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

## Problem

You are given an `m x n` `grid` where each cell can have one of three values:

* `0` representing an empty cell,
* `1` representing a fresh orange, or
* `2` representing a rotten orange.

Every minute, any fresh orange that is **4-directionally adjacent** to a rotten orange becomes rotten.

Return *the minimum number of minutes that must elapse until no cell has a fresh orange*. If *this is impossible, return* `-1`.

### Examples

![Example 1](https://assets.leetcode.com/uploads/2019/02/16/oranges.png)

```
Input: grid = [[2,1,1],[1,1,0],[0,1,1]]
Output: 4
```

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

**Explanation:** The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.

```
Input: grid = [[0,2]]
Output: 0
```

**Explanation:** Since there are already no fresh oranges at minute 0, the answer is just 0.

### Constraints

* `m == grid.length`
* `n == grid[i].length`
* `1 <= m, n <= 10`
* `grid[i][j]` is `0`, `1`, or `2`.

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/rotting_oranges/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/rotting_oranges/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 oranges_rotting(self, grid: list[list[int]]) -> int:
        EMPTY, FRESH, ROTTEN = 0, 1, 2  # noqa: N806
        _ = EMPTY

        m, n = len(grid), len(grid[0])
        queue: deque[tuple[int, int]] = deque()
        fresh = 0

        # Find all rotten oranges and count fresh ones
        for i in range(m):
            for j in range(n):
                if grid[i][j] == ROTTEN:
                    queue.append((i, j))
                elif grid[i][j] == FRESH:
                    fresh += 1

        if fresh == 0:
            return 0

        minutes = 0
        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]

        while queue:
            size = len(queue)
            for _ in range(size):
                x, y = queue.popleft()
                for dx, dy in directions:
                    nx, ny = x + dx, y + dy
                    if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == FRESH:
                        grid[nx][ny] = ROTTEN
                        fresh -= 1
                        queue.append((nx, ny))

            if queue:
                minutes += 1

        return minutes if fresh == 0 else -1
```

## Complexity

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

## Tags

[Grind 75](/catalog/grind-75), [Grind](/catalog/grind), [NeetCode 150](/catalog/neetcode-150), [NeetCode 250](/catalog/neetcode-250), [NeetCode All](/catalog/neetcode), [AlgoMaster 75](/catalog/algo-master-75).