4.20.5 — Surrounded Regions

LeetCode 130 · Medium

The problem

In a grid of 'X' and 'O', flip every region of 'O' that is completely surrounded by 'X'. A region touching the border is not surrounded and survives.

X X X X          X X X X
X O O X    →     X X X X
X X O X          X X X X
X O X X          X O X X

The bottom-left O survives because it sits on the border.

The pattern

Checking each region for whether it touches the border needs a flood fill per region, and then a second pass to flip the losers. That works, but there is a cleaner way, and it is the same reversal as 4.20.4:

Do not look for the regions that are surrounded. Look for the ones that are not.

The ELI5 Analogy

Imagine a large grassy field surrounded by a tall wall, but the wall has some holes in it. Inside the field, there are patches of grass ('O') and patches of mud ('X'). An army wants to burn all the grass that is completely trapped inside the mud. Instead of sending scouts to every single patch of grass to see if they can somehow navigate to the outer wall, the army simply starts from the outside. They walk through the holes in the wall, stepping only on grass, and plant a flag ('S' for safe) on every grassy patch they can reach. Once they've explored as far as they can from the borders, they stop. Then, they look at the whole map: any grass that doesn't have a flag must be completely surrounded by mud, so they burn it ('X'). Any grass with a flag is safe, so they just take the flag back ('O').

What about a Brute Force Approach?

A brute-force strategy might iterate over every single cell. If it finds an 'O', it launches a DFS to check if that specific connected component touches the border. During the DFS, it would need to store all visited 'O' cells in a temporary list. If the DFS hits a border, it leaves them alone; if it finishes without hitting a border, it iterates through the temporary list and flips them to 'X'. This is messy, requires significant bookkeeping per region, and causes massive redundant traversals if not managed perfectly (leading to O(N^2) time). The reverse thinking completely eliminates the need to track individual components.

A region survives exactly when it touches the border. So flood from every border 'O', mark everything reached as safe, and then flip every remaining 'O' — because anything not reached from the border is, by definition, enclosed.

Three passes, no per-region bookkeeping, and no need to know which region a cell belongs to.

The three passes

1. Flood from the border, marking safe cells with a temporary character, say 'S'.
2. Scan the whole grid. Every remaining 'O' was unreachable from the border → flip it to 'X'.
3. Scan again, turning every 'S' back into 'O'.

The temporary marker is what lets one grid hold three states at once — enclosed, safe, and wall — without a second array.

The solution

Python

class Solution:
    def solve(self, board: List[List[str]]) -> None:
        if not board:
            return
        rows, cols = len(board), len(board[0])

        def mark_safe(r: int, c: int):
            if r < 0 or r >= rows or c < 0 or c >= cols:
                return
            if board[r][c] != 'O':
                return                       # wall, or already marked
            board[r][c] = 'S'
            mark_safe(r + 1, c)
            mark_safe(r - 1, c)
            mark_safe(r, c + 1)
            mark_safe(r, c - 1)

        # 1. flood from every border cell
        for r in range(rows):
            mark_safe(r, 0)
            mark_safe(r, cols - 1)
        for c in range(cols):
            mark_safe(0, c)
            mark_safe(rows - 1, c)

        # 2 and 3. flip the enclosed, restore the safe
        for r in range(rows):
            for c in range(cols):
                if board[r][c] == 'O':
                    board[r][c] = 'X'        # never reached → enclosed
                elif board[r][c] == 'S':
                    board[r][c] = 'O'        # restore

TypeScript

function solve(board: string[][]): void {
  if (!board.length) return;
  const rows = board.length, cols = board[0].length;

  function markSafe(r: number, c: number): void {
    if (r < 0 || r >= rows || c < 0 || c >= cols) return;
    if (board[r][c] !== 'O') return;
    board[r][c] = 'S';
    markSafe(r + 1, c); markSafe(r - 1, c);
    markSafe(r, c + 1); markSafe(r, c - 1);
  }

  for (let r = 0; r < rows; r++) { markSafe(r, 0); markSafe(r, cols - 1); }
  for (let c = 0; c < cols; c++) { markSafe(0, c); markSafe(rows - 1, c); }

  for (let r = 0; r < rows; r++)
    for (let c = 0; c < cols; c++) {
      if (board[r][c] === 'O') board[r][c] = 'X';
      else if (board[r][c] === 'S') board[r][c] = 'O';
    }
}

