542. 01 Matrix

Problem

Given an m x n binary matrix mat, return **the distance of the nearest *0* for each cell**.

The distance between two adjacent cells is 1.

  Example 1:

Input: mat = [[0,0,0],[0,1,0],[0,0,0]] Output: [[0,0,0],[0,1,0],[0,0,0]] 

Example 2:

Input: mat = [[0,0,0],[0,1,0],[1,1,1]] Output: [[0,0,0],[0,1,0],[1,2,1]] 

  Constraints:

• m == mat.length

• n == mat[i].length

• 1 <= m, n <= 104

• 1 <= m * n <= 104

• mat[i][j] is either 0 or 1.

• There is at least one 0 in mat.

Solution

/** * @param {number[][]} mat * @return {number[][]} */ var updateMatrix = function(mat) { var arr = []; var m = mat.length; var n = mat[0].length; var res = Array(m).fill(0).map(() => Array(n)); var mark = function(i, j, distance) { if (mat[i] === undefined || mat[i][j] === undefined) return; if (res[i][j] !== undefined) return; arr.push([i, j]); res[i][j] = distance; }; for (var i = 0; i < m; i++) { for (var j = 0; j < n; j++) { mat[i][j] === 0 && mark(i, j, 0); } } while (arr.length) { var [i, j] = arr.shift(); mark(i - 1, j, res[i][j] + 1); mark(i + 1, j, res[i][j] + 1); mark(i, j - 1, res[i][j] + 1); mark(i, j + 1, res[i][j] + 1); } return res; }; 

Explain:

Breadth-first search.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).