01 Matrix

• Create a result matrix dist of the same size as the input mat.
• Iterate through each cell (r, c) of the input matrix.
• If mat[r][c] is 0, the distance is 0, so set dist[r][c] = 0.
• If mat[r][c] is 1, we must find the nearest 0. Initialize a variable min_dist to a very large value.
• Start a second, nested traversal over all cells (i, j) of the matrix.
• If mat[i][j] is 0, calculate the Manhattan distance |r - i| + |c - j| and update min_dist with the minimum value found so far.
• After checking all cells, dist[r][c] is set to the final min_dist.
• Return the dist matrix.

We create a new result matrix, dist, of the same dimensions as the input mat. We traverse each cell (r, c) of the input matrix. If mat[r][c] is 0, the distance is 0, so we set dist[r][c] = 0. If mat[r][c] is 1, we must find the nearest 0. We initialize a variable min_dist to a very large value. Then, we start a second, nested traversal over all cells (i, j) of the matrix. If we find a cell mat[i][j] that is 0, we calculate the Manhattan distance |r - i| + |c - j| and update min_dist with the minimum value found so far. After checking all cells, dist[r][c] is set to the final min_dist. This process is repeated for every cell containing a 1.

1class Solution {2    public int[][] updateMatrix(int[][] mat) {3        int m = mat.length;4        int n = mat[0].length;5        int[][] dist = new int[m][n];6 7        for (int r = 0; r < m; r++) {8            for (int c = 0; c < n; c++) {9                if (mat[r][c] == 0) {10                    dist[r][c] = 0;11                } else {12                    int min_dist = Integer.MAX_VALUE;13                    for (int i = 0; i < m; i++) {14                        for (int j = 0; j < n; j++) {15                            if (mat[i][j] == 0) {16                                min_dist = Math.min(min_dist, Math.abs(r - i) + Math.abs(c - j));17                            }18                        }19                    }20                    dist[r][c] = min_dist;21                }22            }23        }24        return dist;25    }26}

• Initialize a dist matrix of size m x n. For cells with 0 in mat, set dist to 0. For cells with 1, set dist to a large value (e.g., m + n).
• Pass 1 (Top-Left to Bottom-Right):
  • For i from 0 to m-1:
    • For j from 0 to n-1:
      • If i > 0, update dist[i][j] = min(dist[i][j], dist[i-1][j] + 1).
      • If j > 0, update dist[i][j] = min(dist[i][j], dist[i][j-1] + 1).
• Pass 2 (Bottom-Right to Top-Left):
  • For i from m-1 down to 0:
    • For j from n-1 down to 0:
      • If i < m-1, update dist[i][j] = min(dist[i][j], dist[i+1][j] + 1).
      • If j < n-1, update dist[i][j] = min(dist[i][j], dist[i][j+1] + 1).
• Return dist.

The first pass goes from top-left to bottom-right. It calculates the distance for each cell (i, j) based on the distances of the cells above it (i-1, j) and to its left (i, j-1). This effectively propagates distances from 0s that are located to the top-left of the current cell. The second pass goes from bottom-right to top-left. It updates the distance for each cell (i, j) based on the distances of the cells below it (i+1, j) and to its right (i, j+1). This pass propagates distances from 0s located to the bottom-right. By combining these two passes, we ensure that for every cell, we have considered the shortest path from a 0 regardless of its relative position.

1class Solution {2    public int[][] updateMatrix(int[][] mat) {3        int m = mat.length;4        int n = mat[0].length;5        int[][] dist = new int[m][n];6        int maxDist = m + n; // A safe upper bound for any distance7 8        // First pass: top-left to bottom-right9        for (int i = 0; i < m; i++) {10            for (int j = 0; j < n; j++) {11                if (mat[i][j] == 0) {12                    dist[i][j] = 0;13                } else {14                    dist[i][j] = maxDist;15                    if (i > 0) {16                        dist[i][j] = Math.min(dist[i][j], dist[i - 1][j] + 1);17                    }18                    if (j > 0) {19                        dist[i][j] = Math.min(dist[i][j], dist[i][j - 1] + 1);20                    }21                }22            }23        }24 25        // Second pass: bottom-right to top-left26        for (int i = m - 1; i >= 0; i--) {27            for (int j = n - 1; j >= 0; j--) {28                if (i < m - 1) {29                    dist[i][j] = Math.min(dist[i][j], dist[i + 1][j] + 1);30                }31                if (j < n - 1) {32                    dist[i][j] = Math.min(dist[i][j], dist[i][j + 1] + 1);33                }34            }35        }36        return dist;37    }38}

• Get matrix dimensions m and n.
• Create a dist matrix, initialized with 0 for 0-cells and a marker for unvisited (e.g., -1) for 1-cells.
• Create a queue and add the coordinates of all 0-cells to it.
• While the queue is not empty:
  • Dequeue a cell (r, c).
  • For each of its four neighbors (nr, nc):
    • If the neighbor is within bounds and is unvisited (dist[nr][nc] == -1):
      • Set its distance: dist[nr][nc] = dist[r][c] + 1.
      • Enqueue the neighbor (nr, nc).
• Return the dist matrix.

We start by identifying all the 'source' cells, which are the cells containing 0. Their distance to the nearest 0 is 0. We add all these source cells to a queue. We also initialize a dist matrix. We can use the input matrix itself to store distances if modification is allowed, or create a new one. Cells with 0 have distance 0, and cells with 1 can be marked as unvisited (e.g., with a value of -1). Then, we perform a standard BFS. We dequeue a cell, and for each of its unvisited neighbors, we update their distance to be the current cell's distance + 1, and then enqueue them. Because BFS explores layer by layer, the first time we reach a cell, we are guaranteed to have found the shortest path to it from one of the initial 0 sources.

1import java.util.LinkedList;2import java.util.Queue;3 4class Solution {5    public int[][] updateMatrix(int[][] mat) {6        int m = mat.length;7        int n = mat[0].length;8        int[][] dist = new int[m][n];9        Queue<int[]> queue = new LinkedList<>();10 11        // Initialize dist matrix and queue with all 0s12        for (int i = 0; i < m; i++) {13            for (int j = 0; j < n; j++) {14                if (mat[i][j] == 0) {15                    dist[i][j] = 0;16                    queue.offer(new int[]{i, j});17                } else {18                    dist[i][j] = -1; // Mark as unvisited19                }20            }21        }22 23        int[] dr = {-1, 1, 0, 0};24        int[] dc = {0, 0, -1, 1};25 26        while (!queue.isEmpty()) {27            int[] cell = queue.poll();28            int r = cell[0];29            int c = cell[1];30 31            for (int i = 0; i < 4; i++) {32                int nr = r + dr[i];33                int nc = c + dc[i];34 35                // Check bounds and if the cell is unvisited36                if (nr >= 0 && nr < m && nc >= 0 && nc < n && dist[nr][nc] == -1) {37                    dist[nr][nc] = dist[r][c] + 1;38                    queue.offer(new int[]{nr, nc});39                }40            }41        }42        return dist;43    }44}