Java solution with explanation and time complexity analysis


  • 57
    S

    Inspired by previous solution.
    The main idea is the following:

    Traverse the matrix. For each building, use BFS to compute the shortest distance from each '0' to
    this building. After we do this for all the buildings, we can get the sum of shortest distance
    from every '0' to all reachable buildings. This value is stored
    in 'distance[][]'. For example, if grid[2][2] == 0, distance[2][2] is the sum of shortest distance from this block to all reachable buildings.
    Time complexity: O(number of 1)O(number of 0) ~ O(m^2n^2)

    We also count how many building each '0' can be reached. It is stored in reach[][]. This can be done during the BFS. We also need to count how many total buildings are there in the matrix, which is stored in 'buildingNum'.

    Finally, we can traverse the distance[][] matrix to get the point having shortest distance to all buildings. O(m*n)

    The total time complexity will be O(m^2*n^2), which is quite high!. Please let me know if I did the analysis wrong or you have better solution.

    public class Solution {
        public int shortestDistance(int[][] grid) {
            if (grid == null || grid[0].length == 0) return 0;
            final int[] shift = new int[] {0, 1, 0, -1, 0};
            
            int row  = grid.length, col = grid[0].length;
            int[][] distance = new int[row][col];
            int[][] reach = new int[row][col];
            int buildingNum = 0;
            
            for (int i = 0; i < row; i++) {
                for (int j =0; j < col; j++) {
                    if (grid[i][j] == 1) {
                        buildingNum++;
                        Queue<int[]> myQueue = new LinkedList<int[]>();
                        myQueue.offer(new int[] {i,j});
    
                        boolean[][] isVisited = new boolean[row][col];
                        int level = 1;
                        
                        while (!myQueue.isEmpty()) {
                            int qSize = myQueue.size();
                            for (int q = 0; q < qSize; q++) {
                                int[] curr = myQueue.poll();
                                
                                for (int k = 0; k < 4; k++) {
                                    int nextRow = curr[0] + shift[k];
                                    int nextCol = curr[1] + shift[k + 1];
                                    
                                    if (nextRow >= 0 && nextRow < row && nextCol >= 0 && nextCol < col
                                        && grid[nextRow][nextCol] == 0 && !isVisited[nextRow][nextCol]) {
                                            //The shortest distance from [nextRow][nextCol] to thic building
                                            // is 'level'.
                                            distance[nextRow][nextCol] += level;
                                            reach[nextRow][nextCol]++;
                                            
                                            isVisited[nextRow][nextCol] = true;
                                            myQueue.offer(new int[] {nextRow, nextCol});
                                        }
                                }
                            }
                            level++;
                        }
                    }
                }
            }
            
            int shortest = Integer.MAX_VALUE;
            for (int i = 0; i < row; i++) {
                for (int j = 0; j < col; j++) {
                    if (grid[i][j] == 0 && reach[i][j] == buildingNum) {
                        shortest = Math.min(shortest, distance[i][j]);
                    }
                }
            }
            
            return shortest == Integer.MAX_VALUE ? -1 : shortest;
            
            
        }
    }

  • 0
    C

    I think a better solution is using BFS to walk from all buildings together and stop in the middle when all of them meet, instead of completing all spots. However, my run time is just 58ms. I think it is because I used custom class. Can someone help to improve?

    static final int[] s={-1,0,1,0,-1};
    
    class Move{
        int x;
        int steps;
        boolean[][] visited;
        Move(int p, int s){
            x=p;
            steps=s;
        }
    }
    
    public int shortestDistance(int[][] grid) {
        if(grid==null || grid.length==0 || grid[0].length==0) return 0;
        int m = grid.length, n=grid[0].length, total=0, min=Integer.MAX_VALUE;
        int[][] distance= new int[m][n];
        int[][] reach= new int[m][n];
        Deque<Move> queue = new ArrayDeque<>();
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(grid[i][j]==1){
                    Move mv = new Move(i*n+j, 0);
                    mv.visited = new boolean[m][n];
                    mv.visited[i][j]=true;
                    queue.offer(mv);
                    total++;
                }
            }
        }
        while(!queue.isEmpty()){
            Move mv = queue.poll();
            int x = mv.x/n, y=mv.x%n;
            for(int i=0; i<4; i++){
                int p = x+s[i], q=y+s[i+1];
                if(p>=0 && p<m && q>=0 && q<n && !mv.visited[p][q] && grid[p][q]==0){
                    Move newMv = new Move(p*n+q, mv.steps+1);
                    newMv.visited=mv.visited;
                    newMv.visited[p][q]=true;
                    distance[p][q]+=mv.steps+1;
                    if(distance[p][q]<min) {
                        if(++reach[p][q]==total) min = distance[p][q];
                        queue.offer(newMv);
                    }
                }
            }
        }
        return (min==Integer.MAX_VALUE)?-1: min;
    }

  • 0
    H

    @shuoshankou Isn't the time complexity O(#buildings * m^2 * n^2)? BFS's time complexity is O(|V||E|). Here we have mn vertices and the edges are proportional to m*n, so every BFS is O(m^2 * n^2). We do a BFS for every building so the total time complexity is O(#buildings * m^2 * n^2)?


  • 7
    M

    @harunrashidanver The time complexity for BFS/DFS is O(|V|+|E|), not O(|V||E|). In this problem, every vertex has up to 4 edges (left, right, up, down), so |E| ~ 4|V|. Thus, you have overall O(|V|) = O(mn) for a BFS. This has been proven for all sparse graphs like this problem. Now, we do a BFS for each building, so the overall complexity is O(#buildings*(mn)). In worst case, every vertex is a building. So the number of buildings is also upper bounded by O(mn), and thus you have O((mn)(mn)) = O(m^2n^2). This is a very loose bound since when every vertex is a building, we don't even need to do a BFS (nowhere to go).


  • 0
    W

    I thought there should be some better solution before.
    nice solution any way.


  • -1
    public int shortestDistance(int[][] grid) {
            int m = grid.length;
            if(m == 0) return 0;
            int n = grid[0].length;
            int count1 = 0;
            int[][] levelSum = new int[m][n];
            for(int i=0;i<m;i++){
                for(int j=0;j<n;j++){
                    if(grid[i][j] == 1){
                        count1++;
                        bfs(grid,levelSum,m,n,i,j);
                    }
                }
            }
            int res = Integer.MAX_VALUE;
            for(int i=0;i<m;i++){
                for(int j=0;j<n;j++){
                    if(levelSum[i][j] >= count1){
                        res = Math.min(res, levelSum[i][j]);
                    }
                }
            }
            return res == Integer.MAX_VALUE? -1:res;
        }
    
        void bfs(int[][] grid,int[][] levelSum,int m,int n,int i,int j){
            Queue<Point> q = new LinkedList();
            Set<Point> visited = new HashSet();
            Point root = new Point(i,j);
            q.offer(root);
            visited.add(root);
            int level = 0;
            while(!q.isEmpty()){
                int size = q.size();
                for(int k=0;k<size;k++){
                    Point node = q.poll();
                    int x = node.x, y = node.y;
                    levelSum[x][y] += level;
                    if(x-1>=0){
                        Point newNode = new Point(x-1,y);
                        if(!visited.contains(newNode) && grid[x-1][y] == 0){
                            q.offer(newNode);
                            visited.add(newNode);
                        }
                    }
                    if(x+1<m){
                        Point newNode = new Point(x+1,y);
                        if(!visited.contains(newNode) && grid[x+1][y] == 0){
                            q.offer(newNode);
                            visited.add(newNode);
                        }
                    }
                    if(y-1>=0){
                        Point newNode = new Point(x,y-1);
                        if(!visited.contains(newNode) && grid[x][y-1] == 0){
                            q.offer(newNode);
                            visited.add(newNode);
                        }
                    }
                    if(y+1<n){
                        Point newNode = new Point(x,y+1);
                        if(!visited.contains(newNode) && grid[x][y+1] == 0){
                            q.offer(newNode);
                            visited.add(newNode);
                        }
                    }
                }
                level++;
            }
        }
    
        class Point{
            int x;
            int y;
            Point(int x, int y){
                this.x = x;
                this.y = y;
            }
    
            @Override
            public int hashCode(){
                int result = 7;
                result = result * 31 + x;
                result = result * 31 + y;
                return result;
            }
    
            @Override
            public boolean equals(Object obj){
                if(obj == null) return false;
                Point p = (Point) obj;
                if(p.x == this.x && p.y == this.y) return true;
                else return false;
            }
        }

  • 0
    Y

    @coldknight your solution seems to be fine at the first glance, but just want to be clear, you did not stop in the middle when all of them meet at the first time right? You stop when the accumulated reachable distance is no more less than the minimum distance. Otherwise, test case like [[1,0,1],[2,0,2],[2,1,2]] would be wrong. Also, you might push land at the same locations multiple times to the queue.


  • 0
    F

    I feel like the time complexity should be mn time to find all 1's , then for each 1, we go through mn time to calculate distance at each empty space(0). Thus, it is m*n + k mn . Could that reach upper bound of m^2n^2?


Log in to reply
 

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