01 Matrix

medium array dp bfs matrix

Problem

Given an m×n binary matrix mat, return the distance of the nearest 0 for each cell (cells share an edge with neighbours).

Inputmat = [[0,0,0],[0,1,0],[1,1,1]]

Output[[0,0,0],[0,1,0],[1,2,1]]

Multi-source BFS from every 0 simultaneously fills in increasing distances.

matrix rows (semicolon-separated, comma-separated values)

from collections import deque
def update_matrix(mat):
    m, n = len(mat), len(mat[0])
    dist = [[-1]*n for _ in range(m)]
    q = deque()
    for r in range(m):
        for c in range(n):
            if mat[r][c] == 0:
                dist[r][c] = 0
                q.append((r, c))
    while q:
        r, c = q.popleft()
        for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
            nr, nc = r+dr, c+dc
            if 0 <= nr < m and 0 <= nc < n and dist[nr][nc] == -1:
                dist[nr][nc] = dist[r][c] + 1
                q.append((nr, nc))
    return dist

function updateMatrix(mat) {
  const m = mat.length, n = mat[0].length;
  const dist = Array.from({ length: m }, () => Array(n).fill(-1));
  const q = [];
  for (let r = 0; r < m; r++)
    for (let c = 0; c < n; c++)
      if (mat[r][c] === 0) { dist[r][c] = 0; q.push([r, c]); }
  const dirs = [[1,0],[-1,0],[0,1],[0,-1]];
  for (let i = 0; i < q.length; i++) {
    const [r, c] = q[i];
    for (const [dr, dc] of dirs) {
      const nr = r+dr, nc = c+dc;
      if (nr>=0 && nr<m && nc>=0 && nc<n && dist[nr][nc] === -1) {
        dist[nr][nc] = dist[r][c] + 1;
        q.push([nr, nc]);
      }
    }
  }
  return dist;
}

class Solution {
    public int[][] updateMatrix(int[][] mat) {
        int m = mat.length, n = mat[0].length;
        int[][] dist = new int[m][n];
        Deque<int[]> q = new ArrayDeque<>();
        for (int r = 0; r < m; r++)
            for (int c = 0; c < n; c++) {
                if (mat[r][c] == 0) q.offer(new int[]{r, c});
                else dist[r][c] = -1;
            }
        int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
        while (!q.isEmpty()) {
            int[] p = q.poll();
            for (int[] d : dirs) {
                int nr = p[0]+d[0], nc = p[1]+d[1];
                if (nr>=0 && nr<m && nc>=0 && nc<n && dist[nr][nc] == -1) {
                    dist[nr][nc] = dist[p[0]][p[1]] + 1;
                    q.offer(new int[]{nr, nc});
                }
            }
        }
        return dist;
    }
}

vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
    int m = mat.size(), n = mat[0].size();
    vector<vector<int>> dist(m, vector<int>(n, -1));
    queue<pair<int,int>> q;
    for (int r = 0; r < m; r++)
        for (int c = 0; c < n; c++)
            if (mat[r][c] == 0) { dist[r][c] = 0; q.push({r, c}); }
    int dr[4] = {1,-1,0,0}, dc[4] = {0,0,1,-1};
    while (!q.empty()) {
        auto [r, c] = q.front(); q.pop();
        for (int k = 0; k < 4; k++) {
            int nr = r+dr[k], nc = c+dc[k];
            if (nr>=0 && nr<m && nc>=0 && nc<n && dist[nr][nc] == -1) {
                dist[nr][nc] = dist[r][c] + 1;
                q.push({nr, nc});
            }
        }
    }
    return dist;
}

Explanation

We need the distance from every cell to its nearest 0. Doing a separate search from each cell would be slow, so instead we start from all the zeros at once and let the search expand outward.

This is multi-source BFS. We put every 0 cell into a queue with distance 0, then repeatedly pop a cell and look at its four neighbours. Any neighbour we have not labelled yet gets distance + 1 and is pushed onto the queue.

Because BFS processes cells in order of distance, the first time we reach a cell we have already found its shortest path back to some zero. We use -1 in dist to mark "not visited yet" so each cell is filled exactly once.

Example: [[0,0,0],[0,1,0],[1,1,1]]. The four edge zeros seed distance 0. The center 1 is reached from a zero one step away, so it becomes 1. The bottom-middle 1 is two steps from the nearest zero, so it becomes 2, giving [[0,0,0],[0,1,0],[1,2,1]].

Time: O(m·n) Space: O(m·n)