In an m x n grid, each cell is 0 (empty), 1 (fresh orange) or 2 (rotten orange). Every minute, each fresh orange that is next to a rotten one (up, down, left or right) becomes rotten. Return the minimum number of minutes until no fresh orange is left, or -1 if some fresh orange can never rot.
- 1 <= m, n <= 10
- grid[i][j] is 0, 1 or 2
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
Simulating minute by minute and rescanning the whole grid each time costs O((m * n)^2). The spreading is really a multi-source BFS: put every initially rotten orange in the queue as level 0. Each BFS level is one minute, and a fresh orange is reached at exactly the minute it rots. Keep a count of fresh oranges; if it is still positive when the BFS ends, some orange was unreachable.
Algorithm
- Scan the grid: push every rotten cell into a queue and count the fresh ones.
- If there are no fresh oranges, return 0.
- Process the queue one level at a time. For each cell, rot its fresh neighbours, decrease the fresh count and push them.
- After each level that rotted something, add one minute.
- Return the minutes if the fresh count is 0, else
-1.
O(m * n)Space: O(m * n) for the queueclass Solution: def orangesRotting(self, grid: List[List[int]]) -> int: m, n = len(grid), len(grid[0]) queue = deque() fresh = 0 for r in range(m): for c in range(n): if grid[r][c] == 2: queue.append((r, c)) # all sources at once elif grid[r][c] == 1: fresh += 1 minutes = 0 while queue and fresh > 0: for _ in range(len(queue)): # one level = one minute r, c = queue.popleft() for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)): if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == 1: grid[nr][nc] = 2 fresh -= 1 queue.append((nr, nc)) minutes += 1 return minutes if fresh == 0 else -1