542. 01 Matrix

At a Glance

Topic: Array
Pattern: Analyze Pattern
Difficulty: Medium
LeetCode: 542

Problem Statement

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/

Approach & Solution Steps

Use multi-source BFS. Enqueue all 0s and mark 1s as unvisited. BFS outward from the 0s to update distances level by level.

Optimal JS Solution

function updateMatrix(mat) {
  const m = mat.length, n = mat[0].length;
  const queue = [];
  for (let r = 0; r < m; r++) {
    for (let c = 0; c < n; c++) {
      if (mat[r][c] === 0) queue.push([r, c]);
      else mat[r][c] = Infinity;
    }
  }
  const dirs = [[1,0], [-1,0], [0,1], [0,-1]];
  while (queue.length) {
    const [r, c] = queue.shift();
    for (const [dr, dc] of dirs) {
      const nr = r + dr, nc = c + dc;
      if (nr >= 0 && nr < m && nc >= 0 && nc < n && mat[nr][nc] > mat[r][c] + 1) {
        mat[nr][nc] = mat[r][c] + 1;
        queue.push([nr, nc]);
      }
    }
  }
  return mat;
}

Edge Cases & Pitfalls

Always consider empty or null inputs.
Watch out for off-by-one index errors.