You are given an m x n
grid
where each cell can have one of three values:
0
representing an empty cell,1
representing a fresh orange, or2
representing 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 -1
.
For example, consider the following grid:
[[2,1,1],
[1,1,0],
[0,1,1]]
In this case, the function should return 4
, because it takes 4 minutes for all the fresh oranges to become rotten. Let's consider another example:
[[2,1,1],
[0,1,1],
[1,0,1]]
Here, the function should return -1
, because the orange in the bottom-left corner will never become rotten. Write an efficient algorithm to solve this problem. Consider edge cases, such as grids with no fresh oranges or no rotten oranges.
You are given an m x n
grid
where each cell can have one of three values:
0
representing an empty cell,1
representing a fresh orange, or2
representing 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 -1
.
A brute-force approach would involve iterating through the grid at each minute, identifying all rotten oranges, and then checking their neighbors to rot any fresh oranges. This process continues until no more fresh oranges can be rotten.
This approach is inefficient because it rescans the entire grid at each step, even if only a few oranges have been freshly rotten.
Time Complexity: O(T * m * n), where T is the number of minutes and m * n is the size of the grid. In the worst case, T could be proportional to m * n.
Space Complexity: O(m * n) in the worst case, if you need to maintain a copy of the grid to track changes.
A better approach involves using Breadth-First Search (BFS).
This approach optimizes the process by exploring oranges layer by layer, ensuring that oranges rot in the correct order.
Big O Time Complexity: O(m * n), where m * n is the size of the grid, as each cell is visited at most a constant number of times.
Big O Space Complexity: O(m * n) in the worst-case scenario, where the queue might contain all the cells in the grid.
from collections import deque
def oranges_rotting(grid):
rows, cols = len(grid), len(grid[0])
queue = deque()
fresh_oranges = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] == 2:
queue.append((r, c, 0)) # (row, col, time)
elif grid[r][c] == 1:
fresh_oranges += 1
if not queue and fresh_oranges > 0:
return -1
minutes = 0
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
while queue:
r, c, time = queue.popleft()
minutes = time
for dr, dc in directions:
new_r, new_c = r + dr, c + dc
if (0 <= new_r < rows and 0 <= new_c < cols and grid[new_r][new_c] == 1):
grid[new_r][new_c] = 2 # Rot the orange
fresh_oranges -= 1
queue.append((new_r, new_c, time + 1))
if fresh_oranges > 0:
return -1
else:
return minutes