01 Matrix medium

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 (r1, c1) and (r2, c2) is |r1 - r2| + |c1 - c2|.

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,1,0],[1,1,1],[0,1,0]]

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

Steps

1. Initialization: Create a result matrix dist of the same size as mat, initialized with int.MaxValue for all cells except those containing 0s (which remain 0). This represents the initial distance (infinity) to a 0.

2. Multi-Source BFS (Breadth-First Search): Perform a BFS starting from all cells with value 0. This is a multi-source BFS because we start from multiple source nodes simultaneously.

3. Queue: Use a queue to store cells to be processed. Initially, add all cells with value 0 to the queue.

4. Iteration: While the queue is not empty:

   • Dequeue a cell (r, c).
   • For each of its four neighbors (up, down, left, right):
     • If the neighbor is within the bounds of the matrix and its distance in dist is greater than the distance to the current cell plus 1, update its distance in dist and add it to the queue.

5. Result: The dist matrix now contains the shortest distance to 0 for each cell.

Explanation

The algorithm uses a multi-source BFS to find the shortest distance from each cell to the nearest 0. BFS guarantees that we find the shortest path because it explores cells level by level. Starting from all 0s ensures that we find the minimum distance to the closest 0 for every cell. The int.MaxValue initialization ensures that we correctly update distances even for cells far from 0s.

Code

using System;
using System.Collections.Generic;

public class Solution {
    public int[][] UpdateMatrix(int[][] mat) {
        int m = mat.Length;
        int n = mat[0].Length;
        int[][] dist = new int[m][];
        for (int i = 0; i < m; i++) {
            dist[i] = new int[n];
            Array.Fill(dist[i], int.MaxValue);
        }

        Queue<(int, int)> q = new Queue<(int, int)>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mat[i][j] == 0) {
                    dist[i][j] = 0;
                    q.Enqueue((i, j));
                }
            }
        }

        int[] dr = { -1, 1, 0, 0 };
        int[] dc = { 0, 0, -1, 1 };

        while (q.Count > 0) {
            (int r, int c) = q.Dequeue();
            for (int i = 0; i < 4; i++) {
                int nr = r + dr[i];
                int nc = c + dc[i];
                if (nr >= 0 && nr < m && nc >= 0 && nc < n && dist[nr][nc] > dist[r][c] + 1) {
                    dist[nr][nc] = dist[r][c] + 1;
                    q.Enqueue((nr, nc));
                }
            }
        }

        return dist;
    }
}

Complexity

• Time Complexity: O(M * N), where M and N are the dimensions of the matrix. We visit each cell at most once in the BFS.
• Space Complexity: O(M * N) in the worst case, due to the queue and the dist matrix. The queue can hold all cells in the matrix in the worst-case scenario (when all cells are 1s).