My Java O(n^2) accepted solution


  • 26
    F

    The idea is pretty simple: a 'O' marked cell cannot be captured whether:

    1. It is in contact with the border of the board or
    2. It is adjacent to an unflippable cell.

    So the algorithm is straightforward:

    1. Go around the border of the board
    2. When a 'O' cell is found mark it with 'U' and perform a DFS on its adjacent cells looking for other 'O' marked cells.
    3. When the entire border is processed scan again the board
    • If a cell is marked as 'O' it wasn't connected to unflippable cell. Hence capture it with 'X'
    • If a cell is marked as 'X' nothing must be done.
    • If a cell is marked as 'U' mark it as 'O' because it was an original 'O' marked cell which satisfied one of the above conditions.

    On a technical side regarding the code:

    • In the problem statement it's not specified that the board is rectangular. So different checks must performed when scanning the border.
    • Since a pure recursive search causes stack overflow it's necessary to make the DFS iterative using a stack to simulate recursion.

    public class Solution {

    static class Pair {
        public int first;
        public int second;
        public Pair(int f, int s) {
            first = f;
            second = s;
        }
    }
    
    public void solve(char[][] board) {
        if(board == null || board.length == 0) {
            return ;
        }
        for(int i = 0; i < board[0].length; ++i) {
            if(board[0][i] == 'O') {
                markUnflippable(board,0,i);
            }
        }
        for(int i = 0; i < board[board.length-1].length; ++i) {
            if(board[board.length-1][i] == 'O') {
                markUnflippable(board,board.length-1,i);
            }
        }
        for(int i = 0 ; i < board.length; ++i) {
            if(board[i][0] == 'O') {
                markUnflippable(board,i,0);
            }
        }
        for(int i =0; i < board.length; ++i) {
            if(board[i][board[i].length-1] == 'O') {
                markUnflippable(board,i,board[i].length-1);
            }
        }
        
        // modify the board
        for(int i = 0; i < board.length; ++i) {
            for(int j = 0; j < board[i].length; ++j) {
                if(board[i][j] == 'O') {
                    board[i][j] = 'X';
                } else if(board[i][j] == 'U') {
                    board[i][j] = 'O';
                }
            }
        }
    }
    
    public void markUnflippable(char[][] board, int r, int c) {
        int[] dirX = {-1,0,1,0};
        int[] dirY = {0,1,0,-1};
        ArrayDeque<Pair> stack = new ArrayDeque<>();
        stack.push(new Pair(r,c));
        while(!stack.isEmpty()) {
            Pair p = stack.pop();
            board[p.first][p.second] = 'U';
            for(int i = 0; i < dirX.length; ++i) {
                if(p.first + dirX[i] >= 0 && p.first + dirX[i] < board.length && p.second + dirY[i] >= 0 && p.second +dirY[i] < board[p.first + dirX[i]].length && board[p.first+dirX[i]][p.second+dirY[i]] == 'O') {
                    stack.push(new Pair(p.first+dirX[i],p.second+dirY[i]));
                }
            }
        }
    }
    

    }


  • 12
    R

    I have the same idea as you do. Cheers!

        public class Solution {
        public void solve(char[][] board) {
            if(board==null||board.length==0||board[0].length==0) return;
            for(int i=0;i<board.length;i++) if(board[i][0]=='O') linkedUnit(board,i,0);
            for(int i=1;i<board[0].length;i++) if(board[0][i]=='O') linkedUnit(board,0,i);
            for(int i=1;i<board[0].length;i++) if(board[board.length-1][i]=='O') linkedUnit(board,board.length-1,i);
            for(int i=1;i<board.length-1;i++) if(board[i][board[0].length-1]=='O') linkedUnit(board,i,board[0].length-1);
            for(int i=0;i<board.length;i++){
                for(int j=0;j<board[0].length;j++){
                    if(board[i][j]=='1') board[i][j] = 'O';
                    else if(board[i][j]=='O') board[i][j] = 'X';
                    else continue;
                }
            }
        }
        private void linkedUnit(char[][] board, int x, int y){
            board[x][y] = '1';
            if(x-1>0&&board[x-1][y]=='O') linkedUnit(board, x-1, y);
            if(x+1<board.length&&board[x+1][y]=='O') linkedUnit(board, x+1, y);
            if(y-1>0&&board[x][y-1]=='O') linkedUnit(board, x, y-1);
            if(y+1<board[x].length&&board[x][y+1]=='O') linkedUnit(board, x, y+1);
        }
    }

  • 0
    C

    I implement BFS by implementing ArrayDeque as a queue, not stack. But limited time exceeds. Can someone explain this ?


  • 0
    O

    I suddenly feel your alg is BFS, rather than DFS...
    Is my feeling right?


  • 0
    O

    No, I am wrong. It's DFS, you are right.


  • 0
    G

    Best solution


Log in to reply
 

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