LeetCode 994 Rotting Oranges - Algorithm

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 $0$. Run BFS level by level. When the queue empties, if any fresh oranges remain, return $-1$. Otherwise return the maximum time.

This runs in $O(m \times n)$ time and space.