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.

&nbsp;
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]]


&nbsp;
Constraints:


	m == mat.length
	n == mat[i].length
	1 &lt;= m, n &lt;= 104
	1 &lt;= m * n &lt;= 104
	mat[i][j] is either 0 or 1.
	There is at least one 0 in mat.


class Solution:
    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
        if not mat or not mat[0]:
            return []

        m, n = len(mat), len(mat[0])
        queue = deque()
        MAX_VALUE = m * n
        
        # Initialize the queue with all 0s and set cells with 1s to MAX_VALUE.
        for i in range(m):
            for j in range(n):
                if mat[i][j] == 0:
                    queue.append((i, j))
                else:
                    mat[i][j] = MAX_VALUE
        
        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        
        while queue:
            row, col = queue.popleft()
            for dr, dc in directions:
                r, c = row + dr, col + dc
                if 0 <= r < m and 0 <= c < n and mat[r][c] > mat[row][col] + 1:
                    queue.append((r, c))
                    mat[r][c] = mat[row][col] + 1
        
        return mat
class Solution {
//  BFS
// We add all 0 to the queue in the 0th level of the BFS. From there, every subsequent pair of indexes added would be 1 in the mat. THis way levels can represent the distance of a one from the closest 0 to it.
    boolean visited[][];
    
    // Could also convert the indexes to a single number by mat[0].length * i + j.
    class Pair{
        int x;
        int y;
        Pair(int x, int y){
            this.x = x;
            this.y = y;
        }
    }
    public int[][] updateMatrix(int[][] mat) {
        int level = 0;
        visited = new boolean[mat.length][mat[0].length];
        Queue<Pair> q = new ArrayDeque<>();
        // Addition of all pairs in mat that have 0.
        for(int i = 0; i < mat.length; i++){
            for(int j = 0; j < mat[0].length; j++){
                if(mat[i][j] == 0){
                    visited[i][j] = true;
                    q.add(new Pair(i, j));
                }
            }
        }
        while(q.size()>0){
            int size = q.size();
            while(size-- > 0){
                Pair p = q.remove();
                mat[p.x][p.y] = level;
                if(p.x > 0 && visited[p.x - 1][p.y] == false){
                    visited[p.x-1][p.y] = true;
                    q.add(new Pair(p.x-1, p.y));
                }
                if(p.x < mat.length - 1 && visited[p.x + 1][p.y] == false){
                    visited[p.x+1][p.y] = true;
                    q.add(new Pair(p.x+1, p.y));
                    
                }
                if(p.y > 0 && visited[p.x][p.y-1] == false){
                    visited[p.x][p.y-1] = true;
                    q.add(new Pair(p.x, p.y-1));
                    
                }
                if(p.y < mat[0].length-1 && visited[p.x][p.y + 1] == false){
                    visited[p.x][p.y+1] = true;
                    q.add(new Pair(p.x, p.y + 1));
                }
            }
            level++;
        }
        return mat;
    }
}
class Solution {
   bool isValid(vector<vector<int>>& grid,int r,int c,int nr,int nc,int m,int n){
        if(nr>=0 && nc>=0 && nr<m && nc<n && grid[nr][nc]==-1){
            if(grid[r][c]==0)
                grid[nr][nc]=1;
            else
                grid[nr][nc]=grid[r][c]+1;
            return 1;
        }
        return 0;
    }
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
        queue<pair<int,int>> q;
        int m = mat.size();
        int n = mat[0].size();
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(mat[i][j]==0)
                    q.push({i,j});
                else
                    mat[i][j]=-1;
            }
        }
        while(!q.empty()){
            auto per = q.front();
            int r = per.first;
            int c = per.second;
            // if()
            q.pop();
            if(isValid(mat,r,c,r-1,c,m,n)){
                q.push({r-1,c});
            }
            if(isValid(mat,r,c,r+1,c,m,n)){
                q.push({r+1,c});
            }
            if(isValid(mat,r,c,r,c-1,m,n)){
                q.push({r,c-1});
            }
            if(isValid(mat,r,c,r,c+1,m,n)){
                q.push({r,c+1});
            }

        }
        return mat;
    }
};
/**
 * @param {number[][]} mat
 * @return {number[][]}
 */
var updateMatrix = function(mat) {
  const rows = mat.length,
        cols = mat[0].length;
  
  if (!rows) return mat;
  
  const queue = new Queue();
  const dist = Array.from({length: rows}, () => new Array(cols).fill(Infinity));
  
  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < cols; j++) {
      if (!mat[i][j]) {
        dist[i][j] = 0;
        queue.enqueue([i, j]);
      }
    }
  }
  
  const dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]];
  
  while (!queue.isEmpty()) {
    const [ row, col ] = queue.dequeue();
    for (let i = 0; i < 4; i++) {
      const nRow = row + dirs[i][0],
            nCol = col + dirs[i][1];
      
      if (nRow < 0 || nCol < 0 || nRow >= rows || nCol >= cols) continue;
      
      if (dist[nRow][nCol] > dist[row][col] + 1) {
        dist[nRow][nCol] = dist[row][col] + 1;
        queue.enqueue([nRow, nCol]);
      }
    }
  }
  
  return dist;
};
01 Matrix