Sponsored
Sponsored
The BFS approach involves initializing a queue with all positions of zeros in the matrix, since the distance from any zero to itself is zero. From there, perform a level-order traversal (BFS) to update the distances of the cells that are accessible from these initial zero cells. This approach guarantees that each cell is reached by the shortest path.
Time Complexity: O(m * n), as each cell is processed at most once.
Space Complexity: O(m * n), for storing the resulting distance matrix and the BFS queue.
1#include <vector>
2#include <queue>
3using namespace std;
4
5vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
6 int m = mat.size();
7 int n = mat[0].size();
8 vector<vector<int>> dist(m, vector<int>(n, INT_MAX));
9 queue<pair<int, int>> q;
10
11 for (int i = 0; i < m; i++) {
12 for (int j = 0; j < n; j++) {
13 if (mat[i][j] == 0) {
14 dist[i][j] = 0;
15 q.push({i, j});
16 }
17 }
18 }
19
20 vector<pair<int, int>> directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
21 while (!q.empty()) {
22 auto [r, c] = q.front();
23 q.pop();
24 for (auto [dr, dc] : directions) {
25 int nr = r + dr, nc = c + dc;
26 if (nr >= 0 && nr < m && nc >= 0 && nc < n && dist[nr][nc] > dist[r][c] + 1) {
27 dist[nr][nc] = dist[r][c] + 1;
28 q.push({nr, nc});
29 }
30 }
31 }
32
33 return dist;
34}Using C++, we perform a BFS using a queue and directions vector to spread out from each initially zeroed matrix cell, iterating over potential directions and updating distances as we go.
The dynamic programming (DP) approach updates the matrix by considering each cell from four possible directions, iterating twice over the matrix to propagate the minimum distances. First, traverse from top-left to bottom-right, and then from bottom-right to top-left, ensuring a comprehensive minimum distance calculation.
Time Complexity: O(m * n)
Space Complexity: O(m * n)
1public class Solution {
public int[][] UpdateMatrix(int[][] mat) {
int m = mat.Length, n = mat[0].Length;
int[][] dist = new int[m][];
for (int i = 0; i < m; i++) {
dist[i] = new int[n];
for (int j = 0; j < n; j++) {
dist[i][j] = mat[i][j] == 0 ? 0 : int.MaxValue - 1;
}
}
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (mat[i][j] != 0) {
if (i > 0) dist[i][j] = Math.Min(dist[i][j], dist[i - 1][j] + 1);
if (j > 0) dist[i][j] = Math.Min(dist[i][j], dist[i][j - 1] + 1);
}
}
}
for (int i = m - 1; i >= 0; --i) {
for (int j = n - 1; j >= 0; --j) {
if (mat[i][j] != 0) {
if (i < m - 1) dist[i][j] = Math.Min(dist[i][j], dist[i + 1][j] + 1);
if (j < n - 1) dist[i][j] = Math.Min(dist[i][j], dist[i][j + 1] + 1);
}
}
}
return dist;
}
}C# executes this double pass to ensure dist array is filled optimally from reference of initial positions, ultimately accumulating the shortest paths through systematic comprehensive traversal of rows & columns.