Multi‑Source BFS: Solving the 'Rotting Oranges' Problem

Rotting Oranges is a very good breadth‑first search problem because time is part of the structure. We are given a grid where:

• 0 means an empty cell
• 1 means a fresh orange
• 2 means a rotten orange

Every minute, any fresh orange directly adjacent to a rotten one becomes rotten too. The task is to work out how many minutes it takes for all fresh oranges to rot, or return ‑1 if some fresh oranges can never be reached.

That last detail is why this is not just a grid‑mutation problem. It is a shortest‑spread problem, which is exactly the kind of thing BFS handles well.

Why This is Multi‑Source BFS Rather than Ordinary BFS

In many BFS problems we start from one source node. Here, we start from every rotten orange at the same time.

That matters because all rotten oranges begin spreading immediately in parallel. If we only started from one of them and then the others later, we would distort the timing.

So the correct setup is:

• put every initially rotten orange into the queue first
• count how many fresh oranges exist
• process the spread level by level, where each level represents one minute

That is the whole multi‑source idea. The queue begins with several starting points instead of one.

Why Depth‑First Search is the Wrong Fit

It is worth saying this explicitly because the problem uses a grid, and grids often tempt people towards DFS automatically.

DFS is excellent when we need to explore a connected region completely. It is not the best default when the question is asking how long a spreading process takes. The timing here depends on all currently rotten oranges spreading outward together in waves.

That "together" part is exactly what BFS models well and DFS does not. DFS would happily run one branch deeply before another, which is the wrong shape for a minute‑by‑minute process happening in parallel across the grid.

A Practical TypeScript Solution

type Coordinate = [number, number];export const orangesRotting = (grid: number[][]): number => {  const rowCount = grid.length;  const columnCount = grid[0]?.length ?? 0;  const queue: Coordinate[] = [];  let head = 0;  let freshCount = 0;  for (let row = 0; row < rowCount; row += 1) {    for (let column = 0; column < columnCount; column += 1) {      if (grid[row][column] === 2) {        queue.push([row, column]);      } else if (grid[row][column] === 1) {        freshCount += 1;      }    }  }  if (freshCount === 0) {    return 0;  }  let minutes = 0;  const directions: Coordinate[] = [    [1, 0],    [-1, 0],    [0, 1],    [0, -1],  ];  while (head < queue.length && freshCount > 0) {    const levelSize = queue.length - head;    minutes += 1;    for (let count = 0; count < levelSize; count += 1) {      const [row, column] = queue[head];      head += 1;      for (const [rowOffset, columnOffset] of directions) {        const nextRow = row + rowOffset;        const nextColumn = column + columnOffset;        if (          nextRow < 0 ||          nextColumn < 0 ||          nextRow >= rowCount ||          nextColumn >= columnCount ||          grid[nextRow][nextColumn] !== 1        ) {          continue;        }        grid[nextRow][nextColumn] = 2;        freshCount -= 1;        queue.push([nextRow, nextColumn]);      }    }  }  return freshCount === 0 ? minutes : -1;};

Why Each BFS Level Represents One Minute

This is the conceptual heart of the problem.

At the start of each outer loop, the queue contains all oranges that are rotten at the current minute. When we process that whole batch, we rot their fresh neighbours and enqueue those newly rotten oranges.

Those newly rotten oranges should not spread again in the same minute. They only start spreading on the next minute, which is exactly why the queue is processed level by level.

So the algorithm is not just "do BFS on a grid". It is "treat each BFS layer as one unit of elapsed time".

Walking through One Example Minute by Minute

Take this grid:

2 1 11 1 00 1 1

At minute 0, only the top‑left orange is rotten.

After one minute, its fresh neighbours rot:

2 2 12 1 00 1 1

After the next minute, the newly rotten oranges spread further:

2 2 22 2 00 1 1

Then the spread continues until every reachable fresh orange has rotted.

That is exactly the level‑order behaviour of BFS. The queue contents at each stage represent the oranges that became rotten in the previous minute and are now ready to spread to the next layer.

Why the Fresh Orange Count is Worth Tracking

We could scan the whole grid again afterwards to check whether any fresh oranges remain, but that adds unnecessary work and muddies the state.

Keeping freshCount gives us three useful things:

• an immediate 0 result if there were no fresh oranges to begin with
• a clean way to stop once all fresh oranges have rotted
• a simple final check for unreachable fresh oranges

That keeps the control flow much clearer.

Why Mutating the Grid is Acceptable Here

The line that turns a fresh orange into 2 is doing two jobs at once:

• it records that the orange is now rotten
• it prevents the same orange from being enqueued repeatedly from different neighbours

That makes the grid itself part of the visited‑state tracking.

As with a lot of algorithm problems, mutating the input is usually fine because the grid is only being used as working state. If we were writing production code that needed to preserve the original grid, we would either clone it first or keep a separate visited structure. For the LeetCode version, in‑place mutation is the tidiest fit.

Common Mistakes

Starting BFS from Only One Rotten Orange

That gives the wrong timing because the spread begins from all initial rotten oranges simultaneously.

Incrementing Time for Every Orange Instead of Every Level

The clock advances once per wave of spread, not once per cell processed.

Forgetting Unreachable Fresh Oranges

If some fresh oranges are boxed in by empty cells, the answer is ‑1 even if much of the grid does rot successfully.

Complexity and Why It Scales Properly

Each cell is visited at most once as part of the spread, so the time complexity is O(rows * columns). The queue can also hold up to O(rows * columns) cells in the worst case.

That is exactly what we should expect from a grid BFS. The solution scales with the size of the grid rather than with the number of possible spread paths we might imagine.

Wrapping up

Rotting Oranges is a very tidy example of multi‑source BFS because the queue models time so naturally. Once we recognise that all rotten oranges start spreading together and each BFS level represents one minute, the implementation becomes much easier to trust.

Key Takeaways

• This is multi‑source BFS because several starting points spread in parallel.
• Each BFS level corresponds to one minute of elapsed time.
• Tracking fresh oranges explicitly keeps the solution simpler and more reliable.

It is a good reminder that BFS is not only for shortest paths in abstract graphs. It is often the cleanest way to model anything that spreads outward in waves.