Escape the Spreading Fire LeetCode solution in JavaScript

1
var maximumMinutes = function (grid) {
2
  let fireSpread = getFireSpreadTime(grid);
3
  let low = 0,
4
    high = 10 ** 9;
5
  while (low < high) {
6
    let mid = Math.ceil((low + high) / 2);
7
    if (canReachSafehouse(grid, fireSpread, mid)) low = mid;
8
    else high = mid - 1;
9
  }
10
  return canReachSafehouse(grid, fireSpread, low) ? low : -1;
11
};
12

13
function canReachSafehouse(originalGrid, fireSpread, timeToWait) {
14
  const directions = [
15
    [0, 1],
16
    [1, 0],
17
    [0, -1],
18
    [-1, 0],
19
  ];
20
  let grid = originalGrid.map((row) => [...row]);
21
  let m = grid.length,
22
    n = grid[0].length;
23
  let queue = [[0, 0]],
24
    time = timeToWait;
25
  while (queue.length) {
26
    for (let i = queue.length; i > 0; i--) {
27
      let [row, col] = queue.shift();
28
      if (row === m - 1 && col === n - 1) {
29
        return true;
30
      }
31
      for (let [x, y] of directions) {
32
        let newX = row + x,
33
          newY = col + y;
34
        if (
35
          newX < 0 ||
36
          newX >= m ||
37
          newY < 0 ||
38
          newY >= n ||
39
          grid[newX][newY] !== 0
40
        )
41
          continue; // out of bounds or cell is not grass
42
        let isTarget = newX === m - 1 && newY === n - 1;
43
        if (
44
          (isTarget && time + 1 <= fireSpread[newX][newY]) ||
45
          time + 1 < fireSpread[newX][newY]
46
        ) {
47
          // only visit if fire will not spread to new cell at the next minute
48
          grid[newX][newY] = 1;
49
          queue.push([newX, newY]);
50
        }
51
      }
52
    }
53
    time++;
54
  }
55
  return false;
56
}
57

58
function getFireSpreadTime(originalGrid) {
59
  const directions = [
60
    [0, 1],
61
    [1, 0],
62
    [0, -1],
63
    [-1, 0],
64
  ];
65
  let grid = originalGrid.map((row) => [...row]);
66
  let m = grid.length,
67
    n = grid[0].length;
68
  let queue = [];
69
  for (let i = 0; i < m; i++) {
70
    for (let j = 0; j < n; j++) {
71
      if (grid[i][j] === 1) {
72
        queue.push([i, j]);
73
      }
74
    }
75
  }
76

77
  let time = 0,
78
    fireSpread = Array(m)
79
      .fill(0)
80
      .map(() => Array(n).fill(Infinity));
81
  while (queue.length) {
82
    for (let i = queue.length; i > 0; i--) {
83
      let [row, col] = queue.shift();
84
      fireSpread[row][col] = time;
85
      for (let [x, y] of directions) {
86
        let newX = row + x,
87
          newY = col + y;
88
        if (
89
          newX < 0 ||
90
          newX >= m ||
91
          newY < 0 ||
92
          newY >= n ||
93
          grid[newX][newY] !== 0
94
        )
95
          continue; // out of bounds or cell is not grass
96
        grid[newX][newY] = 1;
97
        queue.push([newX, newY]);
98
      }
99
    }
100
    time++;
101
  }
102
  return fireSpread;
103
}