994. Rotting Oranges

In a grid, 0 is empty, 1 is a fresh orange and 2 is a rotten one. Every minute, fresh oranges next to a rotten one rot. Return the minutes until no fresh orange remains, or −1 if that is impossible.

Queue every rotten orange at minute 0 and BFS level by level. Each level is one minute. Count fresh oranges so you know if any are left unreachable.

1function orangesRotting(grid: number[][]): number {
2  let queue: number[][] = [], fresh = 0, minutes = 0;
3  grid.forEach((row, r) => row.forEach((v, c) => (v === 2 ? queue.push([r, c]) : v === 1 && fresh++)));
4  while (queue.length && fresh) {
5    const next: number[][] = [];
6    for (const [r, c] of queue)
7      for (const [x, y] of [[r + 1, c], [r - 1, c], [r, c + 1], [r, c - 1]])
8        if (grid[x]?.[y] === 1) { grid[x][y] = 2; fresh--; next.push([x, y]); }
9    queue = next; minutes++;
10  }
11  return fresh ? -1 : minutes;
12}

minutes = 0fresh = 8

grid

2	1	1	0
1	1	0	1
0	1	1	1

frontier

(0,0)

1 rotten orange(s) start the BFS; 8 fresh.

1 / 0

Space: play/pause · ←/→: step