0-1 Matrix

Problem Link: 01-matrix

Problem Statement

Given an m x n binary matrix mat, return a matrix that represents the distance of the nearest 0 for each cell.

The distance between two adjacent cells is defined as 1.

Examples

Example 1:

Input:
mat = [[0,0,0],
       [0,1,0],
       [1,1,1]]

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

Constraints

Intuition

This is a classic multi-source shortest path problem.

Key idea:

The BFS ensures that we always reach any 1 from its nearest 0 first.

Approach: Multi-Source BFS

Step-by-Step Plan:

  1. Initialize:

    • A result matrix dist with all values as -1.

    • A boolean matrix visited to track visited cells.

    • A queue for BFS.

  2. Preprocessing:

    • Push all cells with value 0 into the queue with distance 0.

    • Mark them visited.

  3. Run BFS:

    • For each popped cell (x, y):

      • For all 4 directions (up, down, left, right), calculate neighbor (nx, ny)

      • If it is inside bounds and not visited:

        • Set dist[nx][ny] = dist[x][y] + 1

        • Mark as visited

        • Push into queue

  4. Return the final dist matrix.

Java Code

class Solution {
    public int[][] updateMatrix(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;
        int[][] dist = new int[m][n];
        boolean[][] visited = new boolean[m][n];
        Queue<int[]> q = new LinkedList<>();

        // Add all 0s to the queue
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mat[i][j] == 0) {
                    q.offer(new int[]{i, j});
                    visited[i][j] = true;
                }
            }
        }

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

        while (!q.isEmpty()) {
            int[] cell = q.poll();
            int x = cell[0], y = cell[1];

            for (int[] dir : dirs) {
                int nx = x + dir[0];
                int ny = y + dir[1];

                if (nx >= 0 && ny >= 0 && nx < m && ny < n && !visited[nx][ny]) {
                    dist[nx][ny] = dist[x][y] + 1;
                    visited[nx][ny] = true;
                    q.offer(new int[]{nx, ny});
                }
            }
        }

        return dist;
    }
}

Dry Run

Input:

[[0,0,0],
 [0,1,0],
 [1,1,1]]

Initial queue:

(0,0), (0,1), (0,2), (1,0), (1,2)

Initial dist:

[[0,0,0],
 [0,-1,0],
 [-1,-1,-1]]

Steps:

Final output:

[[0,0,0],
 [0,1,0],
 [1,2,1]]

Time and Space Complexity

Applications