Java BFS Solution-O(mn) Time


  • 143
    C

    Push all gates into queue first. Then for each gate update its neighbor cells and push them to the queue.

    Repeating above steps until there is nothing left in the queue.

    public class Solution {
        public void wallsAndGates(int[][] rooms) {
            if (rooms.length == 0 || rooms[0].length == 0) return;
            Queue<int[]> queue = new LinkedList<>();
            for (int i = 0; i < rooms.length; i++) {
                for (int j = 0; j < rooms[0].length; j++) {
                    if (rooms[i][j] == 0) queue.add(new int[]{i, j});
                }
            }
            while (!queue.isEmpty()) {
                int[] top = queue.remove();
                int row = top[0], col = top[1];
                if (row > 0 && rooms[row - 1][col] == Integer.MAX_VALUE) {
                    rooms[row - 1][col] = rooms[row][col] + 1;
                    queue.add(new int[]{row - 1, col});
                }
                if (row < rooms.length - 1 && rooms[row + 1][col] == Integer.MAX_VALUE) {
                    rooms[row + 1][col] = rooms[row][col] + 1;
                    queue.add(new int[]{row + 1, col});
                }
                if (col > 0 && rooms[row][col - 1] == Integer.MAX_VALUE) {
                    rooms[row][col - 1] = rooms[row][col] + 1;
                    queue.add(new int[]{row, col - 1});
                }
                if (col < rooms[0].length - 1 && rooms[row][col + 1] == Integer.MAX_VALUE) {
                    rooms[row][col + 1] = rooms[row][col] + 1;
                    queue.add(new int[]{row, col + 1});
                }
            }
        }
    }

  • 0
    F

    this algorithm won't work in the following case:

    INF INF 0 INF\n
    INF INF INF INF\n
    INF INF INF INF\n
    INF 0 INF INF

    this can be fixed easily by comparing the current distance in each iteration


  • 1
    C

    Hi @fan22, thanks for your comment. But what do you mean by "won't work" ? Raises error or wrong answer? I tested this case on my laptop and it generated following matrix:
    2 1 0 1\n
    3 2 1 2\n
    2 1 2 3\n
    1 0 1 2\n
    It should be correct. Why do you think this algorithm does not work for your case?


  • 0
    F

    Hi @chase1991. Sorry it was my bad, I misundersood the algorithm. Your algorithm works perfectly! Thanks for the responding! :P


  • 0
    C

    No problem. Feel free to remind me if you find any problems in my code.

    Thanks.


  • 23
    K

    Similar idea! Simplified the logic for finding adjacent nodes.

    public class Solution {
        public void wallsAndGates(int[][] rooms) {
            LinkedList<int[]> list = new LinkedList<int[]>();
            for(int i = 0; i < rooms.length; i++) {
                for(int j = 0; j < rooms[0].length; j++) {
                    if(rooms[i][j] == 0) 
                        list.add(new int[]{i,j});
                }
            }
            int[][] diff = new int[][]{{-1,0,1,0},{0,1,0,-1}};
            while(!list.isEmpty()) {
                int[] pop = list.remove();
                for(int i = 0; i < diff[0].length; i++) {
                    int newR = pop[0] + diff[0][i];
                    int newC = pop[1] + diff[1][i];
                    if(newR < 0 || newR >= rooms.length || newC < 0 || newC >= rooms[0].length || 
                        rooms[newR][newC] != Integer.MAX_VALUE) 
                        continue;
                    rooms[newR][newC] = rooms[pop[0]][pop[1]] + 1;
                    list.add(new int[]{newR, newC});
                }
            }
        }
    }

  • 8
    S

    At first glance, I am not quite sure how this algorithm works. After thinking about it for a little while, I understood it in an easy way: imagining there is a psuedo "final gate", and all the gates form its neighbors set with distance 0, what is the shortest distance for each empty room to this psuedo "final gate"? BFS WORKS PERFECTLY HERE. Hopefully this understanding helps. Thanks chase1991 for the solution.


  • 0
    R

    Nice solution!! Thank you for sharing!


  • 0
    M
    This post is deleted!

  • 0
    S

    Thank you for your brilliant solution!


  • 0
    A

    I am wondering how the algorithm make sure the result is the shortest distance for every room? I saw some other solutions with a hashset to record if that room being visited or not and update the distance every time.


  • 0
    I

    The readability is poor here.


  • 0

    Could anyone explain why the time complexity is O(mn) not O(n)? In this BFS, I think each room or entry in the matrix is only visited once, and should also be inspected for at most 4 times from 4 directions, which will make the BFS a O(n) operation. Did I miss anything?


  • 2
    N

    I don't see how this makes sure the shortest distance is found!
    Once a room is discovered, it will not be traversed again (the == INF check), and thus will never get updated. What am I missing?


  • 0
    S

    you are right but also keep in mind that the matrix has m * n entries.


  • 2
    S

    @netanelkl the bfs algorithm guaranteed that when the empty room is discovered firstly, the distance is the shortest.


  • 0
    L

    @sherlywang Yes, that is from only one gate, but we may have many gates here, I think we have to continue to update the shortest distance


  • 0
    L

    @sherlywang Ok, just understand what happened here, this solution is awesome!


  • 23

    Here's my understanding of why this solution guarantees the shortest distance.
    We can understand it by level-order BFS.
    First we put all 0s to a queue, let's say these these 0s are in level 1. Then from each 0 of the queue, we will go up, down, left and right, all these positions that are rooms are at level 1, and so forth. So assume we only have Gate A and Gate B, and we have a room C and all the other positions are walls. Assume that distance between AC is 3 and distance between BC is 4. So for Gate A, room C is at its level 3, for Gate B, room C is at its level 4. Since we are doing level-order BFS, so C will always first be accessed by the gate that is closer to it, so it will be A.

    If you still feel it hard to understand, the above code can be written as following alternatively:

    public void wallsAndGates(int[][] rooms) {
            int m = rooms.length;
            if(m == 0)  return;
            int n = rooms[0].length;
            if(n == 0)  return;
            
            Queue<int[]> q = new LinkedList<>();
            for(int i = 0; i < m; i++){
                for(int j = 0; j < n; j++){
                    if(rooms[i][j] == 0)
                        q.offer(new int[] {i, j});
                }
            }
            
            int inf = Integer.MAX_VALUE;
            while(!q.isEmpty()){
                int size = q.size();
                for(int i = 0; i < size; i++){
                    int[] cur = q.poll();
                    int row = cur[0];
                    int col = cur[1];
                    if(row-1 >= 0 && rooms[row-1][col] == inf){
                        rooms[row-1][col] = rooms[row][col]+1;
                        q.offer(new int[] {row-1, col});
                    }
                    if(row+1 < m && rooms[row+1][col] == inf){
                        rooms[row+1][col] = rooms[row][col]+1;
                        q.offer(new int[] {row+1, col});
                    }
                    if(col-1 >= 0 && rooms[row][col-1] == inf){
                        rooms[row][col-1] = rooms[row][col]+1;
                        q.offer(new int[] {row, col-1});
                    }
                    if(col+1 < n && rooms[row][col+1] == inf){
                        rooms[row][col+1] = rooms[row][col]+1;
                        q.offer(new int[] {row, col+1});
                    }
                }
            }
        }
    

  • 0
    H

    @chase1991 Thanks for the solution. I just have one little question. When you confirm the new down/left direction of BFS traversal for row and left, why row/left > 0 instead of row/left >= 0?


Log in to reply
 

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