AlgoViz
HomeGraphs

Surrounded Regions

Medium

Mark what touches the border, flip the rest

Problem

Capture all regions of 'O' fully surrounded by 'X' by flipping them to 'X' (border-connected O's stay).

In simple words

Mark O's connected to the border as safe, then flip every other O to X.

The idea

A region survives only if it touches an edge, so traverse inward from every border 'O' marking those regions as safe. Everything still marked 'O' afterwards was fully enclosed and can be flipped.

The trick

  • Search from the borders, not from the interior.
  • Use a temporary marker, then convert in a final sweep.
  • O(rows × cols).
1
1
0
0
1
0
0
1
0
0
1
1
0
0
0
1

Step 1 of 9. Scan for land. Each unvisited '1' starts a new island; flood-fill its whole blob so it isn't counted twice.

1/9
Optimal
timeO(rows·cols)spaceO(rows·cols)

Sink each island you find.

1for (r, c) if (grid[r][c] === '1') {2  islands++;3  sink(r, c); // DFS marks the blob as water4}5function sink(r, c) {6  if (out of bounds || grid[r][c] !== '1') return;7  grid[r][c] = '0';8  for (const [dr, dc] of DIRS) sink(r+dr, c+dc);9}

Input

grid
4 × 4

Memory

at
—
cells marked
0

Output

islands
—
answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

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']]
Explanation:
Inner O's get captured to X; border-connected O's survive.

Example 2

Input:
board = [[O,O],[O,O]]
Output:
[['O', 'O'], ['O', 'O']]
Explanation:
All touch the border → all stay O.

Example 3

Input:
board = [[X]]
Output:
[['X']]
Explanation:
Nothing to flip.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.