Rotting Oranges

The problem description can be found in LeetCode.

Approach

From the input images, it is clear that this is a BFS problem. In fact, at every minute, the rotten oranges could expand at the usual four directions as a single step. This looks like a breadth expansion.

As usual, this is not a clearly implicit Graph problem, but a matrix can be easily adapted to it.

As for 01 Matrix, we can first initialize our queue with the rotten oranges, and then we can expand them by single steps. In the end, if the amount of rotten oranges (from minute 1 on) is equal to the original number of the fresh oranges, then it means that there is not a fresh orange left, so we can return the elapsed time (number of minutes).

Solution

from collections import deque
from enum import Enum
from typing import Deque, Iterator, List, Tuple


class Orange(Enum):
    NONE = 0
    FRESH = 1
    ROTTEN = 2


class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        # not ideal, but just to avoid to have too many function parameters
        self.grid = grid
        self.rows, self.cols = len(grid), len(grid[0])

        num_fresh_oranges = 0
        queue: Deque[Tuple[int, int]] = deque()
        for row in range(self.rows):
            for col in range(self.cols):
                if grid[row][col] == Orange.FRESH.value:
                    num_fresh_oranges += 1
                elif grid[row][col] == Orange.ROTTEN.value:
                    queue.append((row, col))

        num_rotten_oranges, minutes = self.bfs(queue)

        return minutes if num_fresh_oranges == num_rotten_oranges else -1

    def bfs(self, queue: Deque[Tuple[int, int]]) -> Tuple[int, int]:
        minutes = 0
        num_rotten_oranges = 0

        while queue:
            for _ in range(len(queue)):
                row, col = queue.popleft()
                for nbr_row, nbr_col in self.get_neighbors(row, col):
                    self.grid[nbr_row][nbr_col] = Orange.ROTTEN.value
                    queue.append((nbr_row, nbr_col))
                    num_rotten_oranges += 1

            if queue:
                minutes += 1

        return num_rotten_oranges, minutes

    def get_neighbors(self, row: int, col: int) -> Iterator[Tuple[int, int]]:
        deltas = [
            (-1, 0),  # up
            (+1, 0),  # down
            (0, -1),  # left
            (0, +1),  # right
        ]
        for dt_row, dt_col in deltas:
            nbr_row = row + dt_row
            nbr_col = col + dt_col

            if (
                0 <= nbr_row < self.rows
                and 0 <= nbr_col < self.cols
                and self.grid[nbr_row][nbr_col] == Orange.FRESH.value
            ):
                yield nbr_row, nbr_col

Complexity

• Time: $O(mn)$
• Space: $O(mn)$

Where $m$ and $n$ are the number of rows and columns of the input grid, respectively.