Surrounded Regions medium
Description
Given an m x n matrix board containing 'X' and 'O', capture all regions that are 4-directionally surrounded by 'X' by flipping all 'O's in those regions to 'X'.
A region is surrounded if it is entirely enclosed by 'X' and does not touch the border of the board.
Modify the board in place.
Examples
> Case 1:
Input: Output:
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
> Case 2:
Input: [["X"]]
Output: [["X"]]The bottom-left O in case 1 stays because it’s on the border. The interior Os flip because they’re trapped by Xs.
Constraints
1 <= m, n <= 200board[i][j]is'X'or'O'.
The reverse-flood insight
You could try to detect each surrounded region: pick an O, DFS through connected Os, check if any touches the border, and flip if not. That’s two passes per region — and gets messy when regions branch.
The cleaner trick: flip the question. Instead of asking “which Os are surrounded,” ask “which Os are safe (not surrounded)?” — exactly the ones reachable from the border.
1. Mark every O that touches the border as SAFE (DFS / BFS from border).
2. Walk every cell:
- SAFE O → revert to O.
- Any other O → flip to X. (surrounded)
3. Done.This is the same anchor-from-the-boundary trick as Pacific Atlantic Water Flow — start from where the property is obviously true and propagate inward.
Code
We use a temporary marker '#' to flag safe Os during the first pass.
The temporary marker '#' is essential. Without it, the second sweep can’t distinguish “border-reachable O” from “surrounded O” — they both look like 'O'. The marker is a tiny piece of state encoded in the cell itself, saving an O(m·n) visited matrix.
Trace on the example
Initial: After DFS from border Os: Final:
X X X X X X X X X X X X
X O O X X O O X ← these were X X X X
X X O X X X O X surrounded X X X X
X O X X X # X X ← border O X O X X
markedThe border-reachable O at (3, 1) got marked '#', while the three interior Os stayed 'O'. The final sweep flipped the interior to 'X' and reverted '#' to 'O'.
BFS version
Replace the recursive DFS with iterative BFS using a queue — same logic, no stack overflow risk on huge grids:
from collections import deque
def solve_bfs(board):
if not board or not board[0]: return
rows, cols = len(board), len(board[0])
queue = deque()
# Seed: every border 'O'
for r in range(rows):
for c in [0, cols - 1]:
if board[r][c] == 'O':
board[r][c] = '#'
queue.append((r, c))
for c in range(cols):
for r in [0, rows - 1]:
if board[r][c] == 'O':
board[r][c] = '#'
queue.append((r, c))
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] = '#'
queue.append((nr, nc))
for r in range(rows):
for c in range(cols):
if board[r][c] == 'O': board[r][c] = 'X'
elif board[r][c] == '#': board[r][c] = 'O'The family of “anchor from the boundary” problems
| Problem | Anchor | What you compute |
|---|---|---|
| Surrounded Regions | Border Os | Which interior Os are trapped |
| Pacific Atlantic Water Flow | Both ocean edges | Cells reachable from both |
| Number of Closed Islands | Border land cells | Land not connected to the boundary |
| Number of Enclaves | Border land cells | Count of cells unreachable from the boundary |
| Walls and Gates | All gates | Distance to nearest gate |
Boundary anchoring is a top-3 pattern for grid problems — train your eye to spot “the answer involves what does not touch the edge.”
Analysis
- Time: O(m · n) — every cell visited at most twice (border DFS + final sweep).
- Space: O(m · n) in the worst case for the recursion stack (or BFS queue).