Surrounded Regions
Surrounded Regions: in a board of X and O, capture every region of Os that is completely surrounded by Xs by flipping those Os to X. A region touching the border is never captured.
- m == board.length
- n == board[i].length
- 1 <= m, n <= 200
- board[i][j] is 'X' or 'O'.
Intuition
Surrounded regions flips every O region fully enclosed by X to X. A region touching the border is not enclosed and must survive.
Testing each region for enclosure directly means exploring it and checking whether any cell reaches the edge — workable, but it repeats effort and needs careful bookkeeping.
Inverting the question is much cleaner:
- Find the regions that are safe rather than the ones that are surrounded — flood-fill inward from every border O, and whatever is not reached is enclosed by definition.
Any O connected to the border escapes; everything else is surrounded. One traversal from each border O marks all the survivors.
The standard implementation marks safe cells with a temporary character such as #. Then a final sweep converts every remaining O to X and every # back to O.
That two-step conversion at the end is what makes the approach work, and reversing its order breaks it — converting # back first would leave those cells indistinguishable from the Os about to be flipped.
Seeding must cover all four borders completely, not just the corners. Missing an edge leaves an entire escape route unexplored and wrongly flips surviving regions.
Movement is four-directional. Diagonal connectivity does not count, so a diagonal touch to the border does not save a region.
Recursive DFS can overflow the stack on a large grid where the Os form one long connected region, so BFS or an explicit stack is safer.
Each cell is visited a constant number of times, giving O(m × n) time and space.
Invert the condition. Finding regions that don't touch the border is hard; finding the ones that do is a flood fill from the edges. Mark those as safe, then everything still unmarked is by definition surrounded. Solving the complement is often far easier than the stated problem.
Approach
Before reading on: price up what the brute force costs here, then ask what one visit per cell or vertex would have to mark so nothing is counted twice. Aim for O(m x n) time and O(m x n) space.
Invert the question
Find the safe regions rather than the surrounded ones. Anything connected to the border escapes; everything else is enclosed by definition.
Seed from all four borders
Flood-fill from every O on the complete first and last rows and columns. Missing an edge leaves an escape route unexplored.
Mark safe cells temporarily
Write a placeholder such as # over reached cells. This distinguishes survivors from the Os that will be flipped.
Move in four directions only
Diagonal connectivity does not count, so a region touching the border only diagonally is still surrounded.
Convert in the right order
Flip remaining O to X first, then # back to O. Reversing this makes survivors indistinguishable from the cells being flipped.
Prefer iteration on large grids
Recursive DFS can overflow the stack when the Os form one long region. BFS or an explicit stack avoids the risk.
Cost of the approach
Each cell is visited a constant number of times, giving O(m × n) time and O(m × n) space in the worst case.
Solution & live demo
Common pitfalls
Flood filling from interior cells and checking for escape
for each interior 'O': dfs and test if it reaches the border
seed the stack with border 'O' cells only
That re-explores the same region once per starting cell and needs bookkeeping to remember which regions already escaped. Starting from the border touches each safe cell exactly once.
Missing corner cells in the border scan
for c in range(C):
if board[0][c] == 'O': ...if (r in (0, R - 1) or c in (0, C - 1)) and board[r][c] == 'O':
Scanning only the top and bottom rows omits the left and right columns (and vice versa), leaving whole safe regions unmarked. The combined row-or-column test covers all four sides including corners.
Flipping cells during the flood instead of after
board[nr][nc] = 'O' # already 'O'
board[nr][nc] = '#' # ... final pass restores '#' -> 'O', 'O' -> 'X'
The flood needs a third symbol to distinguish "safe, already visited" from "unvisited". Without it there's no way to tell a protected region from an unexamined one, and the final rewrite can't be done.
Edge cases
Everything is marked safe and the board is unchanged.
Every cell is on the border, so nothing can ever be captured.
There are no seeds and no flips; the board is returned as-is.
The flood follows the corridor inward and marks the entire region safe — which is why flooding from the border is more robust than trying to judge enclosure locally.