01 Matrix — Distance to Nearest 0 (Multi-Source BFS)

Problem

Given a binary matrix, return a matrix where each cell has the distance to the nearest 0.

Approach — Multi-Source BFS from All Zeros

Initialize queue with all 0-cells (dist=0). BFS outward updates each 1-cell with dist[neighbor]+1.

Time: O(mn) | Space: O(mn)

Solutions

C++

class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
        int R=mat.size(),C=mat[0].size();
        vector<vector<int>> dist(R,vector<int>(C,INT_MAX));
        queue<pair<int,int>> q;
        for(int r=0;r<R;r++) for(int c=0;c<C;c++)
            if(mat[r][c]==0){dist[r][c]=0;q.push({r,c});}
        int dr[]={0,0,1,-1},dc[]={1,-1,0,0};
        while(!q.empty()){
            auto[r,c]=q.front();q.pop();
            for(int i=0;i<4;i++){
                int nr=r+dr[i],nc=c+dc[i];
                if(nr>=0&&nr<R&&nc>=0&&nc<C&&dist[nr][nc]>dist[r][c]+1){
                    dist[nr][nc]=dist[r][c]+1; q.push({nr,nc});
                }
            }
        }
        return dist;
    }
};

Python

from collections import deque
class Solution:
    def updateMatrix(self, mat: list[list[int]]) -> list[list[int]]:
        R,C=len(mat),len(mat[0])
        dist=[[float('inf')]*C for _ in range(R)]
        q=deque()
        for r in range(R):
            for c in range(C):
                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<R and 0<=nc<C and dist[nr][nc]>dist[r][c]+1:
                    dist[nr][nc]=dist[r][c]+1; q.append((nr,nc))
        return dist

Complexity

Time: O(mn) | Space: O(mn)