Given a matrix consists of 0 and 1, find the distance to the nearest 0 for each cell.
The distance between two adjacent cells is 1.
Example 1:
Input: [[0,0,0], [0,1,0], [0,0,0]] Output: [[0,0,0], [0,1,0], [0,0,0]]
Example 2:
Input: [[0,0,0], [0,1,0], [1,1,1]] Output: [[0,0,0], [0,1,0], [1,2,1]]
Note:
The core challenge of this problem is to efficiently compute the shortest distance from each cell to the nearest 0. This problem is significant in various applications such as image processing, pathfinding in grids, and more. A common pitfall is to use a naive approach that results in high time complexity, making it impractical for larger matrices.
To solve this problem, we can use a multi-source Breadth-First Search (BFS) approach. The idea is to start from all the 0s simultaneously and propagate the distance to the 1s. This ensures that each cell is updated with the shortest distance to a 0.
A naive solution would involve iterating over each cell and performing a BFS or DFS to find the nearest 0. This approach is not optimal as it results in a time complexity of O((m*n)^2), where m and n are the dimensions of the matrix.
The optimized solution involves using a queue to perform a BFS starting from all 0s. This ensures that each cell is visited in the shortest path order. The time complexity of this approach is O(m*n), which is much more efficient.
1. Initialize a queue and enqueue all cells containing 0. Set their distance to 0.
2. For each cell containing 1, set its distance to infinity initially.
3. Perform BFS from the queue, updating the distance of each cell based on its neighbors.
4. Continue until the queue is empty.
import java.util.LinkedList;
import java.util.Queue;
public class Solution {
public int[][] updateMatrix(int[][] matrix) {
int rows = matrix.length;
int cols = matrix[0].length;
int[][] dist = new int[rows][cols];
Queue queue = new LinkedList<>();
// Initialize distances and queue
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (matrix[i][j] == 0) {
dist[i][j] = 0;
queue.offer(new int[]{i, j});
} else {
dist[i][j] = Integer.MAX_VALUE;
}
}
}
// Directions for moving in the matrix
int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
// BFS to update distances
while (!queue.isEmpty()) {
int[] cell = queue.poll();
int row = cell[0];
int col = cell[1];
for (int[] dir : directions) {
int newRow = row + dir[0];
int newCol = col + dir[1];
if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols) {
if (dist[newRow][newCol] > dist[row][col] + 1) {
dist[newRow][newCol] = dist[row][col] + 1;
queue.offer(new int[]{newRow, newCol});
}
}
}
}
return dist;
}
}
The time complexity of the optimized solution is O(m*n) because each cell is enqueued and dequeued at most once. The space complexity is also O(m*n) due to the distance matrix and the queue.
1. A matrix with all 0s: The output should be the same as the input.
2. A matrix with all 1s except one 0: The distances should increase as we move away from the 0.
3. Large matrices: Ensure the solution handles the upper limit of 10,000 elements efficiently.
To test the solution comprehensively, consider the following test cases:
1. Break down the problem into smaller parts and understand the requirements.
2. Consider different approaches and their time complexities.
3. Use diagrams or pseudo-code to visualize the solution.
4. Practice similar problems to improve problem-solving skills.
Understanding and solving the 01 Matrix problem helps in developing skills for grid-based problems and BFS/DFS algorithms. Practice and exploration of different approaches are key to mastering such problems.