Surrounded Regions: the idea to remember.

The core insight

Flood fill O cells reachable from the border, flip all other O cells, then restore marked cells.

Why it works

A region is surrounded exactly when no path of O cells reaches a board boundary.

The mistake to avoid

Start from all four borders. Diagonal contact does not protect a region.

Commented Java solution

Use java.util.* imports and a surrounding solution class. Tree snippets assume the standard TreeNode definition; linked lists use ListNode and Clone Graph uses a Node with val and neighbors; Copy Random List uses Node with val, next and random. Read the input assumptions above.

// Java reference adapted from neetcode-gh/leetcode (MIT).
// Flood fill O cells reachable from the border, flip all other O cells, then restore marked cells.
public void solve(char[][] board) {
    int nRows = board.length;
    int nCols = board[0].length;


    for (int i = 0; i < nCols; i++) {
        if (board[0][i] == 'O') dfs(board, 0, i);
        if (board[nRows - 1][i] == 'O') dfs(board, nRows - 1, i);
    }


    for (int i = 0; i < nRows; i++) {
        if (board[i][0] == 'O') dfs(board, i, 0);
        if (board[i][nCols - 1] == 'O') dfs(board, i, nCols - 1);
    }

    for (int r = 0; r < nRows; r++) {
        for (int c = 0; c < nCols; c++) {
            if (board[r][c] == 'O') board[r][c] = 'X'; 
            if (board[r][c] == 'T') board[r][c] = 'O'; 
        }
    }
}

private void dfs(char[][] board, int r, int c) {
    int nRows = board.length;
    int nCols = board[0].length;
    if (
        r < 0 || c < 0 || r >= nRows || c >= nCols || board[r][c] != 'O'
    ) return;

    board[r][c] = 'T';
    dfs(board, r + 1, c);
    dfs(board, r - 1, c);
    dfs(board, r, c + 1);
    dfs(board, r, c - 1);
}

Java reference adapted from neetcode-gh/leetcode · MIT license

Make the next connection