130. Surrounded RegionsMedium

130. Surrounded Regions

MediumGraphBFSDFS·GoogleAmazon

Given an m×n board of 'X' and 'O' characters, capture all regions of 'O' that are completely surrounded by 'X'. A surrounded region must not touch the board's border. Flip captured regions to 'X' in-place.

1 ≤ m, n ≤ 200
board[i][j] is 'X' or 'O'

Example

board[['X','X','X','X'],['X','O','O','X'],['X','X','O','X'],['X','O','X','X']]

OutputAll interior 'O' → 'X'; border-connected 'O' stays

Real-world analogy: Fenced territory capture

⚔️ Territory Capture: Imagine a board game where 'O' represents open land and 'X' represents fences. Any open territory completely enclosed by fences gets captured (converted to fenced). But territory touching the edge of the map can never be fully enclosed — it's "borderland" and stays open.

The key insight (reverse thinking): Instead of finding which 'O's are trapped, find which ones are safe (connected to the border). BFS from every border 'O' outward — all reachable 'O's are safe. Everything else gets flipped.

Algorithm — Border BFS

1. Find all border 'O' cells → mark 'S' (safe), enqueue.
2. BFS: spread 'S' to any connected 'O' neighbor.
3. Scan entire board:
   'S' → restore to 'O' (was safe)
   'O' → flip to 'X' (surrounded)
   'X' → stays 'X'

Visualizer — Border BFS

■ Blue = safe 'O' · ■ Yellow = unseen 'O' · ■ Gray = 'X' · ■ Red = being flipped

BORDER BFS—

Press ▶ or step forward to begin.

✓

—

SpacePlay/Pause ←→Step R Reset F Fullscreen

Executing Code

def solve(self, board):

    ROWS, COLS = len(board), len(board[0])

    dirs = [(1,0),(-1,0),(0,1),(0,-1)]

    q = deque()

    for r in range(ROWS):

        for c in range(COLS):

            if (r in (0,ROWS-1) or c in (0,COLS-1)) and board[r][c]=='O':

                board[r][c]='S'; q.append((r,c))

    while q:

        r,c = q.popleft()

        for dr,dc in dirs:

            nr,nc = r+dr, c+dc

            if 0<=nr<ROWS and 0<=nc<COLS and board[nr][nc]=='O':

                board[nr][nc]='S'; q.append((nr,nc))

    for r in range(ROWS):

        for c in range(COLS):

            board[r][c] = 'O' if board[r][c]=='S' else 'X'

Common pitfalls

Trying to find surrounded regions directly

Checking each 'O' region individually to see if it touches a border is O(m·n) per region, potentially O((m·n)²). The reverse approach — mark border-connected 'O's as safe in one BFS pass — is O(m·n).

Forgetting to restore 'S' back to 'O'

After BFS, both safe 'O's (marked 'S') and non-'O' cells need the final scan. If you only flip 'O' → 'X' without restoring 'S' → 'O', safe regions are erased.

What to do next

Discussion

…

Loading comments…

LeetMotion