Java easiest DFS, quicker than BFS


  • 13

    Start from gates 0, use dfs to fill nearby rooms with distances, and return if (i, j) is out of boundary or has smaller distance filled.


    Version 1:


    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) dfs(rooms, i, j, 0);
            }
        }
    }
    
    public void dfs(int[][] rooms, int i, int j, int d) {
        if(i < 0 || i >= rooms.length || j < 0 || j >= rooms[0].length || rooms[i][j] < d) return;
        rooms[i][j] = d;
        dfs(rooms, i - 1, j, d + 1);
        dfs(rooms, i, j - 1, d + 1);
        dfs(rooms, i + 1, j, d + 1);
        dfs(rooms, i, j + 1, d + 1);
    }
    

    Version 2:


    int[][] dirs = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    
    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) {
                    dfs(rooms, i, j);
                }              
            }
        }
    }
    
    public void dfs(int[][] rooms, int i, int j) {
        for(int[] dir : dirs) {
            int x = i + dir[0], y = j + dir[1];
            if(x < 0 || x >= rooms.length || y < 0 || y >= rooms[0].length || rooms[x][y] <= rooms[i][j]) continue;
            rooms[x][y] = rooms[i][j] + 1;
            dfs(rooms, x, y);
        }
    }

  • 0
    A

    Dont you have to keep track of visited nodes, so that you dont keep recursing indefinitely?


  • 0
    A

    Actually, I see that you are using distance as a proxy to that. Great solution!


  • 0

    Thanks! Yeah in dfs function it will skip when smaller distances have been filled.


  • 1
    H

    Great solution! I find dfs better too. It is clever that you are using int[] dirs to avoid repeating code. Mine is similar:

       public class Solution {
            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) DFS(rooms, i, j, 0);
                    }
                }
            }
            
            private void DFS(int[][] rooms, int i, int j, int dist) {
                if (isRoom(rooms, i, j) && dist >= rooms[i][j]) return;
                rooms[i][j] = dist;
                if (i - 1 >= 0  && isRoom(rooms, i - 1, j)) DFS(rooms, i - 1, j, dist + 1);
                if (i + 1 < rooms.length && isRoom(rooms, i + 1, j)) DFS(rooms, i + 1, j, dist + 1);
                if (j - 1 >= 0 && isRoom(rooms, i, j - 1)) DFS(rooms, i, j - 1, dist + 1);
                if (j + 1 < rooms[0].length && isRoom(rooms, i, j + 1)) DFS(rooms, i, j + 1, dist + 1);
            }
            
            private boolean isRoom(int[][] rooms, int i, int j) {
                return rooms[i][j] != -1 && rooms[i][j] != 0;
            }
        }

  • 0

    @he17, great we have nearly the same solution!


  • 0
    Y

    Can I ask why dfs is much faster than bfs, which starts from gate and is also O(mn) time complexity?

    	int m = rooms.length;
    	if(m == 0) return;
    	int n = rooms[0].length;
    	
    	Queue<int[]> queue = new LinkedList<int[]>();
    	for(int i = 0 ; i< m; i++){
    		for(int j = 0; j<n; j++){
    			if(rooms[i][j] == GATE){
    				queue.offer(new int[]{i,j});
    			}
    		}
    	}
    	while(!queue.isEmpty()){
    		int[] point = queue.poll();
    		int row = point[0];
    		int col = point[1];
    		for(int[] direction: DIRECTIONS){
    			int r = row + direction[0];
    			int c = col + direction[1];
    			//here pay attention to condition rooms[r][c] != EMPTY
    			if(r >= m || r<0 || c >=n || c<0 || rooms[r][c] == WALL || rooms[r][c] != EMPTY){
    				continue;
    			}	
    			rooms[r][c] = rooms[row][col] + 1;
    			queue.offer(new int[]{r,c});
    		}
    	}

  • 0
    1. Unnecessary usage of Queue, queue.offer(), and queue.poll() and new int[] {i, j}.
    2. Notice we need to fill each empty room not nearest one. Why not use simpler and faster dfs?

  • 0
    Y

    I got your point, but if we use recursive solution, the performance will be bad if the point matrix goes quite big,right?


  • 0
    B

    In big O, the dfs if O(mn)^2 and the bfs is O(mn), right?

    So in an interview it'd be better to implement the bfs, since Big O is what they mostly care about?


  • 0

    @benji10, both are O(mn) man.


  • 0
    B

    I understand how bfs is O(mn) since you're guaranteed to visit each index only once by adding to the queue each index once. But it seems with DFS, you'll potentially have to overwrite a subset of the entire matrix because you found a better gate. Thus with mn potential gates and a subset of the matrix i might have to fix (mn), it seems dfs would be (mn)^2. May you explain a defect in my logic?


  • 0

    @benji10, I guess the dfs is not traversing all the cells. rooms[x][y] <= rooms[i][j], giving the pruning condition, it's gradually reduce by roughly half. For each gate, it at most need to traverse half of the existing un-optimized cells. The time complexity is roughly O(mn) + O(mn/2) + O(mn/4) + ... = O(2mn).

    Another perspective, is similar to problem: Best Meeting Point. x-axis, and y-axis, is actually independent. If you draw a simple example and consider the one dimensional situation, it'll be much clearer.

    // 16 cells example
    0   INF INF 0
    INF INF INF INF
    INF INF INF INF
    0   INF INF 0
    
    // Start: (0, 0), changed 12 cells <= N
    0 1 2 0
    1 2 3 4
    2 3 4 5
    0 4 5 0
    
    // Start: (0, 3),  changed 6 cells <= N / 2
    0 1 1 0
    1 2 2 1
    2 3 3 2
    0 4 4 0
    
    // Start: (3, 0),  changed 4 cells <= N / 4
    0 1 1 0
    1 2 2 1
    1 2 3 2
    0 1 2 0
    
    // Start: (3, 3),  changed 3 cells <= N / 4
    0 1 1 0
    1 2 2 1
    1 2 2 1
    0 1 1 0

  • 0
    I

    What is the time complexity then?


  • 0
    L

    Nice solution. Though I get a stack overflow in python.


  • 0
    E

    @yavinci I don't think your solution is O(mn). If there are k gates, and the grid is m x n, the worst case time complexity should be O(kmn). For a certain cell, it could be visited(updated) k times if the order of DFSs is from the furthest gate to the closest one.
    For example:

    0 0 0 0 0
    inf inf inf inf inf
    inf inf inf inf inf
    inf inf inf inf inf

    The time complexity should be

    O(mn) + O(m(n-1)) + O(m(n-2)) + ... + O(m) = O(mn^2).

    As is mentioned in https://discuss.leetcode.com/topic/35242/benchmarks-of-dfs-and-bfs, it shouldn't be O(mn) either, and your DFS code is faster than the others only in some scenarios.


Log in to reply
 

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