Rotting Oranges

Problem

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.

Pattern

Array, Breadth-First Search, Matrix

Approaches

BFS

Explanation

Starting from all the rotten oranges, each iteration, we need to rot all fresh neighboring oranges. This behavior matches BFS. We start with the initial rotten oranges in the queue. While the queue is nonempty, we pop an orange and rot its fresh neighbors. To track when each orange was rot, we store the minute the rot reached the orange with the orange position in the queue: (i, j, minute + 1) where minute is the time the popped orange was rotted. The initial rotten oranges have minute = 0.

The time required to rot all the oranges is the maximum minute value. We track this value in a variable max_minutes which we update using

max_minutes = max(max_minutes, minutes)

When the queue is empty, we check for any fresh oranges. If so we return -1. Otherwise we return max_minutes.

Code

from collections import deque


def orangesRotting(grid: list[list[int]]) -> int:
    """Return the minimum number of minutes that must elapse until no cell has
    a fresh orange.
    """
    M = len(grid)
    N = len(grid[0])

    rotten_locs = []
    fresh_locs = []
    for i in range(M):
        for j in range(N):
            if grid[i][j] == 1:
                fresh_locs.append((i, j))
            if grid[i][j] == 2:
                rotten_locs.append((i, j))

    queue = deque()
    for i, j in rotten_locs:
        queue.append((i - 1, j, 0))
        queue.append((i + 1, j, 0))
        queue.append((i, j - 1, 0))
        queue.append((i, j + 1, 0))

    visited = set()
    max_minutes = 0
    while queue:
        i, j, minutes = queue.popleft()

        if not (0 <= i < M and 0 <= j < N):
            continue

        if (i, j) in visited:
            continue

        if grid[i][j] == 0 or grid[i][j] == 2:
            continue

        grid[i][j] = 2
        max_minutes = max(max_minutes, minutes + 1)
        queue.append((i - 1, j, minutes + 1))
        queue.append((i + 1, j, minutes + 1))
        queue.append((i, j + 1, minutes + 1))
        queue.append((i, j - 1, minutes + 1))

    for i, j in fresh_locs:
        if grid[i][j] == 1:
            return -1

    return max_minutes

Test

>>> from rotting_oranges__bfs import orangesRotting
>>> orangesRotting([[2,1,1],[1,1,0],[0,1,1]])
4
>>> orangesRotting([[2,1,1],[0,1,1],[1,0,1]])
-1
>>> orangesRotting([[0,2]])
0

Complexity

Measure	Complexity	Notes
Time	\(O(mn)\)	need to go through to whole grid to identify initial rotten oranges
Auxiliary Space	\(O(mn)\)	all cells could be rotten oranges leading the queue to contain every cell

rotting_oranges__bfs.orangesRotting(grid: list[list[int]]) → int: Return the minimum number of minutes that must elapse until no cell has a fresh orange.