Generated by Codex with GPT-5

Quick facts

• Difficulty: MEDIUM
• Problem: Surrounded Regions
• Main tags: Array, Depth-First Search, Breadth-First Search, Union-Find, Matrix

What the problem is really asking

The board contains X and O. The task is to flip only the O cells that belong to regions fully enclosed by X.

The important phrase is “surrounded region.” A region is safe if it can reach the border through adjacent O cells. A region is captured only if there is no such path.

That means the real question is not:

“Which O cells are inside?”

It is:

“Which O cells are connected to the border, and therefore must stay O?”

Once that is clear, the problem becomes much easier.

The key observation

Any O on the border can never be captured, because one side is already open to the outside. And if a border O is safe, then every O connected to it is also safe.

So instead of trying to detect enclosed regions directly, the clean strategy is to do the opposite:

1. Start from every border O.
2. Mark every O reachable from the border as safe.
3. Flip every remaining O to X, because those are exactly the enclosed cells.
4. Restore the safe cells back to O.

This is the standard interview move: identify the cells that must survive, then flip everything else.

How to derive the optimal solution

A brute-force idea is to start a search from every O and ask whether that region touches the border. That works in principle, but it repeats a lot of work because the same cells get explored many times.

The better thought is to reverse the search direction. Instead of asking, for each region, “does it escape to the border?”, ask once from the border, “which cells can escape?”

That changes the problem from many overlapping searches to one global traversal. Every cell is processed at most a constant number of times, so the solution becomes linear in the size of the board.

Both DFS and BFS work. The underlying idea is identical: treat the board as a graph where each O cell connects to its up, down, left, and right neighbors.

Why the algorithm is correct

The algorithm relies on two facts:

First, every cell marked during the border traversal must remain O, because there is an explicit path of O cells from that cell to the border.

Second, every unmarked O must be captured. If it were not captured, then it would have a path to the border through adjacent O cells. But the border traversal would have found it through that path, which is a contradiction.

So after the marking pass:

• marked cells are exactly the safe cells
• unmarked O cells are exactly the enclosed cells

That is why the final sweep can safely flip only the unmarked O cells.

Best approach

The best general interview answer is a border-first flood fill.

It runs in O(rows * cols) time because each cell is visited at most once during marking and once during the cleanup sweep. The extra space is O(rows * cols) in the worst case if the search stack or queue grows large, although the board itself is modified in place so no separate visited matrix is needed.

In practice, this approach is both simpler and safer than a Union-Find solution for this problem. Union-Find is valid, but it adds more bookkeeping without improving the asymptotic complexity in a meaningful way for the standard interview version.

Python solution

The implementation below uses an iterative depth-first search from the border. It marks all border-connected O cells with a temporary sentinel, then performs one final pass to flip captured cells and restore safe ones.

from typing import List, Tuple


Coordinate = Tuple[int, int]


def is_border_cell(row: int, col: int, row_count: int, col_count: int) -> bool:
    return row == 0 or row == row_count - 1 or col == 0 or col == col_count - 1


def mark_border_connected_region(board: List[List[str]], start_row: int, start_col: int) -> None:
    """
    Mark every 'O' connected to the starting border cell as safe.
    A temporary marker avoids the need for a separate visited matrix.
    """
    row_count = len(board)
    col_count = len(board[0])
    stack: List[Coordinate] = [(start_row, start_col)]
    board[start_row][start_col] = "S"

    while stack:
        row, col = stack.pop()

        for next_row, next_col in (
            (row - 1, col),
            (row + 1, col),
            (row, col - 1),
            (row, col + 1),
        ):
            if not (0 <= next_row < row_count and 0 <= next_col < col_count):
                continue

            if board[next_row][next_col] != "O":
                continue

            board[next_row][next_col] = "S"
            stack.append((next_row, next_col))


def capture_surrounded_regions(board: List[List[str]]) -> None:
    """
    Modify the board in place by flipping surrounded 'O' regions to 'X'.
    """
    if not board or not board[0]:
        return

    row_count = len(board)
    col_count = len(board[0])

    # Mark all border-connected regions as safe.
    for row in range(row_count):
        for col in range(col_count):
            if not is_border_cell(row, col, row_count, col_count):
                continue

            if board[row][col] != "O":
                continue

            mark_border_connected_region(board, row, col)

    # Flip enclosed regions and restore the safe cells.
    for row in range(row_count):
        for col in range(col_count):
            if board[row][col] == "O":
                board[row][col] = "X"
            elif board[row][col] == "S":
                board[row][col] = "O"


class Solution:
    def solve(self, board: List[List[str]]) -> None:
        """LeetCode entry point."""
        capture_surrounded_regions(board)

Interview follow-ups

Could this be solved with BFS instead of DFS?

Yes. The traversal order does not matter here because the goal is only to mark every border-connected O. A queue-based BFS would start from the same border cells and visit the same connected components, just in a different order. It is correct for the same reason as DFS: every discovered cell has a path to the border, so it must stay O. The time complexity remains O(rows * cols), and the worst-case auxiliary space is still O(rows * cols). BFS can feel a bit more natural for some candidates, while iterative DFS often leads to slightly smaller code.

How would the solution change if diagonal neighbors also counted as connected?

The main idea stays exactly the same. The only change is the neighborhood definition: instead of four directions, the traversal would use eight directions. Border-connected cells would still be the safe cells, and every unmarked O would still be enclosed under the updated connectivity rule. The correctness argument is unchanged because it depends only on reachability from the border. The complexity remains O(rows * cols), but each step checks more neighbors, so the constant factor is a bit larger.

How would you solve this with Union-Find?

Create one node for each O cell and add one extra dummy node representing the border. Union every border O with the dummy node, and union adjacent O cells with each other. After building the structure, any O cell not connected to the dummy node must be enclosed and should be flipped. This works because connectivity to the dummy node is exactly the same as connectivity to the border. The time complexity is effectively linear, often written as O(rows * cols * alpha(rows * cols)), but it needs O(rows * cols) extra memory for the disjoint-set structure. It is a solid alternative, though usually not the simplest interview answer.

What if the interviewer wants to minimize extra memory beyond the board itself?

The in-place marking approach already avoids a separate visited matrix, which is the biggest easy win. However, a graph traversal still needs a stack or queue unless recursion is used, and recursion can hit Python’s depth limit on large boards. In an interview, the practical answer is to keep the in-place sentinel marking and use an iterative stack, since it is robust and easy to reason about. If the interviewer insists on strictly constant auxiliary memory, that becomes a much more specialized problem and usually moves beyond the intended scope of the standard LeetCode version.