Rotting Oranges: the idea to remember.

The core insight

Seed a queue with every rotten orange, then spread infection one breadth first layer per minute.

Why it works

All sources advance simultaneously, so the first infection time of each cell is its minimum distance from any source.

The mistake to avoid

Count fresh oranges; an unreachable fresh cell means minus one, while no fresh oranges means zero.

Commented Java solution

Use java.util.* imports and a surrounding solution class. Tree snippets assume the standard TreeNode definition; linked lists use ListNode and Clone Graph uses a Node with val and neighbors; Copy Random List uses Node with val, next and random. Read the input assumptions above.

// Java reference adapted from neetcode-gh/leetcode (MIT).
// Seed a queue with every rotten orange, then spread infection one breadth first layer per minute.
public int orangesRotting(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    Queue<int[]> queue = new LinkedList<>();
    int fresh = 0;

    for (int i = 0; i < m; i += 1) {
        for (int j = 0; j < n; j += 1) {
            if (grid[i][j] == 2) queue.offer(new int[] { i, j }); else if (
                grid[i][j] == 1
            ) fresh += 1;
        }
    }

    int count = 0;
    int[][] dirs = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
    while (!queue.isEmpty() && fresh != 0) {
        count += 1;
        int sz = queue.size();
        for (int i = 0; i < sz; i += 1) {
            int[] rotten = queue.poll();
            int r = rotten[0], c = rotten[1];
            for (int[] dir : dirs) {
                int x = r + dir[0], y = c + dir[1];
                if (0 <= x && x < m && 0 <= y && y < n && grid[x][y] == 1) {
                    grid[x][y] = 2;
                    queue.offer(new int[] { x, y });
                    fresh -= 1;
                }
            }
        }
    }
    return fresh == 0 ? count : -1;
}

Java reference adapted from neetcode-gh/leetcode · MIT license

Make the next connection