MEDIUM

Surrounded Regions

Given an m × n board of 'X' and 'O', flip every 'O' region to 'X' if it's completely enclosed by 'X'. A region is not captured if any of its cells touch the border.

Example

Input board with an enclosed "O" region and one touching the border

Output the enclosed region flipped to "X"; the border-connected one left as "O"

Key Pointers

Checking every O region individually to see if it touches the border is expensive — instead, work backward: start from every border O and mark everything connected to it as "safe".
Any O left unmarked after that pass was never connected to the border, so it must be fully enclosed and gets flipped.
A temporary marker (e.g. '#') protects the safe cells from being flipped, then gets converted back to 'O' at the end.

Step-by-Step Analysis

Run DFS from every 'O' on the border, marking each connected 'O' reached with '#'.
Scan the whole board: flip every remaining 'O' (unmarked, so fully enclosed) to 'X'.
Flip every '#' back to 'O' to restore the safe regions.

Complexity

Time: O(rows · cols) — Space: O(rows · cols)

Code

def solve(board: list[list[str]]) -> None:
    if not board:
        return

    rows, cols = len(board), len(board[0])

    def dfs(r: int, c: int) -> None:
        if r < 0 or r >= rows or c < 0 or c >= cols or board[r][c] != "O":
            return
        board[r][c] = "#"
        for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            dfs(r + dr, c + dc)

    for r in range(rows):
        dfs(r, 0)
        dfs(r, cols - 1)
    for c in range(cols):
        dfs(0, c)
        dfs(rows - 1, c)

    for r in range(rows):
        for c in range(cols):
            if board[r][c] == "O":
                board[r][c] = "X"
            elif board[r][c] == "#":
                board[r][c] = "O"

Code Explanation

How the solution above works, piece by piece.

An O region survives only if it touches the border, so start from the border instead of from each region.
dfs from every border cell turns each connected O into # ("safe").
Then one final pass: remaining O were never reached from the border, so flip them to X; turn # back into O.
Using # in the board itself avoids a separate visited set.
O(rows × cols) time.

Visual Walkthrough

Running it on an example board:

Rather than testing each region, the code rescues the ones that touch the border: DFS from every border O marks its region safe. Whatever O is left unmarked must be enclosed, so it's flipped to X.

touches the bordercaptured

Video Explanation

NeetCode — Surrounded Regions, LeetCode 130