Rotting Oranges
You are given a 2D grid of integers representing a box of oranges. Each cell in the grid can be one of the following:
- 0 → an empty cell
- 1 → a fresh orange
- 2 → a rotten orange
Every minute, any fresh orange that is adjacent (up, down, left, or right) to a rotten orange will become rotten.
Your task is to determine the minimum number of minutes required for all fresh oranges to become rotten. If it is not possible to rot all fresh oranges, return -1.
Example
Input: grid = [ [2,1,0], [0,1,1], [1,1,2] ] Output: 2
Explanation:
Minute 0 (initial): [[2 1 0] [0 1 1] [1 1 2]] Minute 1: Oranges adjacent to rotten at (0,0): (0,1) Oranges adjacent to rotten at (2,2): (1,2), (2,1) Resulting grid: [[2 2 0] [0 1 2] [1 2 2]] Minute 2: Oranges adjacent to rotten at (0,1): none (only neighbors are (0,0) rotten, (0,2) empty, (1,1) fresh) Oranges adjacent to rotten at (1,2): (1,1) Oranges adjacent to rotten at (2,1): (2,0) Resulting grid: [[2 2 0] [0 2 2] [2 2 2]]
We will use BFS approach as the rotting process spreads level by level, minute by minute.
Algorithm
-
Traverse the grid to count all fresh oranges and add all initial rotten oranges to a queue.
-
Use BFS to process the queue minute by minute.
-
In each minute, for every rotten orange in the queue, rot its adjacent fresh oranges and add them to the queue.
-
Track time elapsed and reduce the fresh orange count as they rot.
-
When the queue is empty:
If all fresh oranges are rotted, return the time taken.
Otherwise, return -1 (some fresh oranges are unreachable).
from collections import deque
from typing import List
def rotting_oranges(grid: List[List[int]]) -> int:
rows, cols = len(grid), len(grid[0])
q = deque()
visited = set()
fresh_oranges = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] == 1:
fresh_oranges += 1
elif grid[r][c] == 2:
q.append((r,c))
def bfs(q, fresh_oranges):
time = 0
while q and fresh_oranges:
time += 1
for _ in range(len(q)):
r,c = q.popleft()
for nr, nc in [(r+1,c), (r-1,c), (r,c+1), (r,c-1)]:
if 0<=nr<rows and 0<=nc<cols and grid[nr][nc] == 1 and (nr, nc) not in visited:
fresh_oranges -= 1
grid[nr][nc] = 2
q.append((nr, nc))
visited.add((nr, nc))
return time, fresh_oranges
time, fresh_oranges = bfs(q, fresh_oranges)
if fresh_oranges == 0:
return time
return -1Time Complexity: O(N×M). We visit each cell at most once.
Space Complexity: O(N×M). For the queue and visited set in the worst case.