Beautiful Java Solution 10 lines.


  • 19
    D
    public class Solution {
    int[][] dir ={{0,1},{0,-1},{1,0},{-1,0}};
    public void wallsAndGates(int[][] rooms) {
        for(int i=0;i<rooms.length;i++){
            for(int j=0;j<rooms[0].length;j++){
                if(rooms[i][j]==0)
                    bfs(rooms,i,j);
            }
        }
    }
    public void bfs(int[][] rooms,int i,int j){
        for(int[] d:dir){
            if(i+d[0]>=0 && i+d[0]<rooms.length && j+d[1]>=0 && j+d[1]<rooms[0].length && rooms[i+d[0]][j+d[1]]>rooms[i][j]+1){
                rooms[i+d[0]][j+d[1]]=rooms[i][j]+1;
                bfs(rooms,i+d[0],j+d[1]);
            }
        }
    }
    

    }


  • 6

    I tested, and this solution is very efficient compared to queue!
    One thing: Isn't this dfs? It does recursion and recursion until exhausted. Then it comes back from the recursion stack.


  • 0
    D
    This post is deleted!

  • 1
    D

    It is DFS but only faster because it does't revisit optimized cell
    due to the additional condition rooms[i+d[0]][j+d[1]]>rooms[i][j]+1


  • 0
    S

    I wonder what is the time complexity? I tried to analyze it but couldn't figure it out. Thanks!


  • 1
    R

    good solutions! But I think it is the dfs not the bfs right?


  • 0
    Y

    yep, i think it is bfs.


  • 0
    B

    Isn't this solution O(n^2) where n is the total number of cells?


  • 0
    B

    Isn't this solution O(n^2) where n is the total number of cells?


  • 0
    H

    it is dfs, a long line that really does not make it beautiful and readable


  • 0
    Y

    No, the complexity is O(m + n) with m the number of rows and n the number of columns. This is a DFS and we only visit the cells that does not have an optimized distance. However, you can add a constant which is the number of gates since we are visiting all the cells starting from those gates, so it can be O(km + kn) with k the number of gates, yet k is a constant and can be ignored.


  • 0
    C
    This post is deleted!

  • 0
    M

    Its not O(m+n). Its O(mn). Just the initial for loops itself takes mn, so it is mn+kmn where is k is gates, which is O(mn)


  • 0
    D

    No, benji10 is right. It's O(n^2) where n is total number of cells.
    It is O(mn + kmn) where k is gates, however in worst case k is also m*n.


  • 0
    D

    And DFS is not a better choice compared to BFS for this problem. It runs faster only because the test case is weak, despite that Queue is much slower than simple recursion.


  • 0
    M

    True that in worst case.


Log in to reply
 

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