Loop Solution - Surrounded Regions - Opposite thinking

The tricky and tough part of this problem is to think in opposite way… instead of marking O, first find all Os on boundaries, which are not surrounded… and mark all next Os to 'B' (any letter)… then paint all O to X, then paint B back to O…

Another key is to recursively paint boundaries Os and next Os to be B… so separate verification for in Board and boundaries makes the code cleaner… and only if O then recursive avoid duplicates calls inter leaved between Os (to find next Os)


public class Solution {
    public void solve(char[][] board) {
        if(board == null || board.length == 0){
            return;
        }
        for(int i = 0; i < board[0].length; i++){
            markBoundary(board, 0, i);
        }
        for(int i = 0; i < board[board.length - 1].length; i++){
            markBoundary(board, board.length - 1, i);
        }
        for(int i = 1; i < board.length - 1; i++){
            markBoundary(board, i, 0);
            markBoundary(board, i, board[0].length - 1);
        }
        for(int i =  1; i < board.length - 1; i++){
            for(int j = 1; j < board[0].length - 1; 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] == 'B'){
                    board[i][j] = 'O';
                }
            }
        }
    }
    private boolean isBoundary(char[][] board, int x, int y){
        if(x == 0 || x == board.length - 1 || y == 0 || y == board[0].length - 1){
            return true;
        }
        return false;
    }
    private boolean isInBoard(char[][] board, int x, int y){
        if(x >= board.length || x < 0 || y >= board[0].length || y < 0){
            return false;
        }
        return true;
    }
    private void markBoundary(char[][] board, int x, int y){
        if(board[x][y] == 'O'){
            board[x][y] = 'B';
            if(isInBoard(board, x - 1, y) && !isBoundary(board, x - 1, y)){
                markBoundary(board, x - 1, y);
            }
            if(isInBoard(board, x + 1, y) && !isBoundary(board, x + 1, y)){
                markBoundary(board, x + 1, y);
            }
            if(isInBoard(board, x, y - 1) && !isBoundary(board, x, y - 1)){
                markBoundary(board, x, y - 1);
            }
            if(isInBoard(board, x, y + 1) && !isBoundary(board, x, y + 1)){
                markBoundary(board, x, y + 1);
            }
        }
    }
}