The problem
On a board of X and O, capture every region of O that is completely surrounded by X (turn those O into X). An O region touching the border is never captured.
Input: XXXX / XOOX / XXOX / XOXX Output: XXXX / XXXX / XXXX / XOXX
Picture it
Picture a game of Go: white stones (O) fully surrounded by black (X) are captured. A white group is safe only if it touches the edge of the board. So we start from every white stone on the edge and mark its whole group as safe. Every white stone not marked safe gets captured.
How to recognise it
- A grid of two kinds of cells, and the question is about groups of O cells joined side to side.
- A group is judged by one property: does it touch the border? Border-connected groups are special, all others are not.
- The change must be made in place, so you need a way to remember which cells are safe while you rewrite the rest.
- A grid up to 200 × 200 means 40,000 cells, so one pass per region is fine but one pass per cell is not.
Start with brute force
Take each O cell, find its whole region with a fresh visited set, and check whether any cell of that region lies on the border. If none does, the region is surrounded, so mark its cells for capture.
def solve_brute(board):
R, C = len(board), len(board[0])
out = [row[:] for row in board]
for r in range(R):
for c in range(C):
if board[r][c] == "O":
seen, st = {(r, c)}, [(r, c)]
touches = False
while st:
a, b = st.pop()
if a in (0, R - 1) or b in (0, C - 1):
touches = True
for x, y in nbrs(board, a, b):
if board[x][y] == "O" and (x, y) not in seen:
seen.add((x, y)); st.append((x, y))
if not touches:
out[r][c] = "X"
return out
A region of k cells is searched k times, so a board full of O costs R·C searches of R·C cells: O((R·C)²) time, about 1.6 × 10^9 steps for 200 × 200. Space is O(R·C) for the copy and visited set.
From brute force to the idea
- Find the waste. The brute force asks the same question about every cell of a region and gets the same answer each time.
- Flip the question. Deciding who is surrounded is awkward. Deciding who is safe is easy: a cell is safe exactly when a chain of O cells links it to the border.
- Start from the border. The shown code puts every border cell in the queue. When it pops a cell that is an
"O", it relabels it"S"(safe) and queues its neighbours. Border cells that are"X"are popped and ignored. - Sweep once. After the queue is empty, every
"O"left was never reached, so it is surrounded: turn it into"X". Every"S"goes back to"O".
The key idea: mark the survivors from the border inward, and everything else is captured.
The key idea
Flood fill from border O cells to mark the survivors, then flip the rest. O(rows × cols).
Python solution
def solve(board):
R, C = len(board), len(board[0])
q = deque() # edge cells
for r, c in all_cells(board):
if r in (0, R-1) or c in (0, C-1):
q.append((r, c))
while q: # edge-linked: safe
r, c = q.popleft()
if board[r][c] == "O":
board[r][c] = "S"
q.extend(nbrs(board, r, c))
for r, c in all_cells(board):
if board[r][c] == "O":
board[r][c] = "X" # captured
if board[r][c] == "S":
board[r][c] = "O"
def all_cells(g):
return [(r, c) for r in range(len(g))
for c in range(len(g[0]))]
def nbrs(g, r, c): # in-grid neighbours
R, C = len(g), len(g[0])
for nr, nc in ((r+1, c), (r-1, c),
(r, c+1), (r, c-1)):
if 0 <= nr < R and 0 <= nc < C:
yield nr, ncLeetCode adds the imports for you. To run this on your own machine, put this at the top: from collections import deque
In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force | O((R·C)²): one region search per O cell | O(R·C): visited sets and an output copy |
| Border flood (shown code) | O(R·C): every cell is expanded once; the queue takes at most about four pushes per cell | O(R·C): the queue and the list from all_cells; the board is changed in place |
Edge cases
- A single cell (
[["O"]]or[["X"]]): unchanged, since every cell is on the border. - Boards with 1 or 2 rows or columns: nothing is captured, because every cell is on the border.
- An O in the middle of X (the 3 × 3 ring): becomes X.
- An O region touching the border by one cell: the whole region survives.
- Diagonal contact does not connect, so an O linked to the border only diagonally is captured.
- The function returns
Noneand changes the board itself. The same cell may sit in the queue several times; this is harmless because only an"O"is expanded.dequemust be imported.
Common mistakes
- Flooding from every interior O to see whether it escapes, which is the slow approach.
- Capturing directly while searching, which flips border-connected regions that are found later.
- Forgetting to restore the
"S"cells to"O". - Seeding only the four corners or only the top row instead of the entire border.
- Treating diagonals as connected.
Without changing the board, return how many O cells would be captured. Describe what changes, then write it if you like.
Compare with our answer
Keep the border-first idea, but record the safe cells in a set instead of rewriting the board, then count the O cells that are not in it.
def count_captured(board):
R, C = len(board), len(board[0])
safe, q = set(), deque()
for r, c in all_cells(board):
if (r in (0, R - 1) or c in (0, C - 1)) and board[r][c] == "O":
safe.add((r, c)); q.append((r, c))
while q:
r, c = q.popleft()
for nr, nc in nbrs(board, r, c):
if board[nr][nc] == "O" and (nr, nc) not in safe:
safe.add((nr, nc)); q.append((nr, nc))
return sum(1 for r, c in all_cells(board)
if board[r][c] == "O" and (r, c) not in safe)
Time O(R·C), space O(R·C).
A strong answer mentions: starting only from border O cells, a visited set instead of overwriting, and counting the O cells that were never reached.
1. A grid marks land (1) and water (0). You must count the land cells that cannot reach the grid's edge by walking over land. Which approach fits best?
This is the same border-first idea: the cells that do reach the edge are found in one multi-source pass. A search from every cell repeats work, and row counts ignore connectivity.
2. Why does the shown solution start its search from the border rather than from the surrounded regions?
A region is captured only when no chain of O cells reaches the border, so the safe set is the thing that is easy to compute directly. Border cells may be X, and nothing here overflows.
3. A learner deletes the if board[r][c] == "S": board[r][c] = "O" lines from the final loop. Which input now returns a wrong board?
Only the last input has an O that survives. Its "S" label is never turned back into "O", so the board comes out wrong. The other inputs contain no safe O, so no "S" appears.
Score 60% or more and the lesson is marked complete.