Here is the algorithm:
// Step 1: Initialize
queue = empty
fresh_count = 0
for each cell (r, c) in grid:
if grid[r][c] == 2:
queue.push((r, c, 0))
else if grid[r][c] == 1:
fresh_count = fresh_count + 1
// Step 2: Multi-source BFS
max_time = 0
while queue is not empty:
(r, c, time) = queue.pop_front()
max_time = max(max_time, time)
for each neighbor (nr, nc) of (r, c):
if grid[nr][nc] == 1:
grid[nr][nc] = 2
fresh_count = fresh_count - 1
queue.push((nr, nc, time + 1))
// Step 3: Check result
if fresh_count > 0:
return -1
return max_time
Push all initially rotten oranges with time . Run BFS level by level. When the queue empties, if any fresh oranges remain, return . Otherwise return the maximum time.
This runs in time and space.