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 and Explanation

This problem can be efficiently solved using Breadth-First Search (BFS). The core idea is to treat all cells with value 0 as sources and perform a BFS to find the shortest distance to each cell with value 1.

1. Initialization: Create a copy of the input matrix called dist to store the distances. Initialize all cells in dist with a large value (e.g., Integer.MAX_VALUE) to represent infinity. Cells with 0 in mat will be initialized to 0 in dist.

2. Queue: Create a queue of cell coordinates (rows and columns) and add all cells with value 0 from mat to the queue.

3. BFS Traversal: While the queue is not empty:

   • Dequeue a cell (row, col).
   • For each of its four neighbors (up, down, left, right):
     • If the neighbor is within the matrix bounds and its distance in dist is greater than the distance of the current cell plus 1:
       • Update the distance in dist for the neighbor cell to the distance of the current cell plus 1.
       • Enqueue the neighbor cell.

4. Result: After the BFS completes, the dist matrix will contain the shortest distance from each cell to the nearest 0.

Code

import java.util.*;

class Solution {
    public int[][] updateMatrix(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;
        int[][] dist = new int[m][n];

        // Initialize dist matrix
        for (int i = 0; i < m; i++) {
            Arrays.fill(dist[i], Integer.MAX_VALUE);
        }

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

        int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            int row = cell[0];
            int col = cell[1];

            for (int[] dir : dirs) {
                int newRow = row + dir[0];
                int newCol = col + dir[1];

                if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n &&
                        dist[newRow][newCol] > dist[row][col] + 1) {
                    dist[newRow][newCol] = dist[row][col] + 1;
                    queue.offer(new int[]{newRow, newCol});
                }
            }
        }

        return dist;
    }
}

Complexity

• Time Complexity: O(m * n), where 'm' and 'n' are the dimensions of the matrix. Each cell is visited and processed at most once.
• Space Complexity: O(m * n) in the worst case, due to the queue which might store all cells in the matrix if the matrix is mostly 1s. The dist matrix also takes O(m*n) space.