Why one line make such big difference in the Time Complexity


  • -1
    B

    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};
    Queue<Integer> queue = new LinkedList<>();
    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};
    Queue<Integer> queue = new LinkedList<>();
    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!


  • 0
    B

    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};
            Queue<Integer> queue = new LinkedList<>();
            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};
            Queue<Integer> queue = new LinkedList<>();
            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';
                    }
                }
            }
        }
    }
    

  • 0
    C

    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.


Log in to reply
 

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