LeetCode: Rotting Oranges Solution

Approach: BFS

Final res - 1 is to exclude the last step where there is no fresh cell left

Implementation

1var orangesRotting = function (grid) {
2  const [m, n] = [grid.length, grid[0].length]
3  const cellOutbound = (row, col) => row < 0 || row >= m || col < 0 || col >= n
4  const cellNotFresh = (row, col) => [0, 2].includes(grid[row][col])
5
6  const dirs = [
7    [-1, 0],
8    [1, 0],
9    [0, -1],
10    [0, 1],
11  ]
12  const queue = []
13  let res = 0
14  let countFresh = 0
15
16  for (let row = 0; row < m; row++) {
17    for (let col = 0; col < n; col++) {
18      if (grid[row][col] === 2) queue.push([row, col])
19      if (grid[row][col] === 1) countFresh++
20    }
21  }
22
23  if (countFresh === 0) return 0
24
25  while (queue.length > 0) {
26    res++
27    let currentQueueLength = queue.length
28    while (currentQueueLength--) {
29      const cell = queue.shift()
30      for (const dir of dirs) {
31        const [row, col] = [cell[0] + dir[0], cell[1] + dir[1]]
32        if (cellOutbound(row, col) || cellNotFresh(row, col)) continue
33
34        grid[row][col] = 2
35        countFresh--
36        queue.push([row, col])
37      }
38    }
39  }
40
41  return countFresh === 0 ? res - 1 : -1
42}

References

Original problem

Similar problems

Walls and Gates

Detonate the Maximum Bombs

Escape the Spreading Fire