Surrounded Regions

Given an R × C board of 'X' and 'O', capture all regions surrounded by 'X': flip every 'O' that is not connected (4-directionally) to a border 'O' into 'X'. Regions touching the boundary are safe. Return the modified board.

Hints

· Stuck? Reveal one nudge at a time.

An 'O' is captured only if it is NOT connected to a border 'O'.

Flood from the border to mark all safe 'O's with a temporary symbol.

Then flip unmarked 'O' to 'X' and restore the temporary symbol to 'O'.

Common doubts

A region is surrounded exactly when the border can't reach it, so one border flood identifies all safe cells at once.

It distinguishes 'safe O' from 'capturable O' so a single final sweep can flip and restore correctly.

Identical border-flood pattern — enclaves counts the survivors, surrounded regions rewrites the captured ones.

Interview follow-ups

· What an interviewer asks next.

Yes — union border 'O's with a virtual 'safe' node; any 'O' not connected to it is captured.

Then no O is inherently safe; every enclosed region would be captured differently.

Fun facts

LeetCode 130 — the classic 'work from the boundary inward' problem.
The virtual-node union-find variant is a neat DSU exercise.

Asked at

AmazonMicrosoftGoogle

Frequently Sometimes Occasionally

Example 1

Input: board = [[X,X,X,X],[X,O,O,X],[X,X,O,X],[X,O,X,X]]
Output: [[X,X,X,X],[X,X,X,X],[X,X,X,X],[X,O,X,X]]
The inner O-region is captured; the bottom O touches the border and survives.

Example 2

Input: board = [[O,O,O],[O,O,O],[O,O,O]]
Output: [[O,O,O],[O,O,O],[O,O,O]]
Every O touches the border, so nothing is captured.

Constraints

- 1 <= R, C <= 200 - board[i][j] is 'X' or 'O'

An 'O' region is captured unless it touches the border. So the safe cells are exactly those the boundary can reach through 'O's — the same border-flood pattern as number of enclaves. Mark every border-connected 'O' (with a temporary symbol), then in one pass: flip the remaining 'O's (the surrounded ones) to 'X', and restore the marked cells back to 'O'. O(R·C).

Flooding from the border, rather than trying to detect "surrounded" per region, sidesteps the tricky part — a region is surrounded precisely when the border can't reach it.

Prerequisites

Before you start

· Concepts used directly in the solution.

Border flood. only border-connected O survives.

Temporary marker. distinguish safe O from capturable O in one pass.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

Setup

“Which O's are safe?”

Those connected to a border O.

“In place?”

Yes — mark, then flip and restore.

The ideal opening — say it like this

I flood from every border O and mark it safe, then flip all unmarked O to X and restore the marks.

A region is captured exactly when the border can't reach it — O(R·C).

Understand the problem

Worked example — board = [["X","X","X"],["X","O","X"],["X","X","X"]]

no border O -> flood marks nothing
the central O is surrounded -> flipped to X
result = all X

Key observations

1Aha

Safe ⟺ border-connected

Only O's reachable from the boundary survive.

2Aha

Mark, then sweep

A temporary symbol separates safe O from captured O in one final pass.

3Aha

O(R·C)

One flood plus one sweep.

Brute force vs optimal

	Border DFS	Border BFS
Flood via	recursion	queue
Time	O(R·C)	O(R·C)
Risk	deep recursion	none

Both mark the same safe cells and capture the rest. Full code is in the Approaches selector below.

Summary

Key takeaway

Flood from every border 'O', marking safe cells; then flip unmarked 'O' to 'X' and restore the marks. O(R·C).

mark border-connected O as '#'
sweep: O -> X ; '#' -> O