130. Surrounded Regions

130

MediumGraph DFS and BFSDFS from the grid borderBorder-guarded flood fill

Surrounded Regions

Given an m x n board of 'X' and 'O', capture all regions that are 4-directionally surrounded by 'X' by flipping every 'O' in such a region to 'X'. An 'O' region is safe only if it touches the board's border.

Open official problem prompt ↗

In plain English

Flip only the O regions that are completely enclosed by X, leaving border-connected O regions untouched.

Picture it like this

Think of the border as the only exit from a flooded building; any water (O) that can trace a path to an exit stays, and any water trapped in an inner room gets sealed off (turned to X).

Example

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"]]
Why: The inner O region is fully surrounded and captured; the bottom-row O at (3,1) touches the border so it survives.

Constraints

m == board.lengthn == board[i].length1 <= m, n <= 200board[i][j] is 'X' or 'O'

Pattern lesson

See the pattern, then code

Border-guarded flood fill

↗

Graph DFS and BFS

Connected components, grids, reachability, or unweighted shortest paths.. It is easier to find the O's that are safe than the ones that are captured: any O connected to a border O escapes, so mark those first, then flip everything else.

New words, made simpleKnow these before the algorithm

Border cell: A cell in the first or last row or column.
Safe region: A group of O's connected to at least one border O.
Sentinel marker: A temporary symbol ('#') used to remember safe cells during the scan.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Flood fill from every interior O

Repeatedly re-testing regions for border contact is redundant work.

For each interior O region, test whether it reaches the border.

Time O((m*n)^2)Space O(m*n)

Best choiceFlood fill inward from the border

One pass from the border classifies every O correctly.

Mark all border-reachable O's safe first, then flip the rest and restore.

Time O(m*n)Space O(m*n)

The rule we keep true

Invariant

After the border DFS, a cell is '#' if and only if it is an O connected to the border, so all remaining O's are captured.

Why this is correct

Reasoning

A region is captured exactly when it has no border O, which is the negation of being reachable from the border; marking safe cells first turns the flip step into a simple relabeling.

The algorithm in three movesSay these aloud before coding

1From every 'O' on the four borders, DFS and temporarily mark connected O's as safe ('#')

border DFS marks safe O's as '#'

2Scan the whole board

interior O at (1,1),(1,2),(2,2) stay 'O'

3Flip any remaining 'O' (not border-connected) to 'X'

flip inner O->X, restore #->O

4Restore every '#' back to 'O'

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Readborder cells

2 · AskAny O on the edge?

3 · Update state(3,1) is O on bottom row

4 · ResultDFS marks (3,1) as '#'

Key takeaway

Border-touching O's are marked safe; interior O's with no border path get captured.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 6-14Safe-marking DFS
Spreads through connected O's, marking each with the sentinel '#'.
2
Lines 16-19Launch from the border
Only border O's seed the DFS, so exactly the escapable regions get marked.
3
Lines 21-26Flip then restore
Unmarked O's are captured to 'X'; sentinels are restored to 'O'.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

Board with all X and no O leaves it unchanged
A single row or column where every O touches the border
All O's connected to the border (nothing captured)
1x1 board

Common beginner mistakes

Starting DFS from interior cells instead of the border
Forgetting to restore the sentinel marker back to 'O'
Flipping in place before marking safe cells, which destroys the information needed
Off-by-one when identifying border rows and columns

Check your understanding

Why is it easier to mark safe (border-connected) O's than to directly find captured ones?

PyPython 3 · solution.py

Optimal

1class Solution:2    def solve(self, board: list[list[str]]) -> None:3        if not board or not board[0]:4            return5        rows, cols = len(board), len(board[0])67        def dfs(r: int, c: int) -> None:8            if r < 0 or r >= rows or c < 0 or c >= cols or board[r][c] != "O":9                return10            board[r][c] = "#"11            dfs(r + 1, c)12            dfs(r - 1, c)13            dfs(r, c + 1)14            dfs(r, c - 1)1516        for r in range(rows):17            for c in range(cols):18                if (r in (0, rows - 1) or c in (0, cols - 1)) and board[r][c] == "O":19                    dfs(r, c)2021        for r in range(rows):22            for c in range(cols):23                if board[r][c] == "O":24                    board[r][c] = "X"25                elif board[r][c] == "#":26                    board[r][c] = "O"

Time complexityO(m * n)Optimized

Space complexityO(m * n)Explained

Interview rehearsal

Explain before you code

25:00

Restate constraints and edge cases
Explain brute force and its bottleneck
State the invariant and complexity

Seen at

AmazonGoogleMicrosoft

Surrounded Regions

Surrounded Regions

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Graph DFS and BFS