Surrounded Regions: Border DFS Trick

You are given an m x n board of 'X' and 'O' characters. Capture all regions of 'O' that are completely surrounded by 'X'. A region is surrounded if none of its cells sit on the border of the board. Captured cells get flipped to 'X'.

This is LeetCode 130: Surrounded Regions, and it teaches one of the most useful tricks in grid problems: instead of figuring out which cells to flip, figure out which cells to protect. It is the same "think from the edges" strategy you see in Pacific Atlantic Water Flow, applied in a simpler setting.

Why the naive approach is backwards

The obvious idea is to scan for 'O' cells, run DFS to find each connected region, and then check if any cell in that region touches the border. If none do, flip the whole region.

That works, but it is clunky. You need to collect every cell in a region, check the border condition, and then conditionally flip. There is a cleaner way.

The key insight: protect, then flip everything else

Flip the question. Instead of asking "which O's are surrounded?", ask "which O's are safe?"

An 'O' is safe if it is connected to the border. So start from the border and DFS inward. Every 'O' you reach is safe. After that, any 'O' you did not reach is surrounded, and you flip it.

The algorithm has three steps:

1. Walk the border of the board. For every 'O' on the border, run DFS to mark it and all connected 'O' cells as safe (temporarily change them to 'S').
2. Scan the entire board. Any remaining 'O' is surrounded, so flip it to 'X'.
3. Scan again. Any 'S' was safe, so restore it back to 'O'.

That is the entire solution. No region-tracking, no border-checking after the fact. Just one pass from the edges, then two cleanup scans.

Visual walkthrough

Let's trace through a 5x5 grid step by step. Watch how DFS from the border O protects its entire connected group, while the isolated O gets flipped.

The border DFS finds (0,2) and spreads to all four of its neighbors. The lonely 'O' at (3,1) is never reached. In the final pass, it gets flipped to 'X'. Every other 'O' survives because it was connected to the border.

The solution

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

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

    def dfs(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return
        if board[r][c] != "O":
            return

        board[r][c] = "S"  # mark safe

        dfs(r + 1, c)
        dfs(r - 1, c)
        dfs(r, c + 1)
        dfs(r, c - 1)

    # Step 1: DFS from every border O
    for r in range(rows):
        for c in range(cols):
            if (r == 0 or r == rows - 1 or c == 0 or c == cols - 1):
                if board[r][c] == "O":
                    dfs(r, c)

    # Step 2 + 3: flip surrounded O's, restore safe S's
    for r in range(rows):
        for c in range(cols):
            if board[r][c] == "O":
                board[r][c] = "X"  # surrounded
            elif board[r][c] == "S":
                board[r][c] = "O"  # restore safe

Let's break this down.

The DFS function is a standard flood fill. It checks bounds and whether the cell is 'O'. If so, it marks it 'S' (safe) and recurses into all four neighbors. Once marked 'S', the cell will not be visited again because it is no longer 'O'.

The border scan iterates over every cell but only calls DFS when the cell is on an edge (first/last row or first/last column) and contains 'O'. This seeds the flood fill from every border 'O'.

The cleanup loop makes a single pass over the board. Every 'O' that was not reached by the border DFS is surrounded, so it becomes 'X'. Every 'S' was reachable from the border, so it goes back to 'O'.

Why we DFS from borders instead of from interior cells

Imagine doing it the other way: scan every 'O', DFS to find its region, then check if any cell in that region is on the border. You would need to store the region, check the border condition, and either flip or skip. If the region is safe, you wasted work collecting cells you will not flip.

By starting from the border, you only do one DFS pass total across all border-connected regions. And you never need to "decide" whether to flip or not, because anything left unmarked after the border DFS is automatically surrounded. The approach is both simpler and faster in practice.

This is the same "reverse DFS from edges" idea from Pacific Atlantic Water Flow. In that problem, you DFS uphill from ocean borders to find cells that can reach both oceans. Here, you DFS from board borders to find 'O' cells that should be protected. Same trick, different application.

Complexity analysis

Time is O(m * n). The border scan visits O(2m + 2n) cells, and the DFS from those cells visits each cell at most once (because marking 'S' prevents revisits). The cleanup scan also visits every cell once. Total work is proportional to the size of the board.

Space is O(m * n) in the worst case for the recursion call stack. If the entire board is 'O' cells, the DFS could go m * n frames deep. In practice, the stack depth is proportional to the size of the largest border-connected region.

The BFS alternative

If recursion depth worries you, here is the BFS version. Same three-step structure, just using a queue instead of the call stack.

from collections import deque

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

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

    # Seed: find all border O's
    for r in range(rows):
        for c in range(cols):
            if (r == 0 or r == rows - 1 or c == 0 or c == cols - 1):
                if board[r][c] == "O":
                    queue.append((r, c))
                    board[r][c] = "S"

    # BFS from all border O's at once
    while queue:
        r, c = queue.popleft()
        for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] == "O":
                board[nr][nc] = "S"
                queue.append((nr, nc))

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

