The "01 Matrix" problem requires you to transform a given binary matrix mat (containing only 0s and 1s) into a matrix where each cell containing a 1 is replaced by the distance to the nearest 0. The distance between two adjacent cells is always 1 (up, down, left, right). Cells containing 0 remain 0 in the output.
At first glance, you might think to handle each cell with a 1 individually: for each such cell, search the matrix for the nearest 0. This brute-force method would check all directions for every 1, leading to a very slow solution—especially for large matrices.
Instead, we can flip the problem: rather than searching from every 1 to the nearest 0, we can start from all 0s and "spread out," updating distances for every 1 we encounter. This way, each cell is updated as soon as its minimal distance is discovered. This is a classic use case for Breadth-First Search (BFS) in grids.
We'll use the BFS algorithm to solve this problem efficiently. Here’s how:
This approach ensures that each cell is updated in the order of its true minimal distance, thanks to BFS’s level-by-level expansion.
Consider the input matrix:
[[0,0,0],
[0,1,0],
[1,1,1]]
The final answer is:
[[0,0,0],
[0,1,0],
[1,2,1]]
Each step only updates a cell when a shorter path is found, ensuring correctness.
from collections import deque
class Solution:
def updateMatrix(self, mat):
rows, cols = len(mat), len(mat[0])
queue = deque()
# Initialize: set 1s to inf, queue all 0s
for r in range(rows):
for c in range(cols):
if mat[r][c] == 0:
queue.append((r, c))
else:
mat[r][c] = float('inf')
directions = [(-1,0), (1,0), (0,-1), (0,1)]
while queue:
r, c = queue.popleft()
for dr, dc in directions:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols:
if mat[nr][nc] > mat[r][c] + 1:
mat[nr][nc] = mat[r][c] + 1
queue.append((nr, nc))
return mat
#include <vector>
#include <queue>
#include <climits>
using namespace std;
class Solution {
public:
vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
int rows = mat.size(), cols = mat[0].size();
queue<pair<int, int>> q;
for (int r = 0; r < rows; ++r) {
for (int c = 0; c < cols; ++c) {
if (mat[r][c] == 0) {
q.push({r, c});
} else {
mat[r][c] = INT_MAX;
}
}
}
vector<pair<int, int>> dirs = {{-1,0},{1,0},{0,-1},{0,1}};
while (!q.empty()) {
auto [r, c] = q.front(); q.pop();
for (auto d : dirs) {
int nr = r + d.first, nc = c + d.second;
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols) {
if (mat[nr][nc] > mat[r][c] + 1) {
mat[nr][nc] = mat[r][c] + 1;
q.push({nr, nc});
}
}
}
}
return mat;
}
};
import java.util.*;
class Solution {
public int[][] updateMatrix(int[][] mat) {
int rows = mat.length, cols = mat[0].length;
Queue<int[]> queue = new LinkedList<>();
for (int r = 0; r < rows; ++r) {
for (int c = 0; c < cols; ++c) {
if (mat[r][c] == 0) {
queue.offer(new int[]{r, c});
} else {
mat[r][c] = Integer.MAX_VALUE;
}
}
}
int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
while (!queue.isEmpty()) {
int[] cell = queue.poll();
int r = cell[0], c = cell[1];
for (int[] d : dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols) {
if (mat[nr][nc] > mat[r][c] + 1) {
mat[nr][nc] = mat[r][c] + 1;
queue.offer(new int[]{nr, nc});
}
}
}
}
return mat;
}
}
var updateMatrix = function(mat) {
let rows = mat.length, cols = mat[0].length;
let queue = [];
for (let r = 0; r < rows; ++r) {
for (let c = 0; c < cols; ++c) {
if (mat[r][c] === 0) {
queue.push([r, c]);
} else {
mat[r][c] = Infinity;
}
}
}
let dirs = [[-1,0],[1,0],[0,-1],[0,1]];
let head = 0;
while (head < queue.length) {
let [r, c] = queue[head++];
for (let [dr, dc] of dirs) {
let nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols) {
if (mat[nr][nc] > mat[r][c] + 1) {
mat[nr][nc] = mat[r][c] + 1;
queue.push([nr, nc]);
}
}
}
}
return mat;
};
Brute-force approach: For each cell with a 1, you might need to search the whole matrix for the nearest 0. For an m x n matrix, this is O((m*n)^2) time and O(1) extra space.
Optimized BFS approach: Each cell is processed at most once. For each cell, we check its four neighbors, so the total time is O(m * n). The queue can hold up to O(m * n) elements, so space is also O(m * n).
This is a huge improvement over brute-force, especially for large matrices.
The "01 Matrix" problem is efficiently solved by reversing the naive approach: instead of searching from each 1 to the nearest 0, we spread out from all 0s using BFS. This guarantees that each cell is updated with its minimal distance in optimal time. The key insight is leveraging BFS for shortest-path updates in a grid, leading to an elegant and highly efficient solution.