LeetCode: 01 Matrix Solution

Speading from 0s

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

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 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 < 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}

Comments

Loading comments...

Tags

leetcode

array

matrix

bfs

Apply and earn a $2,500 bonus once you're hired on your first job!

Clients from the Fortune 500 to Silicon Valley startups

Choose your own rate, get paid on time

From hourly, part-time, to full-time positions

Flexible remote working environment

A lot of open JavaScript jobs!!

Fact corner: Referred talent are 5x more likely to pass the Toptal screening process than the average applicant.

Still hesitate? Read HoningJS author's guide on dealing with Toptal interview process.

Next Post

LeetCode: Power of Two

Secondary or high school math, I don't remember

HoningJS

Search Posts