Editorial: Rotting Oranges

1 Intuition

Rot spreads like a multi-source BFS, one layer per minute.

2 Approach

Start a BFS from all rotten oranges at once and count layers until no fresh orange is left.

3 Complexity Analysis

Time O(rows·cols), Space O(rows·cols).

4 Solution Code

class Solution:
    def orangesRotting(self, grid: list[list[int]]) -> int:
        rows, cols = len(grid), len(grid[0])
        g = [row[:] for row in grid]
        frontier = [(r, c) for r in range(rows) for c in range(cols) if g[r][c] == 2]
        fresh = sum(row.count(1) for row in g)
        minutes = 0
        while frontier and fresh:
            nxt = []
            for r, c in frontier:
                for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < rows and 0 <= nc < cols and g[nr][nc] == 1:
                        g[nr][nc] = 2
                        fresh -= 1
                        nxt.append((nr, nc))
            frontier = nxt
            minutes += 1
        return -1 if fresh else minutes

5 Code Walkthrough

The reference solution below implements the approach step by step.