# Java 33ms BFS solution, beat 99%

• 1. run through matrix to find all cell with value 1. If the cell doesn't have zero around it, set it to Integer.MAX_VALUE
2. run through matrix again. For cell with value 1, use BFS to update matrix. If cell value larger than new value, update it and put cell into queue

``````public class Solution {
int[][] dir = new int[][]{{0,1},{0,-1},{1,0},{-1,0}};
public int[][] updateMatrix(int[][] matrix) {
if(matrix.length==0||matrix[0].length==0) return matrix;
int m = matrix.length;
int n = matrix[0].length;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(matrix[i][j]==1){
if(!checkZero(matrix,i,j)){
matrix[i][j] = Integer.MAX_VALUE;
}
}
}
}
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(matrix[i][j]==1){
bfs(matrix,i,j);
}
}
}
return matrix;
}
public boolean checkZero(int[][] matrix,int i,int j){
int m = matrix.length;
int n = matrix[0].length;
for(int[] d:dir){
int dx = d[0]+i;
int dy = d[1]+j;
if(dx>=0&&dx<m&&dy>=0&&dy<n&&matrix[dx][dy]==0) return true;
}
return false;
}
public void bfs(int[][] matrix,int i,int j){
int m = matrix.length;
int n = matrix[0].length;
queue.offer(new int[]{i,j});
int count = 1;
while(!queue.isEmpty()){
int size = queue.size();
count++;
while(size>0){
size--;
int[] p = queue.poll();
int px = p[0];
int py = p[1];
for(int[] d:dir){
int dx = d[0]+px;
int dy = d[1]+py;
if(dx<m&&dx>=0&&dy<n&&dy>=0&&matrix[dx][dy]>count){
matrix[dx][dy] = count;
queue.offer(new int[]{dx,dy});
}
}
}
}
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.