# Beautiful Java Solution 10 lines.

• ``````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]);
}
}
}
``````

}

• 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.

• This post is deleted!

• 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

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

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

• yep, i think it is bfs.

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

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

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

• 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.

• This post is deleted!

• 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)

• 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.

• 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.

• True that in worst case.

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