Intuition

An ‘O’ survives only if it can reach the border. So mark every border-connected ‘O’ as safe first; then every remaining ‘O’ is surrounded and gets flipped.

Approach

DFS/BFS from every ‘O’ on the border, marking reachable ‘O’s as safe (temporary marker).
Scan the board: flip unmarked ‘O’ to ‘X’.
Restore the safe markers back to ‘O’.

Complexity

Time — O(m*n): each cell visited a constant number of times.
Space — O(m*n): recursion/queue worst case.

Common Pitfalls

Mark border-safe cells first; deciding capture per-cell without that global info is wrong.

Full Solution — all languages

class Solution:
    def solve(self, board):
        if not board: return
        R,C=len(board),len(board[0])
        def dfs(r,c):
            if r<0 or r>=R or c<0 or c>=C or board[r][c]!='O': return
            board[r][c]='#'
            dfs(r+1,c); dfs(r-1,c); dfs(r,c+1); dfs(r,c-1)
        for r in range(R):
            dfs(r,0); dfs(r,C-1)
        for c in range(C):
            dfs(0,c); dfs(R-1,c)
        for r in range(R):
            for c in range(C):
                if board[r][c]=='O': board[r][c]='X'
                elif board[r][c]=='#': board[r][c]='O'

import java.util.*;

class Solution {
    public void solve(char[][] board) {
        int R=board.length,C=board[0].length; for(int r=0;r<R;r++){dfs(board,r,0);dfs(board,r,C-1);} for(int c=0;c<C;c++){dfs(board,0,c);dfs(board,R-1,c);} for(int r=0;r<R;r++)for(int c=0;c<C;c++){if(board[r][c]=='O')board[r][c]='X';else if(board[r][c]=='#')board[r][c]='O';}
    }
    void dfs(char[][] board,int r,int c){int R=board.length,C=board[0].length; if(r<0||r>=R||c<0||c>=C||board[r][c]!='O')return; board[r][c]='#'; dfs(board,r+1,c);dfs(board,r-1,c);dfs(board,r,c+1);dfs(board,r,c-1);
    }
}

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    void solve(vector<vector<char>>& board) {
        int R=board.size(),C=board[0].size(); function<void(int,int)> dfs=[&](int r,int c){if(r<0||r>=R||c<0||c>=C||board[r][c]!='O')return;board[r][c]='#';dfs(r+1,c);dfs(r-1,c);dfs(r,c+1);dfs(r,c-1);}; for(int r=0;r<R;r++){dfs(r,0);dfs(r,C-1);} for(int c=0;c<C;c++){dfs(0,c);dfs(R-1,c);} for(int r=0;r<R;r++)for(int c=0;c<C;c++){if(board[r][c]=='O')board[r][c]='X';else if(board[r][c]=='#')board[r][c]='O';}
    }
};

/**
 * @param {character[][]} board
 * @return {character[][]}
 */
var solve = function(board) {
    const R=board.length,C=board[0].length; function dfs(r,c){if(r<0||r>=R||c<0||c>=C||board[r][c]!=='O')return;board[r][c]='#';dfs(r+1,c);dfs(r-1,c);dfs(r,c+1);dfs(r,c-1);} for(let r=0;r<R;r++){dfs(r,0);dfs(r,C-1);} for(let c=0;c<C;c++){dfs(0,c);dfs(R-1,c);} for(let r=0;r<R;r++)for(let c=0;c<C;c++){if(board[r][c]==='O')board[r][c]='X';else if(board[r][c]==='#')board[r][c]='O';}
};

Surrounded Regions

Example 1

Constraints