The problem
Each cell of a grid is 0 (empty), 1 (a fresh orange) or 2 (a rotten one). Every minute, each fresh orange next to a rotten one (up, down, left, right) rots.
Return the number of minutes until no fresh orange is left, or −1 if some can never rot.
Examples
- Input
grid = [[2, 1, 1], [1, 1, 0], [0, 1, 1]]
- Output
4
- Input
grid = [[2, 1, 1], [0, 1, 1], [1, 0, 1]]
- Output
-1
- Input
grid = [[0, 2]]
- Output
0
Constraints
- 1 ≤ m, n ≤ 10
- Each cell is 0, 1 or 2.
The idea
The rot spreads in rings, one step a minute — which is exactly how breadth-first search explores: everything one step away, then everything two steps away. Start it from every rotten orange at once (a “multi-source” search), with all of them in the queue.
Each round of the queue is one minute: every orange rotted in that round was fresh and next to one rotted the round before. Count fresh oranges down as they rot; if the queue empties with some left, they are cut off by empty cells: −1.
- Time
- O(m · n)
- Space
- O(m · n) — the queue
Solution · every language run against every case
class Solution: def orangesRotting(self, grid: List[List[int]]) -> int: rows, cols = len(grid), len(grid[0]) rotten = deque((r, c) for r in range(rows) for c in range(cols) if grid[r][c] == 2) fresh = sum(row.count(1) for row in grid) minutes = 0 # Breadth-first from every rotten orange at once: each round is one minute. while rotten and fresh: for _ in range(len(rotten)): i, j = rotten.popleft() for x, y in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)): if 0 <= x < rows and 0 <= y < cols and grid[x][y] == 1: grid[x][y] = 2 fresh -= 1 rotten.append((x, y)) minutes += 1 return -1 if fresh else minutes