01 Matrix

Description

doc

Solutions

First Idea

const DIRS = [
  [0, 1],
  [-1, 0],
  [0, -1],
  [1, 0],
]

function searchNearestZero(mat, point) {
  const mark = Array(mat.length)
    .fill()
    .map((_, i) => Array(mat[i].length))

  let queue = [point]
  mark[point[0]][point[1]] = 0

  while (queue.length) {
    const [x, y] = queue.shift()

    if (mat[x][y] === 0) {
      return mark[x][y]
    }

    DIRS.forEach(([_x, _y]) => {
      const newX = x + _x
      const newY = y + _y

      if (mat[newX]?.[newY] == null || mark[newX][newY] != null) {
        return
      }

      mark[newX][newY] = mark[x][y] + 1
      queue.push([newX, newY])
    })
  }
}

/**
 * @param {number[][]} mat
 * @return {number[][]}
 */
var updateMatrix = function (mat) {
  return mat.map((v, x) => v.map((sv, y) => (sv ? searchNearestZero(mat, [x, y]) : sv)))
}