An 'O' cell is safe from capture exactly when it has some path of 'O's reaching the border of the board. Checking that “reaches the border” condition per region is the interesting part; the flood fill itself is the same idea as Number of Islands, just applied to O cells instead of 1s. Since the board is naturally two-valued, this maps directly onto GridVisualizer with O -> 1 and X -> 0.
Flood Fill Each Region, Then Decide
Time O(m·n)Space O(m·n)Scan the whole board. Every time an unvisited 'O' is found, flood fill its entire connected region, collecting all of its cells and checking whether any of them sit on the border. If none do, the whole region gets captured (flipped to 'X'); otherwise it is left alone.
class Solution: def solve(self, board: list[list[str]]) -> None: rows, cols = len(board), len(board[0]) visited = set()
def flood(sr, sc): stack = [(sr, sc)] cells = [] touches_border = False local = {(sr, sc)} while stack: r, c = stack.pop() cells.append((r, c)) if r == 0 or r == rows - 1 or c == 0 or c == cols - 1: touches_border = True 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' and (nr, nc) not in local ): local.add((nr, nc)) stack.append((nr, nc)) return cells, touches_border
for r in range(rows): for c in range(cols): if board[r][c] == 'O' and (r, c) not in visited: cells, touches_border = flood(r, c) visited.update(cells) if not touches_border: for rr, cc in cells: board[rr][cc] = 'X'Why it’s correct: a region is captured exactly when none of its cells touch the border, which this checks directly per connected component. Complexity: every cell is visited by exactly one flood fill → O(m·n) time; storing each region’s cell list plus the global visited set is O(m·n) space.
Flood Fill Only From the Border
OptimalTime O(m·n)Space O(m·n)Flip the order of operations: instead of flood-filling every region and then asking “does it touch the border?”, start the flood fill from the border. Any 'O' reachable from a border 'O' is safe by definition — no separate check needed. Mark every cell reached this way (e.g. with a temporary '#'), then in one final pass flip every untouched 'O' to 'X' (captured) and every '#' back to 'O' (safe).
class Solution: def solve(self, board: list[list[str]]) -> None: if not board: return rows, cols = len(board), len(board[0])
def dfs(r, c): if r < 0 or r >= rows or c < 0 or c >= cols or board[r][c] != 'O': return board[r][c] = '#' # mark as safe for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)): dfs(r + dr, c + dc)
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] == '#': board[r][c] = 'O'Tracing on a richer 5x5 example (O=1, X=0 for the visualizer), border-only DFS started from every border cell in row/column order:
Border scan checks column 0 first and finds O at row 0. Mark it safe.
Why it’s correct: an 'O' cell can only be captured if it has no path of 'O's to the border. Flooding from the border directly marks the exact set of cells that fail that condition to be captured, with no need to check each region separately afterward. Complexity: the border flood fill visits each reachable cell once, and the final cleanup pass is a single scan → O(m·n) time, O(m·n) space for the recursion stack in the worst case — same complexity class as the region-wise approach, but simpler: one pass outward from a known-safe set, rather than tracking membership and border-touching per region.