Rotting Oranges

What the problem is really asking

Every rotten orange spreads rot to its four neighbors in one minute.

So the question is really asking:

"If all rotten oranges start spreading at the same time, how many minutes does it take to reach every fresh orange?"

Intuition

This is not a single-source BFS.

All rotten oranges are active at minute 0, which means they should all go into the queue at the beginning.

That is exactly what multi-source BFS does.

Brute-force idea

A slow way would be:

• simulate minute 1 by scanning the whole grid
• then scan again for minute 2
• then again for minute 3

That works, but it repeats a lot of unnecessary work because we keep revisiting the full matrix.

Optimized approach

We do one initial pass:

• push every rotten orange into the queue
• count how many fresh oranges exist

Then BFS spreads outward level by level:

• one BFS layer = one minute
• whenever a fresh orange becomes rotten, decrease fresh
• when fresh becomes 0, we know all oranges are covered

If BFS ends and fresh is still positive, some orange was unreachable, so the answer is -1.

import java.util.ArrayDeque;
import java.util.Queue;

class Solution {
    public int orangesRotting(int[][] grid) {
        int rows = grid.length;
        int cols = grid[0].length;
        Queue<int[]> queue = new ArrayDeque<>();
        int fresh = 0;
        int minutes = 0;

        for (int row = 0; row < rows; row++) {
            for (int col = 0; col < cols; col++) {
                if (grid[row][col] == 2) {
                    queue.offer(new int[] {row, col});
                } else if (grid[row][col] == 1) {
                    fresh++;
                }
            }
        }

        int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

        while (!queue.isEmpty() && fresh > 0) {
            int size = queue.size();
            minutes++;

            for (int i = 0; i < size; i++) {
                int[] current = queue.poll();

                for (int[] direction : directions) {
                    int nextRow = current[0] + direction[0];
                    int nextCol = current[1] + direction[1];

                    if (
                        nextRow < 0 || nextCol < 0 || nextRow == rows || nextCol == cols
                        || grid[nextRow][nextCol] != 1
                    ) {
                        continue;
                    }

                    grid[nextRow][nextCol] = 2;
                    fresh--;
                    queue.offer(new int[] {nextRow, nextCol});
                }
            }
        }

        return fresh == 0 ? minutes : -1;
    }
}

Dry run

For

[
  [2, 1, 1],
  [1, 1, 0],
  [0, 1, 1]
]

• minute 0: queue starts with (0, 0)
• minute 1: rot (0, 1) and (1, 0)
• minute 2: rot (0, 2) and (1, 1)
• minute 3: rot (2, 1)
• minute 4: rot (2, 2)

So the answer is 4.

Common mistakes

1. Starting BFS from only one rotten orange

That misses the fact that many rotten oranges spread at the same time.

2. Counting minutes for every node instead of every layer

In BFS, one full queue layer represents one minute here.

3. Forgetting to track unreachable fresh oranges

Even if BFS finishes, you still need to check whether some fresh orange never got infected.

Complexity

Time Complexity: O(rows * cols)

Space Complexity: O(rows * cols)

Every cell is processed at most once, and the queue can hold a large part of the grid in the worst case.