36 ms C++ solution


  • 71

    I also tested the other three C++ solutions posted so far, they took 340-1812 ms. I think mine is faster because I don't use a fresh "visited" for each BFS. Instead, I walk only onto the cells that were reachable from all previous buildings. From the first building I only walk onto cells where grid is 0, and make them -1. From the second building I only walk onto cells where grid is -1, and I make them -2. And so on.

    int shortestDistance(vector<vector<int>> grid) {
        int m = grid.size(), n = grid[0].size();
        auto total = grid;
        int walk = 0, mindist, delta[] = {0, 1, 0, -1, 0};
        for (int i=0; i<m; ++i) {
            for (int j=0; j<n; ++j) {
                if (grid[i][j] == 1) {
                    mindist = -1;
                    auto dist = grid;
                    queue<pair<int, int>> q;
                    q.emplace(i, j);
                    while (q.size()) {
                        auto ij = q.front();
                        q.pop();
                        for (int d=0; d<4; ++d) {
                            int i = ij.first + delta[d];
                            int j = ij.second + delta[d+1];
                            if (i >= 0 && i < m && j >= 0 && j < n && grid[i][j] == walk) {
                                grid[i][j]--;
                                dist[i][j] = dist[ij.first][ij.second] + 1;
                                total[i][j] += dist[i][j] - 1;
                                q.emplace(i, j);
                                if (mindist < 0 || mindist > total[i][j])
                                    mindist = total[i][j];
                            }
                        }
                    }
                    walk--;
                }
            }
        }
        return mindist;
    }

  • 0
    L
    This post is deleted!

  • 0
    L

    great solution! If I were to solve this problem, I would make a copy of the original grid and then follow your idea. Basically, my preference is never to change the input of reference type. We never know else where is using that input at the same time. That might cause weird result and even worse race conditions.


  • 1

    But I already do that. I do make a copy and am not working in the original.


  • 0
    Y
    This post is deleted!

  • 0

    @yajingleo Not sure what you mean, can you give me a small example?


  • 0
    Y
    This post is deleted!

  • 1

    No, if we can't reach (0,0) from the current building, then we don't need to go there. Because we're searching for a cell that's reachable from all buildings.


  • 0
    Y
    This post is deleted!

  • 0

    @yajingleo What you describe doesn't make sense. Can you please try to build and show an actual example? Maybe then you'll even see your mistake yourself :-)


  • 0
    Y
    This post is deleted!

  • 3
    M

    Good idea and very easy to understand,
    and you can add only one line to improve your performance!

    after each check of if(grid[i][j]==1){ } block
    just add: if(mindist==-1) return -1; Because you don't have to traverse every block as long as you've already found some block that is not reachable.
    And it only takes 20 ms.


  • 7
    E

    Really nice idea. The code beneath is the same idea implemented in Java listed here for reference (10ms beats 100%).

    public class Solution {
    static final int[] delta = new int[]{0, 1, 0, -1, 0};
    int min = Integer.MAX_VALUE;
    public int shortestDistance(int[][] grid) {
        int[][] dist = new int[grid.length][grid[0].length];
        int start = 1;
        for(int i = 0; i < grid.length; i++){
            for(int j = 0; j < grid[0].length; j++){
                if(grid[i][j] == 1){
                    bfsVisit(grid, dist, i, j, --start);
                }
            }
        }
        return min == Integer.MAX_VALUE? -1 : min;
    }
    private void bfsVisit(int[][] grid, int[][] dist, int row, int col, int start){
        Deque<int[]> que = new ArrayDeque<int[]>();
        que.offer(new int[]{row, col});
        int level = 0;
        min = Integer.MAX_VALUE;
        while(!que.isEmpty()){
            int size = que.size();
            level++;
            for(int k = 0; k < size; k++){
                int[] node = que.poll();
                for(int i = 1; i < delta.length; i++){
                    int newRow = node[0] + delta[i - 1];
                    int newCol = node[1] + delta[i];
                    if(newRow >= 0 && newRow < grid.length && 
                       newCol >= 0 && newCol < grid[0].length && 
                       grid[newRow][newCol] == start){
                        que.offer(new int[]{newRow, newCol});
                        dist[newRow][newCol] += level;
                        min = Math.min(min, dist[newRow][newCol]);
                        grid[newRow][newCol]--;
                    }
                }
            }
        }
    }
    

    }


  • 3
    A

    Great idea and nice code. Here is my Java version and also thanks for ericxliu's answer.

    int[] delta = {0, 1, 0, -1, 0};
    int minDist = -1;
    
    public int shortestDistance(int[][] grid) {
        if (grid == null || grid.length == 0 || 
            grid[0].length == 0) return minDist;
        int m = grid.length, n = grid[0].length;
        int[][] dist = new int[m][n];
        int walk = 1;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) bfs(i, j, --walk, grid, dist);
            }
        }
        return minDist;
    }
    
    private void bfs(int i, int j, int walk, int[][] grid, int[][] dist) {
        minDist = -1;
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{i, j});
        int depth = 0;
        while (!q.isEmpty()) {
            depth++;
            int len = q.size();
            for (int k = 0; k < len; k++) {
                int[] pos = q.poll();
                for (int d = 0; d < 4; d++) {
                    int r = pos[0] + delta[d];
                    int c = pos[1] + delta[d + 1];
                    if (r >= 0 && r < grid.length && c >= 0 && c < grid[0].length
                        && grid[r][c] == walk) {
                        grid[r][c] = walk - 1;
                        dist[r][c] += depth;
                        if (minDist < 0 || minDist > dist[r][c]){
                            minDist = dist[r][c];
                        }
                        q.offer(new int[]{r, c});
                    }
                }
            }
        }
    }
    

  • 0
    M

    How can you avoid loop in you bfs traverse?


  • 2

    @mdyuki1016 By going only where grid[i][j] == walk and right away doing grid[i][j]--.


  • 0
    C

    Is the time complexity O(kmn), where k is number of buildings and m*n is number of whole grid?

    And the space complexity is O(kmn) too.
    Thanks


  • 2

    @coder2 I'd also say time complexity O(kmn), but space complexity can be regarded as O(mn). That's the most I ever use at any point in time. Otherwise, i.e., if you add up all memory ever possibly used, then for example traversals in a balanced binary search tree might not be O(log n) space but only O(n) space (there probably are better examples, it's just the first that came to my mind).

    It could easily be made clearly O(mn) space, but that would just make the code uglier and not be interesting, in my opinion.


  • 0
    T

    Beautiful and elegant solution. This is my goal coding and problem solving style


  • 0
    S

    What a brilliant solution!


Log in to reply
 

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