01 Matrix
Problem Description​
| Problem Statement | Solution Link | LeetCode Profile |
|---|---|---|
| 01 Matrix | 01 Matrix Solution on LeetCode | Nikita Saini |
Problem Description​
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.
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,0,0],[0,1,0],[1,1,1]]
Output:[[0,0,0],[0,1,0],[1,2,1]]
Constraints​
m == mat.lengthn == mat[i].length1 <= m, n <= 10^41 <= m * n <= 10^4mat[i][j]is either 0 or 1.- There is at least one 0 in
mat.
Approach​
To solve this problem, we can use the Breadth-First Search (BFS) approach. The idea is to start from all the 0s and perform a multi-source BFS to update the distances to the nearest 0 for all 1s.
Step-by-Step Algorithm​
- Initialize a queue and push all the cells containing 0s into the queue.
- Create a
distmatrix initialized withinffor cells containing 1s and 0 for cells containing 0s. - Perform BFS starting from all the 0s simultaneously:
- For each cell, pop it from the queue.
- For each neighboring cell, if the current distance + 1 is less than the stored distance, update the distance and push the neighbor into the queue.
- Continue until the queue is empty.
- Return the
distmatrix.
Solutions​
Python​
from collections import deque
def updateMatrix(mat):
rows, cols = len(mat), len(mat[0])
dist = [[float('inf')] * cols for _ in range(rows)]
queue = deque()
for r in range(rows):
for c in range(cols):
if mat[r][c] == 0:
dist[r][c] = 0
queue.append((r, c))
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 dist[nr][nc] > dist[r][c] + 1:
dist[nr][nc] = dist[r][c] + 1
queue.append((nr, nc))
return dist
Java​
import java.util.*;
public class Solution {
public int[][] updateMatrix(int[][] mat) {
int rows = mat.length, cols = mat[0].length;
int[][] dist = new int[rows][cols];
for (int[] row : dist) Arrays.fill(row, Integer.MAX_VALUE);
Queue<int[]> queue = new LinkedList<>();
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (mat[r][c] == 0) {
dist[r][c] = 0;
queue.add(new int[] { r, c });
}
}
}
int[][] directions = {{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 : directions) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols) {
if (dist[nr][nc] > dist[r][c] + 1) {
dist[nr][nc] = dist[r][c] + 1;
queue.add(new int[] { nr, nc });
}
}
}
}
return dist;
}
}
C++​
#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();
vector<vector<int>> dist(rows, vector<int>(cols, INT_MAX));
queue<pair<int, int>> q;
for (int r = 0; r < rows; ++r) {
for (int c = 0; c < cols; ++c) {
if (mat[r][c] == 0) {
dist[r][c] = 0;
q.push({r, c});
}
}
}
vector<pair<int, int>> directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
while (!q.empty()) {
auto [r, c] = q.front(); q.pop();
for (auto [dr, dc] : directions) {
int nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols) {
if (dist[nr][nc] > dist[r][c] + 1) {
dist[nr][nc] = dist[r][c] + 1;
q.push({nr, nc});
}
}
}
}
return dist;
}
};
C​
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define MAX 10000
typedef struct {
int row, col;
} Pair;
Pair queue[MAX];
int front = 0, rear = 0;
void enqueue(int row, int col) {
queue[rear].row = row;
queue[rear].col = col;
rear = (rear + 1) % MAX;
}
Pair dequeue() {
Pair p = queue[front];
front = (front + 1) % MAX;
return p;
}
int** updateMatrix(int** mat, int matSize, int* matColSize, int* returnSize, int** returnColumnSizes) {
int rows = matSize, cols = matColSize[0];
int** dist = (int**)malloc(rows * sizeof(int*));
for (int i = 0; i < rows; i++) {
dist[i] = (int*)malloc(cols * sizeof(int));
for (int j = 0; j < cols; j++) {
dist[i][j] = (mat[i][j] == 0) ? 0 : INT_MAX;
}
}
front = rear = 0;
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (mat[r][c] == 0) {
enqueue(r, c);
}
}
}
int directions[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
while (front != rear) {
Pair cell = dequeue();
int r = cell.row, c = cell.col;
for (int i = 0; i < 4; i++) {
int nr = r + directions[i][0], nc = c + directions[i][1];
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols) {
if (dist[nr][nc] > dist[r][c] + 1) {
dist[nr][nc] = dist[r][c] + 1;
enqueue(nr, nc);
}
}
}
}
*returnSize = rows;
*returnColumnSizes = (int*)malloc(rows * sizeof(int));
for (int i = 0; i < rows; i++) {
(*returnColumnSizes)[i] = cols;
}
return dist;
}
JavaScript​
var updateMatrix = function(mat) {
const rows = mat.length, cols = mat[0].length;
const dist = Array.from({ length: rows }, () => Array(cols).fill(Infinity));
const queue = [];
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
if (mat[r][c] === 0) {
dist[r][c] = 0;
queue.push([r, c]);
}
}
}
const directions = [[1, 0], [-1, 0], [
0, 1], [0, -1]];
while (queue.length) {
const [r, c] = queue.shift();
for (const [dr, dc] of directions) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols) {
if (dist[nr][nc] > dist[r][c] + 1) {
dist[nr][nc] = dist[r][c] + 1;
queue.push([nr, nc]);
}
}
}
}
return dist;
};
Conclusion​
The problem of finding the distance to the nearest zero in a binary matrix can be efficiently solved using a multi-source Breadth-First Search (BFS) approach. This method ensures that all cells are visited in the shortest possible distance order, ensuring an optimal solution.