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

Multi Source BFS

Code

from collections import deque


def orangesRotting(grid: list[list[int]]) -> int:
    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__multi_source_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

rotting_oranges__multi_source_bfs.orangesRotting(grid: list[list[int]]) → int