Surrounded Regions

mediumGraphs: BFS / DFS154 stepsJava · Python · C++

Capture every 'O' region that is fully surrounded by 'X'. Reverse the problem: any 'O' connected to the border can't be captured. Mark those safe with a DFS from every border 'O', then flip the rest to 'X' and restore the safe ones.

▶ Watch the animated trace

Traced input: board = [[X,X,X,X],[X,O,O,X],[X,X,O,X],[X,O,X,X]] → [["X", "X", "X", "X"], ["X", "X", "X", "X"], ["X", "X", "X", "X"], ["X", "O", "X", "X"]]. Original problem: neetcode.io/problems/surrounded-regions

Complexity

BestO(m·n)

AverageO(m·n)

WorstO(m·n)

SpaceO(m·n)

Each cell is visited a constant number of times.

Key idea

A region escapes capture only if it touches the border.
DFS from border 'O's and mark them (e.g. '#').
Final pass: 'O' → 'X' (captured), '#' → 'O' (safe).

Common mistakes

Trying to detect surrounded regions directly is much harder.
Forgetting the left/right border columns.

Solution

Java

// DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}: down, up, right, left
void solve(char[][] board) {
    int m = board.length, n = board[0].length;
    for (int r = 0; r < m; r++) {
        mark(board, r, 0);
        mark(board, r, n - 1);
    }
    for (int c = 0; c < n; c++) {
        mark(board, 0, c);
        mark(board, m - 1, c);
    }
    for (int r = 0; r < m; r++)
        for (int c = 0; c < n; c++) {
            if (board[r][c] == 'O') board[r][c] = 'X';
            else if (board[r][c] == '#') board[r][c] = 'O';
        }
}

void mark(char[][] board, int r, int c) {
    if (r < 0 || c < 0 || r >= board.length || c >= board[0].length || board[r][c] != 'O') return;
    board[r][c] = '#';
    for (int[] d : DIRS) mark(board, r + d[0], c + d[1]);
}

Python

# DIRS = [(1, 0), (-1, 0), (0, 1), (0, -1)]: down, up, right, left
def solve(board: List[List[str]]) -> None:
    m, n = len(board), len(board[0])

    def mark(r: int, c: int) -> None:
        if r < 0 or c < 0 or r >= m or c >= n or board[r][c] != 'O': return
        board[r][c] = '#'
        for dr, dc in DIRS: mark(r + dr, c + dc)

    for r in range(m):
        mark(r, 0)
        mark(r, n - 1)
    for c in range(n):
        mark(0, c)
        mark(m - 1, c)
    for r in range(m):
        for c in range(n):
            if board[r][c] == 'O': board[r][c] = 'X'
            elif board[r][c] == '#': board[r][c] = 'O'

C++

// DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}: down, up, right, left
void mark(vector<vector<char>>& board, int r, int c) {
    if (r < 0 || c < 0 || r >= (int)board.size() || c >= (int)board[0].size() || board[r][c] != 'O') return;
    board[r][c] = '#';
    for (auto& d : DIRS) mark(board, r + d[0], c + d[1]);
}

void solve(vector<vector<char>>& board) {
    int m = board.size(), n = board[0].size();
    for (int r = 0; r < m; r++) {
        mark(board, r, 0);
        mark(board, r, n - 1);
    }
    for (int c = 0; c < n; c++) {
        mark(board, 0, c);
        mark(board, m - 1, c);
    }
    for (int r = 0; r < m; r++)
        for (int c = 0; c < n; c++) {
            if (board[r][c] == 'O') board[r][c] = 'X';
            else if (board[r][c] == '#') board[r][c] = 'O';
        }
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
Region touching the border The column of O's reaches the top edge, so it's safe.	`board = [[X,O,X],[X,O,X],[X,X,X]]`	`[["X", "O", "X"], ["X", "O", "X"], ["X", "X", "X"]]`
Single cell A border cell is never captured.	`board = [[O]]`	`[["O"]]`
Fully enclosed The centre O is captured.	`board = [[X,X,X],[X,O,X],[X,X,X]]`	`[["X", "X", "X"], ["X", "X", "X"], ["X", "X", "X"]]`