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.
class Solution:
def solve(self, 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 actually O(m·n), but the framing is clumsy and easy to get wrong (forget the memo and it degrades toward O((m·n)²)). The reverse-thinking approaches below are cleaner and just as fast.
Approach 2 — Border DFS (flood fill from the edges)
The insight: instead of asking “is this region enclosed?”, ask “is this region safe?” A region is safe iff it touches the border. So flood-fill inward from every border 'O', tagging reachable cells with a sentinel 'S'. When done, any remaining 'O' was never reached from an edge → it is enclosed → flip it. The 'S' cells revert to 'O'.
DFS is the natural first cut: recurse in all four directions from each border 'O'.
class Solution:
def solve(self, 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 → O(m·n) time. Space is O(m·n) for the recursion stack in the worst case (a grid that is one giant snake of 'O's).
Approach 3 — Border BFS (preferred on huge grids)
The insight: identical strategy, but explore with an explicit queue instead of recursion. This matters here because a 200×200 grid full of 'O's can drive DFS recursion ~40,000 frames deep and blow Python’s default recursion limit. BFS iterates, so it has no such ceiling — 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
class Solution:
def solve(self, 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 (named for completeness): 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 shines 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’s reachable, and the complement is what’s enclosed. BFS and DFS both do the flood fill — DFS for concise code on bounded depth, BFS to dodge recursion limits on large grids — and union-find is the connectivity-based alternative when components must be merged incrementally.