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).