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

Infinity
? Take a look back at find min problem

`.css-ds3kc{display:table-row;}.css-1t8atru{display:table-cell;opacity:0.5;padding-right:var(--chakra-space-6);-webkit-user-select:none;-moz-user-select:none;-ms-user-select:none;user-select:none;text-align:right;}1.css-2qghsv{display:table-cell;}function findMin(arr) {2  let min = Infinity3  for (const num of arr) {4    min = Math.min(min, num)5  }6  return min7}`

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

Infinity
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 < n5  const dirs = [6    [-1, 0],7    [1, 0],8    [0, -1],9    [0, 1],10  ].map(createCell)11  const queue = []12
13  // initial state14  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] = Infinity20      }21    }22  }23
24  // bfs traversal25  while (queue.length > 0) {26    const cell = queue.shift()27    for (const delta of dirs) {28      const row = cell.row + delta.row29      const col = cell.col + delta.col30      const adjCell = createCell([row, col]) // adj stands for adjacent31      if (!validCell(adjCell)) continue32
41  return mat42}```

leetcode

array

matrix

bfs

Next Post

LeetCode: Power of Two

Sep 24, 2021

Secondary or high school math, I don't remember

Search Posts