Graphs crash course ↗ · 96

130. Surrounded Regions

Any O region fully surrounded by Xs gets flipped. The trick: instead of asking "is this O surrounded?" — ask "is it reachable from a border?" Seed a DFS from every border O, mark what's safe, then flip everything else.

● MediumDFS / BFS Flood FillBoundary SeedingTypeScript

PROBLEM What we're solving

Given an m×n board of 'X' and 'O', flip every 'O' that is fully surrounded by 'X' in all four directions. An 'O' is safe if it touches — or connects to — a board edge.

Worked example — input:

X X X X
X O O X
X X O X
X O X X

The three Os in the interior (rows 1–2, cols 1–2) form one component with no path to any border → they get flipped. The lone O at row 3 col 1 also has no border connection → flipped too. Output:

X X X X
X X X X
X X X X
X X X X

KEY IDEA Invert the question — find safe O's, not surrounded ones

Insight → Directly checking "is this Osurrounded?" requires knowing the entire component, which is expensive to verify per-cell. Instead, invert: an O is safe (not flipped) if and only if it can reach the board border via 4-directional O steps. Run DFS/BFS from every border O, tagging reachable cells as safe — everything left unmarked is surrounded.

RECIPE Mark safe from edges, then flip

1 · Seed DFS from the border. For every cell on the four edges that holds 'O', launch a DFS. This reaches every O connected to the edge — they are all safe.
2 · Mark safe cells temporarily. Replace each reachable 'O' with a sentinel like 'S'so we don't revisit it and can distinguish it from the surrounded ones in step 3.
3 · Flip surrounded cells. Scan the whole board: any remaining 'O' was never reachedfrom the border — it's surrounded. Flip it to 'X'.
4 · Restore safe cells. Replace every sentinel 'S' back to 'O'.

Classic confusion → Cells on the border itself are never flipped — even a lone Ositting on the edge is safe by definition because it can't be "surrounded" when it already touches the boundary. Many learners forget to seed the DFS at the border cells themselves (not just their interior neighbors), leaving border Os incorrectly flipped.

COST Complexity & alternatives

Per-cell BFS (brute force)

O(m²·n²)

BFS each O to check border reachability individually.

Border-seeded DFS

O(m·n)

Each cell visited at most once. O(m·n) extra space for the call stack.

In-place modification (using the 'S' sentinel) means we need no separate visited array — the board itself tracks state. Space is O(m·n) in the worst case due to DFS recursion depth (a zigzag path of O's). An iterative BFS with an explicit queue has the same space bound but avoids stack overflow on large boards.

Pattern transfer →This "mark from the boundary, flip the rest" technique generalizes: Pacific Atlantic Water Flow runs two BFS from opposite edges and intersects the reachable sets; Number of Islands floods fills from each unvisited land cell; Walls and Gates (multi-source BFS) seeds from all gates at once.

RUN IT Mark safe O’s from edges, then flip the rest

board (rows separated by ;)

step 0 / 7

STARTScan the four edges. Seed DFS from every border O to mark safe cells.

1▶function solve(board: string[][]): void {
2▶  const rows = board.length;
3▶  const cols = board[0]?.length ?? 0;
4 
5  // DFS from a border cell, marking every reachable 'O' as safe ('S').
6▶  function dfs(r: number, c: number): void {
7    if (r < 0 || r >= rows || c < 0 || c >= cols) return;
8    if (board[r][c] !== 'O') return;
9    board[r][c] = 'S';           // mark safe
10    dfs(r - 1, c);
11    dfs(r + 1, c);
12    dfs(r, c - 1);
13    dfs(r, c + 1);
14  }
15 
16  // 1. Seed DFS from every 'O' on the four edges.
17  for (let r = 0; r < rows; r++) {
18    dfs(r, 0);
19    dfs(r, cols - 1);
20  }
21  for (let c = 0; c < cols; c++) {
22    dfs(0, c);
23    dfs(rows - 1, c);
24  }
25 
26  // 2. Flip: 'O' → 'X' (surrounded), 'S' → 'O' (restore safe).
27  for (let r = 0; r < rows; r++) {
28    for (let c = 0; c < cols; c++) {
29      if (board[r][c] === 'O') board[r][c] = 'X';
30      else if (board[r][c] === 'S') board[r][c] = 'O';
31    }
32  }
33}

State
phase: idle
safeCount: 0
flipped: 0
Legend
O active cell
S safe (border-connected)
X wall / flipped

current DFS cell / being flippedsafe (border-connected O, marked S)

slowfast

TYPESCRIPT The solution, annotated

surroundedRegions.ts
function solve(board: string[][]): void {
  const rows = board.length;
  const cols = board[0]?.length ?? 0;

  // DFS from a border cell, marking every reachable 'O' as safe ('S').
  function dfs(r: number, c: number): void {
    if (r < 0 || r >= rows || c < 0 || c >= cols) return;
    if (board[r][c] !== 'O') return;
    board[r][c] = 'S';           // mark safe
    dfs(r - 1, c);
    dfs(r + 1, c);
    dfs(r, c - 1);
    dfs(r, c + 1);
  }

  // 1. Seed DFS from every 'O' on the four edges.
  for (let r = 0; r < rows; r++) {
    dfs(r, 0);
    dfs(r, cols - 1);
  }
  for (let c = 0; c < cols; c++) {
    dfs(0, c);
    dfs(rows - 1, c);
  }

  // 2. Flip: 'O' → 'X' (surrounded), 'S' → 'O' (restore safe).
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (board[r][c] === 'O') board[r][c] = 'X';
      else if (board[r][c] === 'S') board[r][c] = 'O';
    }
  }
}

