LeetCode 542: 01 Matrix
Problem Description
Explanation
To solve this problem, we can use a breadth-first search (BFS) approach. We start by initializing a queue with all cells that have the value 0. Then, we iterate through the queue, popping cells one by one and updating their neighboring cells with the distance from the original cell. We continue this process until all cells are visited. At the end, the distances stored in the matrix will represent the distance of the nearest 0 for each cell.
Time complexity: O(m * n) where m is the number of rows and n is the number of columns in the matrix. Space complexity: O(m * n) for the queue and the resulting matrix.
Solutions
import java.util.LinkedList;
import java.util.Queue;
class Solution {
public int[][] updateMatrix(int[][] mat) {
int m = mat.length;
int n = mat[0].length;
Queue<int[]> queue = new LinkedList<>();
int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (mat[i][j] == 0) {
queue.offer(new int[]{i, j});
} else {
mat[i][j] = Integer.MAX_VALUE;
}
}
}
while (!queue.isEmpty()) {
int[] curr = queue.poll();
int row = curr[0];
int col = curr[1];
for (int[] dir : directions) {
int newRow = row + dir[0];
int newCol = col + dir[1];
if (newRow < 0 || newRow >= m || newCol < 0 || newCol >= n || mat[newRow][newCol] <= mat[row][col] + 1) {
continue;
}
mat[newRow][newCol] = mat[row][col] + 1;
queue.offer(new int[]{newRow, newCol});
}
}
return mat;
}
}Related LeetCode Problems
Loading editor...