# 11ms simple Java soluton that beats 100% with explanation

• ``````public class Solution {

public int shortestDistance(int[][] grid) {

int[][] d = new int[grid.length][grid[0].length];//sum of distance from all buildings
int[][] cc = new int[grid.length][grid[0].length];//reachable by how many buildings
int count = 0;
//find how many buildings
for(int i = 0;i<grid.length;i++){
for(int j = 0;j<grid[0].length;j++){
if(grid[i][j] == 1) {
count++;
}
}
}

for(int i = 0;i<grid.length;i++){
for(int j = 0;j<grid[0].length;j++){
if(grid[i][j] == 1) {
//bfs each building, keep on updating empty spot's distance value
boolean x = bfs(grid, i, j, d, new boolean[grid.length][grid[0].length], count, cc);
if(!x)
return -1;//if this building can not reach all other buildings return -1
}
}
}

//find the smallest distance, need be an empty spot, and a spot can be reached by all buildings
int res = Integer.MAX_VALUE;
for(int i = 0;i<grid.length;i++){
for(int j = 0;j<grid[0].length;j++){
if(d[i][j] != 0 && cc[i][j] == count)
res = Math.min(res, d[i][j]);
}
}
return res == Integer.MAX_VALUE ? -1 : res ;
}

//nothing much, just bfs, but updates how many building can an empty spot reach, and
//if current building can reach all other buildings, otherwise returns false, solution returns -1
private boolean bfs(int[][]grid, int i, int j, int[][] d, boolean[][] used, int count, int[][] cc) {
used[i][j] = true;
int[] xx = new int[]{-1,0,1,0};
int[] yy = new int[]{0,-1,0,1};
int c = 1;
int neigh = 0;
while(!is.isEmpty()){
int x = is.poll();
int y = js.poll();
int dis = ds.poll();
for(int k =0 ;k<4;k++){
int newx = x + xx[k];
int newy = y + yy[k];
if(newx >=0 && newx < grid.length && newy >=0 && newy<grid[0].length && !used[newx][newy]) {
if(grid[newx][newy] == 0) {
used[newx][newy] = true;
d[newx][newy] += dis+1;
cc[newx][newy]++;
neigh++;
} else if(grid[newx][newy] == 1) {
c++;
used[newx][newy] = true;
}
}
}
}

return c == count && neigh > 0;
}
}``````

• Great Solution!
But I believe this variable is not useful:

``````int neigh = 0;
``````

• it is useful for cases like

``````1 0
1 1
``````

it detects that the corner 1 can reach all other buildings ,but it doesn't have a ”neigh“ (thus actually not reachable)
so it's an invalid case.