Rotting oranges

Multi-source BFS on a grid: every rotten orange spreads to its fresh neighbours at the same time, one minute per layer.

Time O(rows × cols)Space O(rows × cols)Code C#

Watch it animatedStep through it, with the running line highlighted. Free with an account.

The idea

Queue every rotten orange first, not just one: this is a BFS with several sources at once. Process the queue one whole layer at a time; everything rotted during a layer is one minute. A fresh orange left over once the queue empties can never be reached.

Code

public static int OrangesRotting(int[][] grid) {
    var queue = new Queue<(int r, int c)>();
    int fresh = 0;
    for (int r = 0; r < grid.Length; r++)
        for (int c = 0; c < grid[0].Length; c++) {
            if (grid[r][c] == 2) queue.Enqueue((r, c));
            else if (grid[r][c] == 1) fresh++;
        }
    int minutes = 0;
    int[] dr = { 1, -1, 0, 0 }, dc = { 0, 0, 1, -1 };
    while (queue.Count > 0 && fresh > 0) {
        int size = queue.Count;
        for (int i = 0; i < size; i++) {
            var (r, c) = queue.Dequeue();
            for (int k = 0; k < 4; k++) {
                int nr = r + dr[k], nc = c + dc[k];
                if (nr >= 0 && nc >= 0 && nr < grid.Length && nc < grid[0].Length && grid[nr][nc] == 1) {
                    grid[nr][nc] = 2; fresh--; queue.Enqueue((nr, nc));
                }
            }
        }
        minutes++;
    }
    return fresh == 0 ? minutes : -1;
}

Tips

Snapshot the queue size before the inner loop (`size = queue.Count`), so you process exactly one minute's layer, not newly rotted oranges too.
Count fresh oranges up front; when it hits 0 you can stop early instead of draining the rest of the queue.

In the .NET library

This is the same BFS-by-layers shape as plain BFS shortest paths, except the starting frontier is every "2" cell at once instead of a single source.