The flood only follows 'O'. An 'X' stops it, which is what makes a wall a wall.

Marking with 'S' doubles as the visited check. A cell already marked is no longer 'O', so the second condition rejects it and there is no infinite loop.

Passes 2 and 3 are folded into one loop, since flipping an 'O' and restoring an 'S' are independent — a cell is one or the other, never both.

Seeding the whole border, including corners twice, is harmless thanks to the visited check.

Code Walkthrough & Trace

Consider this 3x3 grid:

X X X
X O X
X O O

Step	Action	State of Grid
1	mark_safe loops over Top/Left/Right borders	All 'X', nothing changes.
2	mark_safe loops over Bottom border	Finds 'O' at (2,1) and (2,2).
3	DFS from (2,1). Marks it 'S'.	[[X, X, X], [X, O, X], [X, S, O]]
4	DFS recurses up to (1,1). Marks it 'S'.	[[X, X, X], [X, S, X], [X, S, O]]
5	DFS from (2,2). Marks it 'S'.	[[X, X, X], [X, S, X], [X, S, S]]
6	Pass 2 & 3. Loop over grid.
7	(1,1) is 'S' -> 'O'	[[X, X, X], [X, O, X], [X, S, S]]
8	(2,1) is 'S' -> 'O'	[[X, X, X], [X, O, X], [X, O, S]]
9	(2,2) is 'S' -> 'O'	[[X, X, X], [X, O, X], [X, O, O]]

(Note: In this specific example, no 'O' was trapped, so no 'X' flipping occurred. The edge 'O's saved the inner 'O').

Complexity

O(rows \times cols) time — the flood touches each cell at most once, and the final scan is one more pass. To break it down: The first loops scan only the perimeter. The DFS only ever traverses cells that are currently 'O', immediately mutating them to 'S'. So across the entire algorithm, a cell is transformed at most twice ('O' \to 'S' \to 'O', or 'O' \to 'X'). Finally, the nested loops do exactly one pass over the grid. Total operations are strictly proportional to N.

O(rows \times cols) worst-case space for the recursion, when the whole grid is one connected 'O' region. In this scenario, the recursion call stack would grow to rows \times cols frames deep before winding down. BFS or an explicit stack removes that risk on large grids.

Where this goes next

The "find the survivors, then everything else loses" inversion is a recurring move:

• Number of Closed Islands — same idea, counting instead of flipping.
• Number of Enclaves — count the land cells that cannot walk off the grid.
• Pacific Atlantic — search from the edges rather than from every cell. 4.20.4.
• Garbage collection — a real system doing exactly this. A tracing collector marks everything reachable from the roots, then frees the rest. It never asks "is this object garbage"; it asks "is this object reachable", and the answer to the first is whatever is left. Chapter 3.4 covers it.

The general shape: when "surrounded", "unreachable" or "unused" is hard to test directly, mark what is definitely safe and take the complement.

What the interviewer will push on

"Why search from the border instead of from each region?" It avoids tracking which region a cell belongs to and whether that region ever touched an edge. One flood answers the question for the whole grid.

"Why a temporary marker?" The grid must hold three states during the middle of the algorithm — wall, safe, and not-yet-decided — and one character each is enough.

"What if the grid is huge?" BFS or an explicit stack, because the recursion can be rows × cols deep.

"Could you use union-find?" Yes — union every 'O' with its 'O' neighbours, plus a virtual node representing "the border", and union every border 'O' with it. Then a cell survives if it shares a component with the virtual node. It is more code and the same complexity. The virtual-node trick is worth knowing, because it converts "is this connected to anything in a set" into one union-find query.

One thing to volunteer: mention garbage collection. It shows the inversion is a real technique rather than a puzzle-specific trick.

Next: 4.20.6 Rotting Oranges — the first BFS in this chapter where the answer is a number of steps.