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]]
Pseudocode
- rephrase question as find shortest distance of 1 to 0
- use a queue, start with 0 value cells and reassign 1 to -1
- while queue is not empty
- iterate through queue (where cells were 0 value), in 4 directions
- if cells are -1 while traversing, push it into queue
- reassign cell value to origin cell from where it traverse + 1
Solution
// https://leetcode.com/problems/01-matrix/
// from solutions
// from solutions
// https://leetcode.com/problems/01-matrix/solutions/1369741/c-java-python-bfs-dp-solutions-with-picture-clean-concise-o-1-space/
var updateMatrix = function (matrix) {
const m = matrix.length;
const n = matrix[0].length;
const dir = [0, 1, 0, -1, 0];
let q = [];
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (matrix[i][j] === 0) {
q.push([i, j]);
} else {
matrix[i][j] = -1;
}
}
}
while (q.length) {
const [r, c] = q.shift();
// console.log(q)
for (let i = 0; i < 4; i++) {
let nr = r + dir[i];
let nc = c + dir[i + 1];
if (nr < 0 || nr === m || nc < 0 || nc === n || matrix[nr][nc] !== -1) {
continue;
}
matrix[nr][nc] = matrix[r][c] + 1;
q.push([nr, nc]);
}
// console.log(matrix)
}
return matrix;
};
