• Time:O(mn)
• Space:O(mn)

## C++

``````class Solution {
public:
vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
const int m = mat.size();
const int n = mat[0].size();
const vector<int> dirs{0, 1, 0, -1, 0};
queue<pair<int, int>> q;
vector<vector<bool>> seen(m, vector<bool>(n));

for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
if (mat[i][j] == 0) {
q.emplace(i, j);
seen[i][j] = true;
}

while (!q.empty()) {
const auto [i, j] = q.front();
q.pop();
for (int k = 0; k < 4; ++k) {
const int x = i + dirs[k];
const int y = j + dirs[k + 1];
if (x < 0 || x == m || y < 0 || y == n)
continue;
if (seen[x][y])
continue;
mat[x][y] = mat[i][j] + 1;
q.emplace(x, y);
seen[x][y] = true;
}
}

return mat;
}
};
``````

## JAVA

``````class Solution {
public int[][] updateMatrix(int[][] mat) {
final int m = mat.length;
final int n = mat[0].length;
final int[] dirs = new int[] {0, 1, 0, -1, 0};
Queue<int[]> q = new ArrayDeque<>();
boolean[][] seen = new boolean[m][n];

for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
if (mat[i][j] == 0) {
q.offer(new int[] {i, j});
seen[i][j] = true;
}

while (!q.isEmpty()) {
final int i = q.peek()[0];
final int j = q.poll()[1];
for (int k = 0; k < 4; ++k) {
final int x = i + dirs[k];
final int y = j + dirs[k + 1];
if (x < 0 || x == m || y < 0 || y == n)
continue;
if (seen[x][y])
continue;
mat[x][y] = mat[i][j] + 1;
q.offer(new int[] {x, y});
seen[x][y] = true;
}
}

return mat;
}
}
``````

## Python

``````class Solution:
def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
m = len(mat)
n = len(mat[0])
dirs = [0, 1, 0, -1, 0]
q = deque()
seen = [[False] * n for _ in range(m)]

for i in range(m):
for j in range(n):
if mat[i][j] == 0:
q.append((i, j))
seen[i][j] = True

while q:
i, j = q.popleft()
for k in range(4):
x = i + dirs[k]
y = j + dirs[k + 1]
if x < 0 or x == m or y < 0 or y == n:
continue
if seen[x][y]:
continue
mat[x][y] = mat[i][j] + 1
q.append((x, y))
seen[x][y] = True

return mat
``````

• Time:O(mn)
• Space:O(mn)

## C++

``````class Solution {
public:
vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
const int m = mat.size();
const int n = mat[0].size();
const vector<int> dirs{0, 1, 0, -1, 0};
queue<pair<int, int>> q;

for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
if (mat[i][j] == 0)
q.emplace(i, j);
else
mat[i][j] = INT_MAX;

while (!q.empty()) {
const auto [i, j] = q.front();
q.pop();
for (int k = 0; k < 4; ++k) {
const int x = i + dirs[k];
const int y = j + dirs[k + 1];
if (x < 0 || x == m || y < 0 || y == n)
continue;
if (mat[x][y] <= mat[i][j] + 1)
continue;
q.emplace(x, y);
mat[x][y] = mat[i][j] + 1;
}
}

return mat;
}
};
``````

## JAVA

``````class Solution {
public int[][] updateMatrix(int[][] mat) {
final int m = mat.length;
final int n = mat[0].length;
final int[] dirs = new int[] {0, 1, 0, -1, 0};
Queue<int[]> q = new ArrayDeque<>();

for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
if (mat[i][j] == 0)
q.offer(new int[] {i, j});
else
mat[i][j] = Integer.MAX_VALUE;

while (!q.isEmpty()) {
final int i = q.peek()[0];
final int j = q.poll()[1];
for (int k = 0; k < 4; ++k) {
final int x = i + dirs[k];
final int y = j + dirs[k + 1];
if (x < 0 || x == m || y < 0 || y == n)
continue;
if (mat[x][y] <= mat[i][j] + 1)
continue;
q.offer(new int[] {x, y});
mat[x][y] = mat[i][j] + 1;
}
}

return mat;
}
}
``````

## Python

``````class Solution:
def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
m = len(mat)
n = len(mat[0])
dirs = [0, 1, 0, -1, 0]
q = deque()

for i in range(m):
for j in range(n):
if mat[i][j] == 0:
q.append((i, j))
else:
mat[i][j] = math.inf

while q:
i, j = q.popleft()
for k in range(4):
x = i + dirs[k]
y = j + dirs[k + 1]
if x < 0 or x == m or y < 0 or y == n:
continue
if mat[x][y] <= mat[i][j] + 1:
continue
q.append((x, y))
mat[x][y] = mat[i][j] + 1

return mat
``````