#994 - Rotting Oranges

MediumGraphs - BFS

In an m × n grid, each cell can be empty (0), a fresh orange (1), or a rotten orange (2). Every minute, fresh oranges adjacent (4-directionally) to rotten ones become rotten. Return the minimum number of minutes until no fresh orange remains, or -1 if impossible.

Input	Output
grid = [[2,1,1],[1,1,0],[0,1,1]]	4
grid = [[2,1,1],[0,1,1],[1,0,1]]	-1
grid = [[0,2]]	0

Solution Space

Try it

/**
 * Returns the minimum minutes for all oranges to rot, or -1 if impossible.
 * Multi-source BFS starting from all initially rotten oranges.
 *
 * @param grid m×n grid with 0 (empty), 1 (fresh), 2 (rotten)
 * @returns Minimum minutes, or -1
 */
export function orangesRotting(grid: number[][]): number {
  const m = grid.length;
  const n = grid[0].length;
  const dirs = [
    [0, 1],
    [0, -1],
    [1, 0],
    [-1, 0],
  ];
  const queue: [number, number][] = [];
  let fresh = 0;

  // Enqueue all initially rotten oranges and count fresh ones
  for (let r = 0; r < m; r++) {
    for (let c = 0; c < n; c++) {
      if (grid[r][c] === 2) queue.push([r, c]);
      else if (grid[r][c] === 1) fresh++;
    }
  }

  if (fresh === 0) return 0;

  let minutes = 0;

  while (queue.length > 0 && fresh > 0) {
    minutes++;
    const size = queue.length;

    for (let i = 0; i < size; i++) {
      const [row, col] = queue.shift()!;

      for (const [dr, dc] of dirs) {
        const nr = row + dr;
        const nc = col + dc;
        if (nr < 0 || nr >= m || nc < 0 || nc >= n || grid[nr][nc] !== 1)
          continue;

        grid[nr][nc] = 2;
        fresh--;
        queue.push([nr, nc]);
      }
    }
  }

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

Approach: multi-source BFS – enqueue all rotten oranges simultaneously, expand level-by-level (each level = one minute). Track remaining fresh count.

Time: O(m · n) – each cell enqueued at most once.

Space: O(m · n) – queue size.

#200 Number of Islands

#1926 Nearest Exit from Entrance in Maze