@StefanPochmann Why can't we just run BFS at each '0', summing up the distance to each '1'. Once we've hit every node, we can return this distance only if we were able to go to all the 1's on the board.

This way we don't use any extra space other than the BFS, and the time complexity would also be O(K*m(n)) where K = # of 0's. Using your trick surely makes it faster, but in terms of time complexity its basically the same.. What would be better in an interview setting?

class Solution { int numOfHouses = 0; public int shortestDistance(int[][] grid) { int minDistance = Integer.MAX_VALUE; for(int i = 0; i < grid.length; i++){ for(int j = 0; j < grid[0].length; j++){ if(grid[i][j] == 1) numOfHouses++; } } for(int i = 0; i < grid.length; i++){ for(int j = 0; j < grid[0].length; j++){ if(grid[i][j] == 2 || grid[i][j] == 1) continue; minDistance = Math.min(minDistance, bfs(grid, i, j)); } } return minDistance == Integer.MAX_VALUE ? -1 : minDistance; } public int bfs(int[][] grid, int i, int j){ int[][] dirs = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; boolean[][] visited = new boolean[grid.length][grid[0].length]; Queue<int[]> queue = new LinkedList<>(); queue.offer(new int[]{i, j}); visited[i][j] = true; int distance = 0, houses = 0, level = 0; while(!queue.isEmpty()){ int size = queue.size(); for(int k = 0; k < size; k++){ int[] curr = queue.poll(); if(grid[curr[0]][curr[1]] == 1){ distance += level; ++houses; continue; } for(int[] d : dirs){ int row = curr[0] + d[0], col = curr[1] + d[1]; if(row >= 0 && col >= 0 && row < grid.length && col < grid[0].length && !visited[row][col] && grid[row][col] != 2){ visited[row][col] = true; queue.offer(new int[]{row, col}); } } } level++; } return houses == numOfHouses ? distance : Integer.MAX_VALUE; } }