Why is DFS passed while BFS exceeds time limit


  • 2
    D

    Started from boundaries, all the neighboring entries are set to be 'S'. Then traverse the entire matrix, make all 'O's become 'X' and all 'S' to be 'O'.

    This is my code that passed OJ:
    Note the piece

    Stack<int[]> q = new Stack<int[]>(); 
    

    if Queue is used instead of Stack, it always exceeds the time limit, no matter what implementation of Queue I use(LinkedList, ArrayDeque)

    The difference in coding BFS and DFS are minor and one only need to modify the Stack/Queue, poll/pop.

    Does that mean DFS in this problem is faster? If so, why? Or, is there anything improper in my code? Is there an efficient way to implement BFS?

    public class Solution {
        public void solve(char[][] board) {
            int m = board.length; 
            if(m == 0) return;
            int n = board[0].length;
            
            for(int i = 0; i < m; i++) if(board[i][0] == 'O' ) recordOpenEntries(board,i,0); 
            for(int i = 0; i < m; i++) if(board[i][n-1] == 'O') recordOpenEntries(board,i,n-1); 
            for(int i = 1; i < n-1; i++) if(board[0][i] == 'O') recordOpenEntries(board,0,i); 
            for(int i = 1; i < n-1; i++) if(board[m-1][i] == 'O') recordOpenEntries(board,m-1,i);
            
            for(int i = 0; i < m ; i++) {
                for(int j = 0; j < n ; j++) {
                    if(board[i][j] == 'O') board[i][j] = 'X';
                    if(board[i][j] == 'S') board[i][j] = 'O';
                }
            }
        }
        private void recordOpenEntries(char[][] board, int i0, int j0) {
                    int m = board.length; int n = board[0].length;
                    Stack<int[]> q = new Stack<int[]>(); 
                    int[] index0 = new int[2]; 
                    index0[0] = i0; index0[1] =j0; q.add(index0); 
                    while(!q.isEmpty()) { 
                        int[] p = q.pop();
                        board[p[0]][p[1]] = 'S';
                        if(p[0] > 0 && board[p[0] -1][p[1]] == 'O')  
                            {int[] index = new int[2];index[0] =p[0] -1; index[1] =p[1]; q.push(index);} 
                        if(p[0] < m - 1 && board[p[0] +1][p[1]] == 'O')  
                            {int[] index = new int[2];index[0] =p[0] +1; index[1] =p[1]; q.push(index);} 
                        if(p[1] > 0 &&  board[p[0] ][p[1]-1] == 'O')  
                            {int[] index = new int[2];index[0] =p[0]; index[1] =p[1]-1; q.push(index);} 
                        if(p[1] < n - 1 && board[p[0]][p[1]+1] == 'O')  
                            {int[] index = new int[2];index[0] =p[0]; index[1] =p[1]+1; q.push(index);}
                    }
        }
    }

  • 5
    C

    If you are using a queue, make sure not to enqueue the already marked element's
    neighbors in your bfs:

    if board[p[0]][p[1]] == 'S':
        continue
    

    Below shows why queue brings duplication without the lines above:

    Suppose a, b, c, d, e, f all marked with 'O' and line up as:

     a   b   c
     d   e   f
    

    Now if current queue has ab in it, then the queue goes as follow:

    ab --> bbd --> bdce --> dcece --> cecee --> eceff --> cefff --> effff --> fffff --> ... --> STOP

    What happens when it is stack?

    ab --> ace --> acdf --> acdc --> acd --> ac --> a --> STOP

    As you can see, stack also brings in duplicates, but because dfs goes as deep as possible,
    the duplicates are much fewer than those in queue.


Log in to reply
 

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