This BFS version seeds all border 'O' cells into the queue at once (multi-source BFS), then processes them level by level. The queue lives on the heap, so no recursion limit concerns. The maximum queue size is O(m * n) in the worst case.

Edge cases

Before submitting, check these:

• No O's on the board: nothing to flip. The DFS never fires, and the cleanup loop flips nothing.
• All O's on the border: every 'O' is border-connected. Nothing gets flipped.
• Single row or column: every cell is on the border. No 'O' can be surrounded.
• 1x1 board: [["O"]] stays "O". It is on the border.
• Entire board is O: one big region connected to the border. Nothing flipped.

The building blocks

This problem is built on three reusable pieces that CodeBricks drills independently:

1. Grid neighbor generation

The same four-direction pattern you use in every grid problem:

directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
for dr, dc in directions:
    nr, nc = r + dr, c + dc
    if 0 <= nr < rows and 0 <= nc < cols:
        # (nr, nc) is a valid neighbor

You saw this in Number of Islands, Pacific Atlantic Water Flow, and you will keep seeing it. The pattern never changes.

2. DFS flood fill with in-place marking

The same flood fill from Number of Islands, with the twist of using a temporary marker instead of sinking cells:

def dfs(r, c):
    if not in_bounds(r, c) or board[r][c] != target:
        return
    board[r][c] = marker
    for each neighbor:
        dfs(neighbor)

In Number of Islands, you mark "1" as "0". Here, you mark "O" as "S". Same skeleton, different characters. The key property is the same: marking before recursing prevents infinite loops.

3. Border seeding (multi-source DFS from edges)

Instead of DFS from a single cell, you seed from every cell on the border:

for r in range(rows):
    for c in range(cols):
        if on_border(r, c) and board[r][c] == "O":
            dfs(r, c)

This is identical to the seeding step in Pacific Atlantic Water Flow, where you DFS from every ocean border cell. The total work across all DFS calls is still O(m * n) because visited cells are never re-explored.

Common mistakes

1. Flipping all O's first, then trying to restore border ones. If you flip everything to 'X' and then try to figure out which ones were border-connected, you have lost the connectivity information. You need to mark safe cells before flipping.

2. Only checking edge cells, not DFS-ing from them. A cell deep in the interior can be safe if it connects to a border 'O' through a chain of 'O' cells. You must DFS from border 'O' cells to find the entire connected region, not just check the border cells themselves.

3. Forgetting to restore the temporary marker. If you mark safe cells as 'S' but forget the cleanup pass that turns them back to 'O', your output will contain 'S' characters. The cleanup loop handles both directions: flip 'O' to 'X' and restore 'S' to 'O'.

4. DFS from every O cell instead of just border O cells. If you start DFS from interior 'O' cells too, you will mark everything as safe and nothing gets flipped. The whole trick is that you only seed from the border.

When to use this pattern

Look for these signals:

• The problem involves a grid with "interior" vs "boundary" regions
• You need to find cells that are NOT reachable from the edges
• The problem mentions "surrounded," "enclosed," or "captured"
• Brute force requires checking every region against a boundary condition

Problems that use the same border DFS trick:

• Number of Islands (LeetCode 200): the foundational grid DFS pattern this problem builds on
• Pacific Atlantic Water Flow (LeetCode 417): multi-source DFS from two separate borders
• Walls and Gates (LeetCode 286): multi-source BFS from all gates to compute distances

From understanding to recall

You now see how border DFS turns "find surrounded regions" into a clean three-step process: protect border-connected cells, flip the rest, restore. The insight, thinking from the edges inward instead of from the interior outward, is the hard part. The code itself reuses grid neighbor generation, flood fill, and border seeding, the same building blocks from Number of Islands and Pacific Atlantic Water Flow.

But can you write the border seeding loop and the three-phase cleanup from scratch under pressure? The details trip people up: which cells to seed from, the temporary marker, the two-pass cleanup. They are not conceptually hard. They are recall challenges.

Spaced repetition closes that gap. You practice writing the border scan, the DFS function, and the cleanup loop from memory at increasing intervals. After a few rounds, the pattern is automatic. You see "surrounded regions" or "border DFS" in a problem, and the code flows out without hesitation.

Related posts

• Number of Islands - The foundational grid DFS problem that teaches flood fill, the core pattern reused here
• Pacific Atlantic Water Flow - The same "reverse DFS from edges" trick applied to a height-based reachability problem

CodeBricks breaks Surrounded Regions into its grid-neighbor-generation, DFS-flood-fill, and border-seeding building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a border DFS grid problem shows up in your interview, you do not think about it. You just write it.