Java 4ms Beats 95.14% (with comments)


  • 0
    W

    The idea is similar to sugeladi's solution at https://discuss.leetcode.com/topic/17224/a-really-simple-and-readable-c-solution-only-cost-12ms

    First, we find all 'O' nodes at the boundaries/borders of the matrix and replace all 'O' nodes connected to these boundary 'O' nodes with '0'.
    These '0' nodes will be the only surviving non-'X' nodes in the matrix.

    Then, we go through the whole matrix to replace the remaining 'O' nodes with 'X'.
    At last, change the surviving '0' nodes back to 'O'.

    public void solve(char[][] board) {
        if(board.length <= 0) {return;}
        // visit the "left" and "right" boundary nodes
        for(int i=0; i<board.length; i++) {
            if (board[i][0] == 'O') {
                sink(board, i, 0);
            }
            if (board[i][board[i].length-1] == 'O') {
                sink(board, i, board[i].length-1);
            }
        }
        // visit the "upper" and "bottom" boundary nodes
        // loop from j=1 to board[0].length-1 to avoid revisiting the corner nodes
        for(int j=1; j<board[0].length-1; j++) {
            if (board[0][j] == 'O') {
                sink(board, 0, j);
            }
            if (board[board.length-1][j] == 'O') {
                sink(board, board.length-1, j);
            }
        }
        
        
        for(int i=0; i<board.length; i++) {
            for(int j=0; j<board[0].length; j++) {
                if(board[i][j] == 'O') {
                   board[i][j] = 'X'; 
                }
            }
        }
        for(int i=0; i<board.length; i++) {
            for(int j=0; j<board[0].length; j++) {
                if(board[i][j] == '0') {
                   board[i][j] = 'O'; 
                }
            }
        }
        
    }
    
    public void sink(char[][] board, int x, int y) {
        board[x][y] = '0';
        if(x > 0 && board[x-1][y]=='O') {
            sink(board, x-1, y);
        }
        // check x < board.length-2 so that we don't revisit the boundary nodes (if you don't do this, a test case will cause stackoverflow)
        if(x < board.length-2 && board[x+1][y]=='O') {
            sink(board, x+1, y);
        }
        // similarly, check  y < board[x].length-2 so that we don't revisit the boundary nodes (if you don't do this, a test case will cause stackoverflow)
        if(y < board[x].length-2 && board[x][y+1]=='O') {
            sink(board, x, y+1);
        }
        if(y > 0 && board[x][y-1]=='O') {
            sink(board, x, y-1);
        }
    }

Log in to reply
 

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