Marauder Bot

Problem

You are given a grid where each cell holds an empty space, a fresh orange, or a rotten orange. Every minute, each rotten orange spreads rot to any fresh orange directly above, below, left, or right of it. Return the minimum number of minutes until no fresh orange remains, or -1 if some fresh orange can never be reached.

Example. A grid with one rotten orange next to two fresh oranges takes 1 minute to rot both; if a third fresh orange sits in a pocket with no path to any rotten one, the answer is -1.

Key idea

The rotting process happens in lockstep: every currently rotten orange infects its fresh neighbors during the same minute, not one at a time. That parallel spreading is what breadth-first search captures if seeded with every rotten orange at once, instead of growing outward from a single source. Put every initially rotten cell into the queue, then process it in waves: each wave rots the current batch's fresh neighbors and pushes those newly rotten cells as the next wave, incrementing a minute counter once per wave. Keep a running count of fresh oranges remaining; each cell rotted decrements it. When the queue empties, the process has reached everything it can: if the fresh count is zero, the minute counter holds the answer; otherwise some fresh oranges were unreachable and the answer is -1.

Solution

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

  for (let row = 0; row < rows; row++) {
    for (let col = 0; col < cols; col++) {
      if (grid[row][col] === 2) {
        queue.push([row, col]); // seed with every rotten orange, not just one
      } else if (grid[row][col] === 1) {
        freshCount++;
      }
    }
  }

  const directions = [
    [1, 0],
    [-1, 0],
    [0, 1],
    [0, -1],
  ];
  let minutes = 0;

  while (queue.length > 0 && freshCount > 0) {
    const nextQueue: Array<[number, number]> = []; // cells that rot this minute, next wave

    for (const [row, col] of queue) {
      for (const [dr, dc] of directions) {
        const newRow = row + dr;
        const newCol = col + dc;
        if (
          newRow >= 0 &&
          newRow < rows &&
          newCol >= 0 &&
          newCol < cols &&
          grid[newRow][newCol] === 1
        ) {
          grid[newRow][newCol] = 2;
          freshCount--;
          nextQueue.push([newRow, newCol]);
        }
      }
    }

    queue = nextQueue;
    minutes++;
  }

  return freshCount === 0 ? minutes : -1; // leftover fresh oranges mean a pocket was unreachable
}

Complexity

Time: O(rows × cols). Every cell is enqueued and processed at most once.
Space: O(rows × cols). The queue can hold up to every cell in the grid.

Watch out for

Seed the queue with all rotten oranges up front, not just the first one found, or the timing between sources will be wrong.
Track the fresh orange count separately rather than rescanning the grid, so an unreachable pocket is detected cleanly.
If there are no fresh oranges initially, the answer is 0 minutes, not -1.

Pattern

This is multi-source breadth-first search, where several starting points expand simultaneously and each search layer corresponds to one unit of time. The same layered-expansion idea applies to any shortest-time problem with several origins.

Rotting Oranges