01 Matrix

Problem Description

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

The distance between two cells sharing a common edge 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.

Note: This question is the same as 1765: https://leetcode.com/problems/map-of-highest-peak/

Solution (JavaScript)

/**
 * @param {number[][]} mat
 * @return {number[][]}
 */
var updateMatrix = function(mat) {
    let m = mat.length, n = mat[0].length;
    let cells = [];
    for(let i = 0; i<m; i++) {
        for(let j = 0; j<n; j++) {
            if(mat[i][j] === 0) {
                cells.push([i,j]);
            } else {
                mat[i][j] = null;
            }
        }
    }

    const DIR = [0, 1, 0, -1, 0];
    while(cells.length) {
        let newCells = [];
        for(const cell of cells) {
            const distance = mat[cell[0]][cell[1]] + 1;
            for(let i = 0; i<4; i++) {
                const nr = cell[0] + DIR[i], nc = cell[1] + DIR[i+1];
                if (nr < 0 || nr == m || nc < 0 || nc == n || mat[nr][nc] != null) {
                    continue
                }
                mat[nr][nc] = distance;
                newCells.push([nr, nc]);
            }
        }
        cells = newCells;
    }

    return mat;
};