# Why one line make such big difference in the Time Complexity

• I using BFS to solve this problem. A little bug here make me stuck on this problem whole afternoon. Before I fixed the bug, it was TimeLimitExceeded. After I reordered, it passed.

Only the position of code ''' board[xNew][yNew] = 'Y' ''' changed.

Bug Code:

'''
public class Solution {
public void solve(char[][] board) {
if (board == null || board.length == 0 || board[0].length == 0){
return;
}
int row = board.length;
int col = board[0].length;
int[] dx = new int[]{0, 1, 0, -1};
int[] dy = new int[]{1, 0, -1, 0};
for (int i = 0; i < row; i++){
for (int j = 0; j < col; j++){
if (i == 0 || i == row - 1 || j == 0 || j == col - 1){
if (board[i][j] == 'O'){
queue.offer(i * col + j);
board[i][j] = 'Y';
while (!queue.isEmpty()){
int curr = queue.poll();
int currX = curr / col;
int currY = curr % col;
board[currX][currY] = 'Y';
for (int k = 0; k < 4; k++){
int xNew = currX + dx[k];
int yNew = currY + dy[k];
if (xNew >= 0 && xNew < row && yNew >= 0 && yNew < col && board[xNew][yNew] == 'O'){
queue.offer(xNew * col + yNew);
}
}
}
}
}
}
}

``````    for (int i = 0; i < row; i++){
for (int j = 0; j < col; j++){
if (board[i][j] == 'Y'){
board[i][j] = 'O';
} else if (board[i][j] == 'O'){
board[i][j] = 'X';
}
}
}
}
``````

}
''''

Correct Code:

'''
public class Solution {
public void solve(char[][] board) {
if (board == null || board.length == 0 || board[0].length == 0){
return;
}
int row = board.length;
int col = board[0].length;
int[] dx = new int[]{0, 1, 0, -1};
int[] dy = new int[]{1, 0, -1, 0};
for (int i = 0; i < row; i++){
for (int j = 0; j < col; j++){
if (i == 0 || i == row - 1 || j == 0 || j == col - 1){
if (board[i][j] == 'O'){
queue.offer(i * col + j);
board[i][j] = 'Y';
while (!queue.isEmpty()){
int curr = queue.poll();
int currX = curr / col;
int currY = curr % col;
for (int k = 0; k < 4; k++){
int xNew = currX + dx[k];
int yNew = currY + dy[k];
if (xNew >= 0 && xNew < row && yNew >= 0 && yNew < col && board[xNew][yNew] == 'O'){
queue.offer(xNew * col + yNew);
board[xNew][yNew] = 'Y';
}
}
}
}
}
}
}

``````    for (int i = 0; i < row; i++){
for (int j = 0; j < col; j++){
if (board[i][j] == 'Y'){
board[i][j] = 'O';
} else if (board[i][j] == 'O'){
board[i][j] = 'X';
}
}
}
}
``````

}

''''

Why the position of this line code make such difference, thanks!

• Sorry for the format...
First time to post the code

Bug Code:

``````public class Solution {
public void solve(char[][] board) {
if (board == null || board.length == 0 || board[0].length == 0){
return;
}
int row = board.length;
int col = board[0].length;
int[] dx = new int[]{0, 1, 0, -1};
int[] dy = new int[]{1, 0, -1, 0};
for (int i = 0; i < row; i++){
for (int j = 0; j < col; j++){
if (i == 0 || i == row - 1 || j == 0 || j == col - 1){
if (board[i][j] == 'O'){
queue.offer(i * col + j);
board[i][j] = 'Y';
while (!queue.isEmpty()){
int curr = queue.poll();
int currX = curr / col;
int currY = curr % col;
board[currX][currY] = 'Y';
for (int k = 0; k < 4; k++){
int xNew = currX + dx[k];
int yNew = currY + dy[k];
if (xNew >= 0 && xNew < row && yNew >= 0 && yNew < col && board[xNew][yNew] == 'O'){
queue.offer(xNew * col + yNew);
}
}
}
}
}
}
}
for (int i = 0; i < row; i++){
for (int j = 0; j < col; j++){
if (board[i][j] == 'Y'){
board[i][j] = 'O';
} else if (board[i][j] == 'O'){
board[i][j] = 'X';
}
}
}
}
}

``````

Correct Code:

``````public class Solution {
public void solve(char[][] board) {
if (board == null || board.length == 0 || board[0].length == 0){
return;
}
int row = board.length;
int col = board[0].length;
int[] dx = new int[]{0, 1, 0, -1};
int[] dy = new int[]{1, 0, -1, 0};
for (int i = 0; i < row; i++){
for (int j = 0; j < col; j++){
if (i == 0 || i == row - 1 || j == 0 || j == col - 1){
if (board[i][j] == 'O'){
queue.offer(i * col + j);
board[i][j] = 'Y';
while (!queue.isEmpty()){
int curr = queue.poll();
int currX = curr / col;
int currY = curr % col;
for (int k = 0; k < 4; k++){
int xNew = currX + dx[k];
int yNew = currY + dy[k];
if (xNew >= 0 && xNew < row && yNew >= 0 && yNew < col && board[xNew][yNew] == 'O'){
queue.offer(xNew * col + yNew);
board[xNew][yNew] = 'Y';
}
}
}
}
}
}
}
for (int i = 0; i < row; i++){
for (int j = 0; j < col; j++){
if (board[i][j] == 'Y'){
board[i][j] = 'O';
} else if (board[i][j] == 'O'){
board[i][j] = 'X';
}
}
}
}
}
``````

• I have the same problem. And I guess its because when you flag the board[i][j] earlier, it will not be put into the queue repeatedly by next loop iterating the queue.

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