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, initially filled with Infinity. For cells containing 0 in mat, set the corresponding cell in dist to 0.

2. Multi-Source Breadth-First Search (BFS): Perform a BFS starting from all cells with value 0 in mat. We use a queue to store coordinates of cells to be processed.

3. Iteration: In each iteration, dequeue a cell (row, col) from the queue. For its adjacent cells (up, down, left, right):

   • If the distance in dist to the adjacent cell is greater than the distance to the current cell plus 1, update the distance in dist.
   • Enqueue the adjacent cell.

4. Termination: Continue until the queue is empty. All reachable cells will have their minimum distances updated.

Explanation:

This problem is a classic shortest path problem where the source nodes are all cells with value 0. BFS is an efficient algorithm to find the shortest path from multiple sources. The algorithm ensures that cells closer to a 0 are processed first, guaranteeing that the distances calculated are minimal. Using Infinity as the initial distance ensures that the first encountered distance to a 0 will always be the shortest.

Code:

function updateMatrix(mat: number[][]): number[][] {
    const m = mat.length;
    const n = mat[0].length;
    const dist: number[][] = Array.from({ length: m }, () => Array(n).fill(Infinity));
    const queue: [number, number][] = [];

    // Initialize queue and dist matrix for cells with 0
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (mat[i][j] === 0) {
                dist[i][j] = 0;
                queue.push([i, j]);
            }
        }
    }

    // BFS
    const directions = [[0, 1], [0, -1], [1, 0], [-1, 0]];
    while (queue.length > 0) {
        const [row, col] = queue.shift()!;
        for (const [dr, dc] of directions) {
            const newRow = row + dr;
            const newCol = col + dc;
            if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && dist[newRow][newCol] > dist[row][col] + 1) {
                dist[newRow][newCol] = dist[row][col] + 1;
                queue.push([newRow, newCol]);
            }
        }
    }

    return dist;
}

Complexity:

• Time Complexity: O(m * n), where 'm' and 'n' are the dimensions of the matrix. Each cell is visited at most once during the BFS.
• Space Complexity: O(m * n) in the worst case, due to the dist matrix and the queue. In the worst case, the queue could contain all cells.