Reading it block by block

Lines 6–12 — the DFS helper. dfs(r, c) returns immediately if the cell is out of bounds or not an 'O'. Otherwise it marks the cell 'S' (safe sentinel) and recurses in all four directions. The early !== 'O' check also stops re-entry on already-marked 'S' cells and on 'X' borders.

Lines 15–21 — seed the four edges. We call dfs on every cell in the leftmost and rightmost columns, and in the top and bottom rows. Any 'O' that can reach the border gets tagged. Crucially this is O(m+n) seed calls, and each internal cell is visited at most once overall.

Lines 23–29 — the final two-pass sweep. One scan over every cell: if it's still 'O' it was unreachable from any border — flip it to 'X'. If it's 'S' (safe) restore it to 'O'. 'X' cells are left unchanged throughout.

Complexity → O(m·n) time — every cell is touched at most twice (once in the DFS phase, once in the sweep). O(m·n) space in the worst case from DFS recursion (a path winding through all cells). An iterative BFS replaces the implicit call stack with an explicit queue but keeps the same asymptotic bound.

INTERVIEWFollow-ups they'll ask

"Can you do it iteratively?" Yes — replace the recursive DFS with a stack or queue. This avoids call-stack overflow on large boards (e.g. a 200×200 board of all Os would blow the stack).
"What if the board is huge and memory matters?" Union-Find lets you union every border Ointo a virtual "border" node, then a single pass identifies which Os are connected. Same asymptotic complexity, often more cache-friendly.
"8-directional connectivity instead of 4?" Just extend the dirs array to include the four diagonals. The rest of the algorithm is unchanged.
"Return the list of flipped cells instead of mutating?" Collect coordinates of any cell that is O after the DFS phase (i.e., surrounded) before the flip step.
"What's the brute-force approach?" For each O, BFS to check whether it can reach the border. O(m·n) per cell → O(m²n²) total. The border-seeding trick fuses all those searches into a single O(m·n) sweep.

MNEMONIC The one-liner

"Safe O's touch the shore. Flood from every edge, mark survivors, drown the rest."

TRIGGERS When you see _ → reach for _

"flip surrounded region / captured cells"	DFS from border edges
two-category graph (safe vs captured)	sentinel + two-pass flip
"reachable from boundary" type check	boundary-seeded flood fill
connected components touching / not touching edge	mark then sweep

SKELETON The reusable shape

skeleton.ts
function solve(board: string[][]): void {
  const rows = board.length, cols = board[0]?.length ?? 0;

  function dfs(r: number, c: number): void {
    if (r < 0 || r >= rows || c < 0 || c >= cols) return;
    if (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);
  }

  // seed from all four edges
  for (let r = 0; r < rows; r++) { dfs(r,0); dfs(r,cols-1); }
  for (let c = 0; c < cols; c++) { dfs(0,c); dfs(rows-1,c); }

  // flip 'O'→'X', restore 'S'→'O'
  for (let r = 0; r < rows; r++)
    for (let c = 0; c < cols; c++) {
      if (board[r][c] === 'O') board[r][c] = 'X';
      else if (board[r][c] === 'S') board[r][c] = 'O';
    }
}

FLASHCARDS Tap to flip

When is an O cell safe (not flipped)?

When it can reach any board edge via a 4-connected path of 'O' cells — i.e., it is in the same component as the border.

tap to flip

1 / 7

Answer to reveal explanations. No penalty for retries.Score: 0 / 9

QUESTION 01

What is the time complexity of the border-seeded DFS approach on an m×n board?

QUESTION 02

On this board, how many Os get flipped?

X X X X
X O O X
X X O X
X O X X

QUESTION 03

Why does the algorithm mark reachable O cells with a sentinel "S" rather than just tracking them in a Set?

QUESTION 04

Which cells do we use as DFS starting points?

QUESTION 05

A board consists entirely of Os. After running solve, what is the board?

QUESTION 06

What happens to an O cell that sits exactly on the board edge?

QUESTION 07

Which alternative algorithm has the same correctness but avoids deep recursion on very large boards?

QUESTION 08

#130 · Surrounded RegionsAny 'O' connected to the border cannot be captured. DFS from every border 'O' to mark safe cells, then flip all remaining 'O's to 'X' in a single scan.Which algorithmic approach does this primarily use?

QUESTION 09

PROBLEM What we're solving

KEY IDEA Invert the question — find safe O&apos;s, not surrounded ones

RECIPE Mark safe from edges, then flip

COST Complexity & alternatives

RUN IT Mark safe O’s from edges, then flip the rest

TYPESCRIPT The solution, annotated

Reading it block by block

INTERVIEWFollow-ups they'll ask

MNEMONIC The one-liner

TRIGGERS When you see ___ → reach for ___

SKELETON The reusable shape

FLASHCARDS Tap to flip

KEY IDEA Invert the question — find safe O's, not surrounded ones

TRIGGERS When you see _ → reach for _