Java solution, 23ms


  • 0
    G

    Worst time complexity is O((n*m)^2) - do BFS for each empty point.

    The solution is pretty straightforward - it is just a simple finding of shortest paths. I am a bit surprised the problem is marked as "Hard". Maybe there is some more sophisticated solution? (however based on average execution time there is no)

    The only tricky moment is in case we did not reach all buildings during some traversal - that means in later steps we can ignore all empty points which we visited during that failure traversal. Such trick decreases execution time from ~400ms to ~25ms.

    public class Solution {
        public int shortestDistance(int[][] grid) {
            if (grid == null || grid.length == 0 || grid[0].length == 0) {
                return -1;
            }
            
            int totalBldgs = countBldgs(grid);
            int minDist = -1;
            int dist;
            
            boolean[][] pointsToSkip = new boolean[grid.length][grid[0].length];
            
            for (int x = 0; x < grid.length; x++) {
                for (int y = 0; y < grid[x].length; y++) {
                    if (grid[x][y] == 0 && !pointsToSkip[x][y]) {
                        
                        List<int[]> newPointsToSkip = new ArrayList<>();
                        dist = shortestPathTillBlds(grid, x, y, totalBldgs, newPointsToSkip);
                        
                        if (dist > 0 && (minDist == -1 || dist < minDist)) {
                            minDist = dist;
                        }
                        
                        // if we didn't reach all buildings in this step
                        // later we can skip from checking all empty points which we just visited 
                        for (int[] point : newPointsToSkip) {
                            pointsToSkip[point[0]][point[1]] = true;
                        }
                    }
                }
            }
            
            return minDist;
        }
        
        private int countBldgs(int[][] grid) {
            int bldgs = 0;
            for (int x = 0; x < grid.length; x++) {
                for (int y = 0; y < grid[x].length; y++) {
                    if (grid[x][y] == 1) {
                        bldgs++;
                    }
                }
            }
            return bldgs;
        }
        
        private int shortestPathTillBlds(int[][] grid, int startX, int startY, int totalBldgs, List<int[]> pointsToSkipLater) {
            int path = 0;
            int bldgsFound = 0;
            
            // any value: length of path from the start point
            int[][] visited = new int[grid.length][grid[0].length];
            
            // [0],[1] - point to visit
            // [2],[3] - point where came from
            Queue<int[]> toVisit = new LinkedList<>();
            toVisit.offer(new int[]{startX, startY, -2, -2});
            pointsToSkipLater.add(new int[]{startX, startY});
            
            int[] p;
            int x, y, fromX, fromY;
            while (!toVisit.isEmpty()) {
                p = toVisit.poll();
                x = p[0];
                y = p[1];
                fromX = p[2];
                fromY = p[3];
                
                if (grid[x][y] == 1) {
                    path += visited[x][y];
                    bldgsFound++;
                    continue;
                }
                
                // add neighbour points to visit
                if (x > 0 && grid[x-1][y] != 2 && visited[x-1][y] == 0 && !(x-1 == startX && y == startY)) {
                    toVisit.offer(new int[]{x-1, y, x, y});
                    visited[x-1][y] = visited[x][y] + 1;
                    pointsToSkipLater.add(new int[]{x-1, y});
                }
                if (x < grid.length - 1 && grid[x+1][y] != 2 && visited[x+1][y] == 0 && !(x+1 == startX && y == startY)) {
                    toVisit.offer(new int[]{x+1, y, x, y});
                    visited[x+1][y] = visited[x][y] + 1;
                    pointsToSkipLater.add(new int[]{x+1, y});
                }
                if (y > 0 && grid[x][y-1] != 2 && visited[x][y-1] == 0 && !(x == startX && y-1 == startY)) {
                    toVisit.offer(new int[]{x, y-1, x, y});
                    visited[x][y-1] = visited[x][y] + 1;
                    pointsToSkipLater.add(new int[]{x, y-1});
                }
                if (y < grid[0].length - 1 && grid[x][y+1] != 2 && visited[x][y+1] == 0 && !(x == startX && y+1 == startY)) {
                    toVisit.offer(new int[]{x, y+1, x, y});
                    visited[x][y+1] = visited[x][y] + 1;
                    pointsToSkipLater.add(new int[]{x, y+1});
                }
            }
            
            if (bldgsFound == totalBldgs) {
                pointsToSkipLater.clear();
                return path;
            } else {
                return -1;
            }
        }
    }

Log in to reply
 

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