# Why is DFS passed while BFS exceeds time limit

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

• If you are using a queue, make sure not to enqueue the already marked element's

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

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