Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Mediumgrid-graph-bfs

Rotting Oranges

Problem (restated)

Grid cells are empty (0), fresh orange (1), or rotten (2). Every minute, any fresh orange 4-adjacent to a rotten one becomes rotten. Return minutes until no fresh oranges remain, or -1 if impossible.

Intuition

All initially rotten oranges rot their neighbors in parallel. That is multi-source BFS: seed the queue with every rotten cell at time 0, then expand level by level (each level = one minute).

Approaches

Multi-source BFS by minute

Tested only

Time O(m·n)Space O(m·n)

Idea. Count fresh oranges. Enqueue all rotten cells. While the queue is non-empty and fresh remain, process one full layer: rot adjacent fresh cells, enqueue them, decrement fresh. Each layer increments minutes.

Walkthrough. [[2,1,1],[1,1,0],[0,1,1]] → all fresh rot in 4 minutes.

Trade-offs. Single-source BFS from each rotten cell and taking min times is slower and messier. In-place mutation marks cells as rotten so they are not re-enqueued.

Solution

export function orangesRotting(grid: number[][]): number {
  const R = grid.length;
  const C = grid[0]?.length ?? 0;
  const q: [number, number][] = [];
  let fresh = 0;
  for (let r = 0; r < R; r++) {
    for (let c = 0; c < C; c++) {
      if (grid[r]![c] === 2) q.push([r, c]);
      else if (grid[r]![c] === 1) fresh++;
    }
  }
  if (fresh === 0) return 0;
  const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]] as const;
  let minutes = 0;
  let head = 0;
  while (head < q.length && fresh > 0) {
    const size = q.length - head;
    for (let s = 0; s < size; s++) {
      const [r, c] = q[head++]!;
      for (const [dr, dc] of dirs) {
        const nr = r + dr, nc = c + dc;
        if (nr < 0 || nc < 0 || nr >= R || nc >= C) continue;
        if (grid[nr]![nc] !== 1) continue;
        grid[nr]![nc] = 2;
        fresh--;
        q.push([nr, nc]);
      }
    }
    minutes++;
  }
  return fresh === 0 ? minutes : -1;
}

export function orangesRotting(grid: number[][]): number {
  const R = grid.length;
  const C = grid[0]?.length ?? 0;
  const q: [number, number][] = [];
  let fresh = 0;
  for (let r = 0; r < R; r++) {
    for (let c = 0; c < C; c++) {
      if (grid[r]![c] === 2) q.push([r, c]);
      else if (grid[r]![c] === 1) fresh++;
    }
  }
  if (fresh === 0) return 0;
  const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]] as const;
  let minutes = 0;
  let head = 0;
  while (head < q.length && fresh > 0) {
    const size = q.length - head;
    for (let s = 0; s < size; s++) {
      const [r, c] = q[head++]!;
      for (const [dr, dc] of dirs) {
        const nr = r + dr, nc = c + dc;
        if (nr < 0 || nc < 0 || nr >= R || nc >= C) continue;
        if (grid[nr]![nc] !== 1) continue;
        grid[nr]![nc] = 2;
        fresh--;
        q.push([nr, nc]);
      }
    }
    minutes++;
  }
  return fresh === 0 ? minutes : -1;
}

Template connection

Flagship multi-source grid BFS. Same skeleton as 01 Matrix (542) and walls-and-gates style problems.

Reflection

Which pattern gave this away within 90 seconds?
What changed from the standard template?
What would break the current solution?