LeetCode: 01 Matrix Solution

Approach: BFS

To find the nearest distance to 0 for each cell, spread from 0s to other cells

Why init with

? Take a look back at find min problem

1function findMin(arr) {
2  let min = Infinity
3  for (const num of arr) {
4    min = Math.min(min, num)
5  }
6  return min
7}

Because we don't know the possible max number will be, so set initial min to

will be the safe start point

Implementation

1var updateMatrix = function (mat) {
2  const [m, n] = [mat.length, mat[0].length]
3  const createCell = ([row, col]) => ({ row, col })
4  const validCell = ({ row, col }) => 0 <= row && row < m && 0 <= col && col < n
5  const dirs = [
6    [-1, 0],
7    [1, 0],
8    [0, -1],
9    [0, 1],
10  ].map(createCell)
11  const queue = []
12
13  // initial state
14  for (let row = 0; row < m; row++) {
15    for (let col = 0; col < n; col++) {
16      if (mat[row][col] === 0) {
17        queue.push(createCell([row, col]))
18      } else {
19        mat[row][col] = Infinity
20      }
21    }
22  }
23
24  // bfs traversal
25  while (queue.length > 0) {
26    const cell = queue.shift()
27    for (const delta of dirs) {
28      const row = cell.row + delta.row
29      const col = cell.col + delta.col
30      const adjCell = createCell([row, col]) // adj stands for adjacent
31      if (!validCell(adjCell)) continue
32
33      // maintain the min distance to nearest 0
34      if (mat[adjCell.row][adjCell.col] > mat[cell.row][cell.col] + 1) {
35        mat[adjCell.row][adjCell.col] = mat[cell.row][cell.col] + 1
36        queue.push(adjCell)
37      }
38    }
39  }
40
41  return mat
42}