# LeetCode 994. Rotting Oranges

## Description

https://leetcode.com/problems/rotting-oranges/

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

Example 1:

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

Example 2:

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

Example 3:

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

## Explanation

We can use bread-first search to find out the rotten oranges at each minute.

## Python Solution

``````class Solution:
def orangesRotting(self, grid: List[List[int]]) -> int:
minutes = -1
queue = []

all_empty = True
for i in range(len(grid)):
for j in range(len(grid)):
if grid[i][j] == 2:
queue.append((i, j))
all_empty = False
elif grid[i][j] == 1:
all_empty = False

if all_empty:
return 0

while queue:
minutes += 1

size = len(queue)
for _ in range(size):
rotten = queue.pop(0)

i = rotten
j = rotten

grid[i][j] = 2

if i - 1 >= 0:
left = (i - 1, j)
if grid[left][left] == 1 and left not in queue:
queue.append(left)

if i + 1 <= len(grid) - 1:
right = (i + 1, j)
if grid[right][right] == 1 and right not in queue:
queue.append(right)

if j - 1 >= 0:
up = (i, j - 1)
if grid[up][up] == 1 and up not in queue:
queue.append(up)

if j + 1 <= len(grid) - 1:
down = (i, j + 1)
if grid[down][down] == 1 and down not in queue:
queue.append(down)

for i in range(len(grid)):
for j in range(len(grid)):
if grid[i][j] == 1:
print (i, j)

return -1

return minutes
``````
• Time Complexity: O(N^2).
• Space Complexity: O(N^2).