LeetCode #130 Medium

Surrounded Regions

In a board of X and O, capture every region of Os that is completely surrounded by Xs by flipping those Os to X. A region touching the border is never captured.

graphsdfsbfsmatrix

Open on LeetCode ↗

02

Intuition

💡

The direct approach — flood each O region and ask whether it is enclosed — forces you to carry an 'escaped to the border' flag out of the recursion and then revisit the region to flip it. Invert the question. A region survives exactly when it touches the border, so flood inward from the border and mark everything reachable as safe. Every O left unmarked is enclosed by definition, and can be flipped in a final sweep. No flags, and each cell is visited a constant number of times.

03

Approach

1

See why the direct version is awkward

Starting a DFS at an interior O, you must determine whether any cell in that region touches the edge. That means either threading a boolean back up through every recursive call, or collecting the region into a list and checking it afterwards. Both work, but both mix the traversal with the decision, and the flag version is easy to get subtly wrong when a region has several branches.

2

Flood inward from the border instead

Collect every O sitting on the outer ring — top row, bottom row, first column, last column. Each is unambiguously safe, and so is every O connected to it. Run a DFS or BFS from each of these seeds, marking cells safe as you go. This traversal never has to decide anything: reachability from the border is the answer.

3

Sweep once and flip what was never marked

After the flood, walk the whole board. Any O that was not marked safe could not reach the border, so it is enclosed — flip it to X. Marked cells stay O. In an in-place implementation the marking is often done by writing a temporary character such as #, then converting # back to O and every remaining O to X in the final sweep. Two passes, O(mn) total.

04

Solution & live demo

python

▶1class Solution:
▶2    def solve(self, board):
▶3        R, C = len(board), len(board[0])
▶4        stack = []
▶5        for r in range(R):
▶6            for c in range(C):
▶7                if (r in (0, R - 1) or c in (0, C - 1)) and board[r][c] == 'O':
▶8                    stack.append((r, c))
▶9                    board[r][c] = '#'
▶10        while stack:
▶11            r, c = stack.pop()
▶12            for dr, dc in ((1,0), (-1,0), (0,1), (0,-1)):
▶13                nr, nc = r + dr, c + dc
▶14                if 0 <= nr < R and 0 <= nc < C and board[nr][nc] == 'O':
▶15                    board[nr][nc] = '#'
▶16                    stack.append((nr, nc))
▶17        for r in range(R):
▶18            for c in range(C):
▶19                board[r][c] = 'O' if board[r][c] == '#' else 'X'

05

Edge cases

All Os touch the border

Everything is marked safe and the board is unchanged.

Single row or single column

Every cell is on the border, so nothing can ever be captured.

No Os at all

There are no seeds and no flips; the board is returned as-is.

A region touching the border through a long thin corridor

The flood follows the corridor inward and marks the entire region safe — which is why flooding from the border is more robust than trying to judge enclosure locally.

06

Complexity

Time

O(m x n)

Space

O(m x n)

The space is the explicit stack in the worst case (a single snaking region). Marking in place avoids a separate visited grid.