Surrounded Regions — Solution

Problem

Given an m×n grid of 'X' and 'O' characters, flip every 'O' cell that is completely enclosed by 'X' cells. An 'O' is considered safe — never flipped — if it sits on the border or is connected to a border 'O' through a chain of adjacent 'O' cells.

• Input: board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
• Output: [["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]
• Explanation: The three interior O's form a cluster with no path to the border, so they are captured; the O in the bottom row sits on the border and is left alone.

Counter-example — a single-cell board is trivially on the border and nothing is ever captured:

• Input: board = [["O"]]
• Output: [["O"]]

Intuition

Trying to find surrounded regions by searching inward is tricky — you'd need to check whether every O cluster can reach the border. It's far simpler to flip the question: start from the border and flood outward, marking every O reachable from an edge as safe. Once that pass is done, any remaining O has no escape route and must be captured.

Solution — Border-First DFS

Mark all O cells reachable from a border O as temporarily safe, then flip everything that remains unmarked.

1. Scan all four border edges (top row, bottom row, left column, right column).
2. For each border 'O' found, run DFS in all four directions, overwriting connected O cells with a sentinel 'S' to flag them as safe.
3. DFS terminates at grid boundaries, 'X' cells, and already-visited 'S' cells.
4. After the full border scan, make one pass over the board: flip 'O' → 'X' (surrounded) and restore 'S' → 'O' (safe).

1def solve(board: list[list[str]]) -> None:
2    if not board or not board[0]:
3        return
4    rows, cols = len(board), len(board[0])
5
6    def dfs(row: int, col: int) -> None:
7        if row < 0 or row >= rows or col < 0 or col >= cols:
8            return
9        if board[row][col] != 'O':
10            return
11        board[row][col] = 'S'  # sentinel: reachable from border, never captured
12        dfs(row + 1, col)
13        dfs(row - 1, col)
14        dfs(row, col + 1)
15        dfs(row, col - 1)
16
17    for row in range(rows):
18        dfs(row, 0)           # left column
19        dfs(row, cols - 1)    # right column
20    for col in range(cols):
21        dfs(0, col)           # top row
22        dfs(rows - 1, col)    # bottom row
23
24    for row in range(rows):
25        for col in range(cols):
26            if board[row][col] == 'O':
27                board[row][col] = 'X'   # surrounded — capture
28            elif board[row][col] == 'S':
29                board[row][col] = 'O'   # restore safe cell

Time: O(m·n) — each cell is visited at most once across all DFS calls.
Space: O(m·n) — the DFS call stack can reach the full board size when the entire grid is 'O'.

Complexity Summary

Common Mistakes

• Searching inward instead of outward — starting DFS from every interior O to check whether it reaches the border requires tracking the full frontier per region, which is more complex; seeding from the border is both simpler and faster.
• Flipping O's to X's during the DFS pass — overwriting in place loses the distinction between original X's and newly captured O's; the sentinel 'S' keeps the two phases separate.
• Treating border cells as candidates for capture — O's on row 0, row m-1, col 0, or col n-1 are by definition not surrounded; the DFS must start from them, not skip them.
• Scanning fewer than all four borders — you need to seed DFS from every cell in each of the four edge rows/columns; missing even one edge leaves some safe O's incorrectly captured.
• Recursive DFS stack overflow on large boards — a 200×200 board filled with O's produces ~40,000 recursive frames; switch to iterative BFS with a deque for production code on boards near the constraint limit.

Related Problems

• Number of Islands — same flood fill structure; counts disconnected O components instead of capturing them
• Max Area of Island — flood fill that accumulates region size rather than marking for capture
• Flood Fill — textbook single-source flood fill, the direct building block of this problem
• Rotting Oranges — multi-source BFS spreading outward from known cells, the same border-seeding intuition applied to a timed spread
• 01 Matrix — multi-source BFS from all 0-cells mirrors seeding from borders; both avoid interior-out searching