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.

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.

Complexity

O(rows \times cols) time — the flood touches each cell at most once, and the final scan is one more pass.

O(rows \times cols) worst-case space for the recursion, when the whole grid is one connected 'O' region. 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.