01 Matrix
Problem link: https://leetcode.com/problems/01-matrix/
Problem Statement
Given an m x n binary matrix mat, return the distance of the nearest 0 for each cell. The distance between two adjacent cells is 1.
Input
An m x n binary matrix mat.
Output
An m x n matrix where each cell contains the distance to the nearest 0.
Example
Input: mat = [[0,0,0],[0,1,0],[1,1,1]] Output: [[0,0,0],[0,1,0],[1,2,1]]
Explanation
Cells with 0 have a distance of 0 to themselves. The '1' at (1,1) is adjacent to a 0, so distance is 1. The '1' at (2,1) is two steps away from the nearest 0.
Brute Force
Intuition
For every cell containing a 1, perform a Breadth-First Search (BFS) to find the nearest 0.
Approach
- Iterate through every cell $(i, j)$ in the matrix.
- If
mat[i][j] == 1, start a BFS from that cell. - Stop the BFS as soon as a
0is reached and record the distance. - If
mat[i][j] == 0, distance is 0.
Dry Run
For a matrix of size N*M, if there are many 1s, we restart BFS many times.
Code (Java)
// Omitted: Inefficient approach involving repeated BFS
Complexity Analysis
In the worst case (mostly 1s), we perform a full matrix traversal for almost every cell.
Optimal Solution
Intuition
Instead of finding the nearest 0 from every 1, we can start from all 0s simultaneously. This is called Multisource BFS. We treat all 0s as the 'starting layer' (distance 0) and propagate outward to the 1s.
Approach
- Initialize a
distmatrix with infinity for all 1s and 0 for all 0s. - Add all coordinates of 0s into a
Queue. - While the queue is not empty:
- Extract a cell $(r, c)$.
- Look at its 4 neighbors.
- If
dist[neighbor] > dist[r][c] + 1, update it and add the neighbor to the queue.
- Return the
distmatrix.
Dry Run
Input: [[0,1],[1,1]]
- Queue: [(0,0)], dist[0,1]=inf, dist[1,0]=inf, dist[1,1]=inf
- Pop (0,0): Neighbors (0,1) and (1,0) updated to dist 1. Queue: [(0,1), (1,0)]
- Pop (0,1): Neighbor (1,1) updated to dist 2. Queue: [(1,0), (1,1)] Result: [[0,1],[1,2]]
Code (Java)
class Solution {
public int[][] updateMatrix(int[][] mat) {
int m = mat.length, n = mat[0].length;
Queue<int[]> q = new LinkedList<>();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (mat[i][j] == 0) q.add(new int[]{i, j});
else mat[i][j] = -1; // Use -1 to mark unvisited
}
}
int[] dirs = {0, 1, 0, -1, 0};
while (!q.isEmpty()) {
int[] curr = q.poll();
for (int i = 0; i < 4; i++) {
int nr = curr[0] + dirs[i], nc = curr[1] + dirs[i+1];
if (nr >= 0 && nr < m && nc >= 0 && nc < n && mat[nr][nc] == -1) {
mat[nr][nc] = mat[curr[0]][curr[1]] + 1;
q.add(new int[]{nr, nc});
}
}
}
return mat;
}
}
Complexity Analysis
Each cell is added to the queue and processed exactly once. Space is used for the queue and the result matrix.
Quick Revision (Brute Force)
- BFS from every 1
- Inefficient: O((N*M)^2)
Quick Revision (Optimal)
- Multisource BFS
- Start BFS from all 0s simultaneously
- O(N*M) time and space
- Can also be solved using 2-pass Dynamic Programming