Rotting Oranges

Each cell is 0 (empty), 1 (fresh) or 2 (rotten). Every minute, each fresh orange next to a rotten one (up, down, left, right) turns rotten. Return the minutes until no fresh orange is left, or -1 if that can never happen. (LC 994)

This is Level Order and the grid problems fused. The grid is the graph, the minutes are the levels, and the twist is that the search starts from many places at the same time.

The recipe

Say before you type: "Every rotten orange spreads at once, so one minute is one BFS level. I seed the queue with all of them, count the fresh oranges, and stop when that count hits zero. If any fresh orange is left when the queue runs dry, it was unreachable."

1. Scan the grid once. Push every rotten orange onto the queue, and count the fresh ones.
2. While the queue has work and fresh oranges remain, process exactly the oranges that are in the queue right now. That is one minute.
3. For each, rot every fresh neighbour: mark it rotten as you enqueue it, decrement the fresh count, and push it.
4. After the level, minutes++.
5. If fresh === 0, return minutes. Otherwise return -1.

The code

function orangesRotting(grid: number[][]): number {
  const rows = grid.length, cols = grid[0].length;
  const queue: [number, number][] = [];
  let fresh = 0;

  for (let r = 0; r < rows; r++)
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === 2) queue.push([r, c]);
      else if (grid[r][c] === 1) fresh++;
    }

  const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
  let minutes = 0;
  let head = 0; // read pointer: shift() would make every dequeue O(n)

  while (head < queue.length && fresh > 0) {
    const levelEnd = queue.length; // SNAPSHOT: this minute's oranges
    while (head < levelEnd) {
      const [r, c] = queue[head++];
      for (const [dr, dc] of dirs) {
        const nr = r + dr, nc = c + dc;
        if (nr < 0 || nr >= rows || nc < 0 || nc >= cols || grid[nr][nc] !== 1) continue;
        grid[nr][nc] = 2; // mark on enqueue, so nothing is queued twice
        fresh--;
        queue.push([nr, nc]);
      }
    }
    minutes++;
  }

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

Why this shape

BFS finds things in order of distance, and here distance is time. Starting from one orange would answer "how long until this orange rots everything", which is the wrong question. Starting from all of them at once is the same as adding a virtual source connected to every rotten orange: the first level is everyone's neighbours, and each level after that is one more minute.

Counting the fresh oranges up front earns its keep twice. It gives the loop a clean stopping point, and it answers the -1 question without a second scan: if the count is not zero when BFS ends, something was never reached.

Complexity

	Cost	Because
Time	O(m·n)	Each cell is enqueued at most once and looked at a constant number of times
Space	O(m·n)	The queue can hold most of the grid at once

Traps

• Counting one minute too many. If the loop runs while the queue is non-empty, the final level (oranges that have nothing left to rot) still increments minutes. [[2,1]] should be 1, not 2. Stopping when fresh === 0 fixes it.
• Seeding from one orange. [[2,1,1,2]] is 1 minute, because both ends spread at once. Starting from the first 2 alone gives 2.
• Forgetting the unreachable case. A fresh orange behind an empty cell, or in a corner nothing touches, leaves fresh > 0 forever. Return -1, not minutes.
• Marking on pop instead of on push. A fresh orange next to two rotten ones gets enqueued twice, and fresh goes negative.
• Diagonals do not spread. Four directions, not eight.
• queue.shift() is O(n) per call, which quietly makes the whole search quadratic on a big grid. A read pointer keeps it linear.

The pattern this trains

Multi-source BFS is one idea with many costumes: when the question is "how long until it has spread everywhere", put every source in the queue before the first step. It is the same move in 01 Matrix (542, distance to the nearest zero), Walls and Gates (286), and Pacific Atlantic (417). The one-source versions are Level Order and Shortest Path in Binary Matrix (1091).