TL;DR
Flood-fill from the border to mark safe 'O's (DFS or BFS), then flip everything still 'O' — O(m·n) time, O(m·n) space.
Approach 1 — Brute force: test every region
For each 'O', explore its whole region and check whether any cell touches the border; if not, flip the region. Without care this re-scans overlapping regions repeatedly.
def solve(board: list[list[str]]) -> None:
rows, cols = len(board), len(board[0])
def region(r: int, c: int) -> tuple[list, bool]:
stack, seen, safe = [(r, c)], {(r, c)}, False
cells = []
while stack:
cr, cc = stack.pop()
cells.append((cr, cc))
if cr in (0, rows - 1) or cc in (0, cols - 1):
safe = True
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = cr + dr, cc + dc
if 0 <= nr < rows and 0 <= nc < cols and \
board[nr][nc] == "O" and (nr, nc) not in seen:
seen.add((nr, nc))
stack.append((nr, nc))
return cells, safe
done = set()
for r in range(rows):
for c in range(cols):
if board[r][c] == "O" and (r, c) not in done:
cells, safe = region(r, c)
done.update(cells)
if not safe:
for cr, cc in cells:
board[cr][cc] = "X"
Complexity: with the done memo this is O(m·n), but the framing is easy to get wrong — forget the memo and it degrades toward O((m·n)²). The approaches below are cleaner and just as fast.
Approach 2 — Border DFS (flood fill from the edges)
Instead of asking “is this region enclosed?”, ask “is this region safe?” A region is safe iff it touches the border. Flood-fill inward from every border 'O', tagging reachable cells with a sentinel 'S'. Afterward, any remaining 'O' was never reached from an edge, so it is enclosed and gets flipped; the 'S' cells revert to 'O'.
Use DFS: recurse in all four directions from each border 'O'.
def solve(board: list[list[str]]) -> None:
rows, cols = len(board), len(board[0])
def dfs(r: int, c: int) -> None:
if r < 0 or r >= rows or c < 0 or c >= cols or board[r][c] != "O":
return
board[r][c] = "S"
dfs(r + 1, c)
dfs(r - 1, c)
dfs(r, c + 1)
dfs(r, c - 1)
for r in range(rows):
dfs(r, 0)
dfs(r, cols - 1)
for c in range(cols):
dfs(0, c)
dfs(rows - 1, c)
for r in range(rows):
for c in range(cols):
if board[r][c] == "O":
board[r][c] = "X"
elif board[r][c] == "S":
board[r][c] = "O"
Walkthrough (example 1): the only border 'O' is at (3, 1) on the bottom row. DFS from it tags just that one cell as 'S' (its neighbors are all 'X'). The three middle 'O's at (1,1), (1,2), (2,2) are never reached. Final sweep: those three → 'X' (captured), the 'S' at (3,1) → back to 'O'.
Complexity: each cell is visited a constant number of times, so O(m·n) time. Space is O(m·n) for the recursion stack in the worst case, a grid that is a single winding path of 'O's.
Approach 3 — Border BFS (preferred on huge grids)
Same strategy, but explore with an explicit queue instead of recursion. A 200×200 grid full of 'O's can drive DFS recursion ~40,000 frames deep and exceed Python’s default recursion limit. BFS iterates, so it has no such limit; prefer it when the grid can be large. DFS is fine when depth is bounded and the recursive code reads more cleanly.
from collections import deque
def solve(board: list[list[str]]) -> None:
rows, cols = len(board), len(board[0])
queue = deque()
for r in range(rows):
for c in (0, cols - 1):
if board[r][c] == "O":
queue.append((r, c))
for c in range(cols):
for r in (0, rows - 1):
if board[r][c] == "O":
queue.append((r, c))
while queue:
r, c = queue.popleft()
if not (0 <= r < rows and 0 <= c < cols) or board[r][c] != "O":
continue
board[r][c] = "S"
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
queue.append((r + dr, c + dc))
for r in range(rows):
for c in range(cols):
if board[r][c] == "O":
board[r][c] = "X"
elif board[r][c] == "S":
board[r][c] = "O"
Complexity: O(m·n) time, O(m·n) worst-case queue space — but no recursion depth risk.
Union-find alternative: create a virtual “safe” node, union every border 'O' to it, and union each 'O' with its 'O' neighbors. Afterward, any 'O' not in the same set as “safe” is captured. Union-find (disjoint-set union) tracks connected components with near-constant-time find/union via path compression and union by rank; it is useful when connectivity is queried incrementally, though for this one-shot scan a flood fill is simpler.
Common pitfalls
- Scanning corners twice. Corner cells belong to both a border row and a border column — harmless as long as you re-check the sentinel and skip already-marked cells.
- Forgetting to restore
'S'. The final pass must turn sentinels back into 'O'; leave them and you corrupt the board.
- Marking on enqueue vs. dequeue in BFS. If you don’t guard against duplicates, the same cell can enter the queue several times — check
board[r][c] != "O" when you pop.
- Recursion depth (DFS). On a maximal all-
'O' grid, DFS can exceed Python’s recursion limit; reach for BFS there.
Pattern takeaway
When “surrounded / enclosed / not reachable from the outside” is the condition, invert it: flood-fill from the boundary to mark what is reachable, and the complement is what is enclosed. BFS and DFS both do the flood fill — DFS for concise code when depth is bounded, BFS to avoid recursion limits on large grids — and union-find is the connectivity-based alternative when components must be merged incrementally.