You are given an
m x n
grid where each cell can have one of three values:
0representing an empty cell,
1representing a fresh orange, or
2representing 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
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 Explanation: The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.
Input: grid = [[0,2]] Output: 0 Explanation: Since there are already no fresh oranges at minute 0, the answer is just 0.
m == grid.length
n == grid[i].length
1 <= m, n <= 10
We can use bread-first search to find out the rotten oranges at each minute.
class Solution: def orangesRotting(self, grid: List[List[int]]) -> int: minutes = -1 queue =  all_empty = True for i in range(len(grid)): for j in range(len(grid)): if grid[i][j] == 2: queue.append((i, j)) all_empty = False elif grid[i][j] == 1: all_empty = False if all_empty: return 0 while queue: minutes += 1 size = len(queue) for _ in range(size): rotten = queue.pop(0) i = rotten j = rotten grid[i][j] = 2 if i - 1 >= 0: left = (i - 1, j) if grid[left][left] == 1 and left not in queue: queue.append(left) if i + 1 <= len(grid) - 1: right = (i + 1, j) if grid[right][right] == 1 and right not in queue: queue.append(right) if j - 1 >= 0: up = (i, j - 1) if grid[up][up] == 1 and up not in queue: queue.append(up) if j + 1 <= len(grid) - 1: down = (i, j + 1) if grid[down][down] == 1 and down not in queue: queue.append(down) for i in range(len(grid)): for j in range(len(grid)): if grid[i][j] == 1: print (i, j) return -1 return minutes
- Time Complexity: O(N^2).
- Space Complexity: O(N^2).