Algorithm
Problem Name: 542. 01 Matrix
Problem Link: https://leetcode.com/problems/01-matrix/
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 <= 1041 <= m * n <= 104mat[i][j]is either0or1.- There is at least one
0inmat.
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
vector<vector<int>> updateMatrix(vector < vector<int>>& matrix) {
int m = matrix.size(), n = matrix[0].size();
vector < pair<int, int>>dir({{0, 1}, {1, 0}, {-1, 0}, {0, -1}});
deque < pair<int, int>>q;
for(int i = 0; i < m; i++)
for(int j = 0; j < n; j++)
if(matrix[i][j]) matrix[i][j] = INT_MAX;
else q.push_back({i, j});
//BFS
while(!q.empty()){
auto p = q.front();
q.pop_front();
for(auto x: dir){
int r = p.first + x.first;
int c = p.second + x.second;
if(r < 0 || c < 0 || r == m || c == n> continue;
if(matrix[r][c] >= matrix[p.first][p.second] + 1){
matrix[r][c] = matrix[p.first][p.second] + 1;
q.push_back({r, c});
}
}
}
return matrix;
}
};
Input
mat = [[0,0,0],[0,1,0],[0,0,0]]
Output
[[0,0,0],[0,1,0],[0,0,0]]
#2 Code Example with Java Programming
Code -
Java Programming
class Solution {
private static final int[][] DIRS = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
public int[][] updateMatrix(int[][] mat) {
int numRows = mat.length;
int numCols = mat[0].length;
int[][] distances = new int[numRows][numCols];
Queue < int[]> queue = new LinkedList<>();
for (int i = 0; i < numRows; i++) {
for (int j = 0; j < numCols; j++) {
if (mat[i][j] == 0) {
queue.add(new int[]{i, j});
} else {
distances[i][j] = Integer.MAX_VALUE;
}
}
}
while (!queue.isEmpty()) {
int[] removed = queue.remove();
int currX = removed[0];
int currY = removed[1];
for (int[] dir : DIRS) {
int newX = currX + dir[0];
int newY = currY + dir[1];
if (newX >= 0 && newY >= 0 && newX < numRows && newY < numCols && distances[newX][newY] > distances[currX][currY] + 1) {
queue.add(new int[]{newX, newY});
distances[newX][newY] = distances[currX][currY] + 1;
}
}
}
return distances;
}
}
Input
mat = [[0,0,0],[0,1,0],[0,0,0]]
Output
[[0,0,0],[0,1,0],[0,0,0]]
#3 Code Example with Javascript Programming
Code -
Javascript Programming
const updateMatrix = function (matrix) {
const rows = matrix.length, cols = matrix[0].length;
const maxDist = rows + cols;
let dist = new Array(rows).fill(null).map(() => new Array(cols).fill(0));
for (let i = 0; i < rows; i++) {
for (let j = 0; j < cols; j++) {
if (matrix[i][j] !== 0) {
dist[i][j] = hasNeighborZero(i, j, matrix, rows, cols) ? 1 : maxDist;
}
}
}
for (let i = 0; i < rows; i++) {
for (let j = 0; j < cols; j++) {
if (dist[i][j] === 1) {
dfs(dist, i, j, -1);
}
}
}
return dist;
};
const dfs = function (dist, row, col, step) {
if (row < 0 || row >= dist.length || col < 0 || col >= dist[0].length || dist[row][col] <= step) return;
if (step > 0) dist[row][col] = step;
dfs(dist, row + 1, col, dist[row][col] + 1);
dfs(dist, row - 1, col, dist[row][col] + 1);
dfs(dist, row, col + 1, dist[row][col] + 1);
dfs(dist, row, col - 1, dist[row][col] + 1);
};
const hasNeighborZero = function (row, col, matrix, rows, cols) {
if (row < rows - 1 && matrix[row + 1][col] === 0) return true;
if (row > 0 && matrix[row - 1][col] === 0) return true;
if (col > 0 && matrix[row][col - 1] === 0) return true;
if (col < cols - 1 && matrix[row][col + 1] === 0) return true;
return false;
};
Input
mat = [[0,0,0],[0,1,0],[1,1,1]]
Output
[[0,0,0],[0,1,0],[1,2,1]]
#4 Code Example with Python Programming
Code -
Python Programming
class Solution:
def updateMatrix(self, matrix):
m, n = len(matrix), len(matrix and matrix[0])
for i in range(m):
for j in range(n):
if matrix[i][j] != 0:
matrix[i][j] = float("inf")
if i > 0 and matrix[i - 1][j] + 1 < matrix[i][j]:
matrix[i][j] = matrix[i - 1][j] + 1
if j > 0 and matrix[i][j - 1] + 1 < matrix[i][j]:
matrix[i][j] = matrix[i][j - 1] + 1
for i in range(m - 1, -1, -1):
for j in range(n - 1, -1, -1):
if matrix[i][j] != 0:
if i + 1 < m and matrix[i + 1][j] + 1 < matrix[i][j]:
matrix[i][j] = matrix[i + 1][j] + 1
if j + 1 < n and matrix[i][j + 1] + 1 < matrix[i][j]:
matrix[i][j] = matrix[i][j + 1] + 1
return matrix
Input
mat = [[0,0,0],[0,1,0],[1,1,1]]
Output
[[0,0,0],[0,1,0],[1,2,1]]