Loading…

mediumGraphsLC #130Frequently asked

Surrounded Regions

Q: How do you solve Surrounded Regions using the Border BFS — Iterative Frontier approach?

When to use it: Offer when the board is large enough to risk recursion-stack overflow. Same O(m × n), explicit queue instead of the call stack. The logic is byte-for-byte the same as the DFS version — find what escapes to the border, capture the rest — but the traversal is iterative, which is what makes it safe at scale. **Why iterative matters here.** A recursive border fill on a 200×200 board that is almost entirely `'O'` can stack ~40,000 frames and overflow the call stack in stack-limited environments. BFS relocates that frontier into a heap-allocated queue, so the depth of exploration never touches the call stack. **Seed first, then expand.** We make one initial pass over the four borders, and for each `'O'` we find we mark it `'#'` and enqueue it. That primes the queue with every entry point to the outside. Then the main loop pops a cell, inspects its four orthogonal neighbours, and for each in-bounds `'O'` it marks `'#'` and enqueues — extending the safe region outward layer by layer. **Mark on enqueue, never on dequeue.** This is the one BFS detail that bites people. If you wait until a cell is dequeued to mark it, multiple neighbours can enqueue the same cell before it's processed, inflating the queue and re-doing work. Marking the instant you enqueue guarantees each cell is added exactly once. **Same final sweep.** Once the queue drains, the board again has `'X'` walls, `'#'` escapees, and trapped `'O'`s. The closing double-flip — `'O' → 'X'`, `'#' → 'O'` — finishes the job identically to the DFS approach. Time complexity: O(m × n). Space complexity: O(m × n) worst-case queue.

Q: How do you solve Surrounded Regions using the Union-Find with a Virtual Border Node approach?

When to use it: Mention as the connectivity-flavored alternative, especially if the interviewer steers toward Union-Find. Same asymptotic cost with near-constant α. Union-Find reframes 'reachable from the border' as 'in the same set as a single virtual node that stands for the outside'. **The virtual node trick.** Create one sentinel id (say `rows * cols`) that means 'connected to the border'. As we scan the grid, every `'O'` that lies on an edge gets unioned with this sentinel. That collapses the question 'can this cell escape?' into 'does this cell's set contain the sentinel?' — a single `find` comparison at the end. **Building the rest of the connectivity.** For each `'O'`, we union it with its `'O'` neighbour directly below and directly to the right. Checking only down and right (rather than all four directions) is enough because every orthogonal adjacency is covered exactly once as we sweep the grid in row-major order — the up/left edges are handled when the *other* endpoint is processed. This halves the union calls without missing any connection. **The final classification.** After the unions, we sweep once more. An `'O'` is captured precisely when `find(cell) != find(virtual)` — i.e. it never joined the outside's set. Those flip to `'X'`; everything else stays. Because we never used a temporary marker, there's no restore step. **Why path compression and the α bound.** The `find` here flattens the tree as it walks (pointing each node at its grandparent), so repeated queries get cheaper. Combined over `m × n` cells, the total work is `O(m × n × α(m × n))`, where α is the inverse Ackermann function — at most 4 for any board you could ever allocate, so effectively linear. The flood-fill solutions are simpler to write under interview pressure; reach for Union-Find when the conversation is explicitly about disjoint-set structures or dynamic connectivity. Time complexity: O(m × n × α(m × n)). Space complexity: O(m × n).

LCPractice

Graphs · 12 of 34 · 11 min

Given an m x n matrix board containing 'X' and 'O', capture all regions that are 4-directionally surrounded by `'X'`.

A region is captured by flipping all 'O's into 'X's in that surrounded region.

Notice that an 'O' should not be flipped if it is on the border, or if it is connected (4-directionally) to an 'O' that is on the border.

Modify board in place; you do not return anything.

In plain English

An 'O' is 'safe' if and only if it can reach the grid border through other 'O's. Every other 'O' is part of a region entirely walled in by 'X' and must be captured. We don't count regions — we flip the trapped ones to 'X' in place.

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"]]
Note: The 'O' cluster in the middle is fully surrounded by 'X' → captured. The 'O' at (3,1) sits on the bottom border, so it (and anything connected to it) is safe and stays 'O'.

Example 2

Input: board = [["X"]]
Output: [["X"]]
Note: No 'O's at all — nothing to capture.

Example 3

Input: board = [["O","O"],["O","O"]]
Output: [["O","O"],["O","O"]]
Note: Every 'O' touches the border, so none are surrounded — the board is unchanged.

Constraints

m == board.length
n == board[i].length
1 ≤ m, n ≤ 200
board[i][j] is 'X' or 'O'

Clarifying questions4First question: Are diagonal cells considered connected?Explore questions

Q1.Are diagonal cells considered connected?
No — only the 4 orthogonal neighbours (up/down/left/right). I'd confirm, since 8-directional would change which regions count as enclosed.
Q2.Can I modify the board in place, and what do I return?
The signature returns void and expects in-place mutation. I'll use a temporary marker on safe cells and clean it up before finishing.
Q3.How big can the board get?
Up to 200×200 = 40,000 cells. A recursive DFS could approach that depth on a board that's almost all 'O', so I'd consider iterative BFS to avoid a stack overflow.
Q4.Is a single-row or single-column board possible?
Yes. In a 1×n or m×1 board every cell is on the border, so nothing is ever captured — my border seeding handles that automatically.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Don't hunt for surrounded regions directly — find the ones that are NOT surrounded. Flood-fill from every 'O' on the border (DFS or BFS), marking those border-connected 'O's as safe (e.g. '#'). After the sweep, any 'O' still left is fully enclosed → flip it to 'X'; restore every '#' back to 'O'. One pass to mark, one pass to flip → O(m × n) time. Union-Find with a virtual 'border' node is the alternative.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you spot that detecting 'fully surrounded' directly is awkward, and invert it to 'reachable from the border'. Also whether you mark safe cells with a temporary state and restore them cleanly.

Where candidates slip

Trying to detect enclosure with a flood fill that 'returns false if it hits the edge' — correct but fiddly and easy to get wrong. Or forgetting to restore the '#' markers back to 'O'.

How to stand out

Lead with the inversion ('mark what escapes, flip what's left'), give both DFS and BFS (BFS avoids stack overflow on huge boards), and mention the Union-Find-with-a-virtual-border-node formulation.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Border DFS — Mark Escapees, Flip the Rest	`O(m × n)`	`O(m × n) worst-case recursion stack`	Lead with this. Phrase it as 'I won't look for surrounded regions; I'll look for the ones that escape to the border, then flip whatever is left'.	Read
2	Border BFS — Iterative Frontier	`O(m × n)`	`O(m × n) worst-case queue`	Offer when the board is large enough to risk recursion-stack overflow. Same O(m × n), explicit queue instead of the call stack.	Read
3	Union-Find with a Virtual Border NodeOptimal	`O(m × n × α(m × n))`	`O(m × n)`	Mention as the connectivity-flavored alternative, especially if the interviewer steers toward Union-Find. Same asymptotic cost with near-constant α.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewCapture regions surrounded by XThink directly or invert the problem?Direct enclosure testInvertExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 3

Border DFS — Mark Escapees, Flip the Rest

TimeO(m × n)SpaceO(m × n) worst-case recursion stack

Lead with this. Phrase it as 'I won't look for surrounded regions; I'll look for the ones that escape to the border, then flip whatever is left'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Detecting 'this region is fully surrounded' from the inside is awkward — you'd have to track whether the fill ever touched an edge. Can you flip the question to make it easy?

2Hint 2Explore hint

An 'O' is safe exactly when it can reach the border. So flood-fill starting from every 'O' on the four edges and mark everything reachable as 'safe'.

3Hint 3Explore hint

After marking, sweep the whole board: any 'O' left was never reached from the border → it's enclosed, flip it to 'X'. Then turn your 'safe' markers back into 'O'.

A · Core idea

The breakthrough is refusing to solve the literal question. Asking 'is this region surrounded?' forces you to explore a region and somehow remember whether it ever brushed the boundary — a flood fill that must thread a boolean back up through recursion. It works, but it's error-prone.

Invert it. A region is captured unless it can escape to the edge. The complement — 'can this 'O' reach the border?' — is trivial to compute: start from the border and flood inward. So we seed a DFS from every 'O' sitting in row 0, the last row, column 0, or the last column. Anything those fills reach is, by definition, connected to the outside and therefore safe. We stamp each safe cell with a temporary marker '#'.

Why the temporary marker matters. After the border fills finish, the board holds three kinds of cells: 'X' (walls), '#' (safe 'O's that escaped), and 'O' (the ones the fills never reached). That last group is exactly the enclosed regions. The final sweep makes two replacements: every surviving 'O' becomes 'X' (captured), and every '#' is restored to 'O' (it was always safe). Skipping the restore step leaves the board littered with '#' — a wrong answer that's easy to overlook in testing.

Why DFS is enough. We're not measuring distances or sizes; we only need to reach every escapee. DFS does that with a four-way recursion and a single base case: stop when out of bounds or when the cell isn't an 'O'. The marker '#' doubles as the visited flag, so cells are never re-entered and the recursion terminates.

Why I'd flag the recursion depth. On a 200×200 board that's almost all 'O', the fill can recurse ~40,000 frames deep and overflow the call stack in languages with modest limits. That's the cue to offer the iterative BFS version, which moves the frontier into a heap-allocated queue.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

board = [[X,X,X,X],[X,O,O,X],[X,X,O,X],[X,O,X,X]]

Interactive diagram

Why inverting the question is easier

scan borders

Active call / nodeSupporting contextReturned stateNot active

Border-reachable 'O's are safe; the captured region is everything the border fill never touches.

Final result[[X,X,X,X],[X,X,X,X],[X,X,X,X],[X,O,X,X]]

C · Code with teaching comments

Reference implementation previewpublic void solve(char[][] board) { if (board == null || board.length == 0 || board[0].length == 0) { return; } int rows = board.length, cols = board[0].length;Explore the full code

solution.javaJava

Border DFS — Mark Escapees, Flip the Rest — reference

5 teaching notes

1
public void solve(char[][] board) {
2
    if (board == null || board.length == 0 || board[0].length == 0) {
3
        return;
4
    }
5
    int rows = board.length, cols = board[0].length;
6
    // Seed DFS from every 'O' on the four borders.
7
    for (int r = 0; r < rows; r++) {
8
        dfs(board, r, 0);
9
        dfs(board, r, cols - 1);
10
    }
11
    for (int c = 0; c < cols; c++) {
12
        dfs(board, 0, c);
13
        dfs(board, rows - 1, c);
14
    }
15
    // Flip: leftover 'O' is enclosed; '#' was safe.
16
    for (int r = 0; r < rows; r++) {
17
        for (int c = 0; c < cols; c++) {
18
            if (board[r][c] == 'O') {
19
                board[r][c] = 'X';
20
            } else if (board[r][c] == '#') {
21
                board[r][c] = 'O';
22
            }
23
        }
24
    }
25
}
26
 
27
private void dfs(char[][] board, int r, int c) {
28
    if (r < 0 || r >= board.length || c < 0 || c >= board[0].length
29
            || board[r][c] != 'O') {
30
        return;
31
    }
32
    // Temporary marker that means 'reachable from the border'; also acts as the visited
33
    // flag.
34
    board[r][c] = '#'; // mark safe
35
    dfs(board, r + 1, c);
36
    dfs(board, r - 1, c);
37
    dfs(board, r, c + 1);
38
    dfs(board, r, c - 1);
39
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.39 lines

D · Why it works and complexityO(m × n) timeO(m × n) worst-case recursion stack spaceOpen the invariant and proofExplore the proof

The captured regions are the complement of the border-reachable region. Whenever a grid asks you to find cells that are 'trapped inside', the cheap move is almost always to flood-fill from the outside and keep what you didn't touch.

ComplexityO(m × n) time, O(m × n) worst-case recursion stack space — Each cell is visited a constant number of times: once by border seeding / a flood fill, and once by the final flip sweep → O(m × n). Recursion can descend to the size of one connected 'O' region, up to O(m × n) on an almost-all-'O' board.

E · Edge cases and pitfalls7board entirely 'O' — Every cell is border-connected → all marked '#', all restored to 'O'. Nothing captured.Explore edge cases

Edge cases handled

board entirely 'O'Every cell is border-connected → all marked '#', all restored to 'O'. Nothing captured.
single row [[O,X,O]]Both 'O's are on the border → safe; board unchanged.
no 'O' at allNo fills seed; the flip sweep changes nothing.

Pitfalls

Trying to detect enclosure directly with a fill that returns a boolean — works but error-prone; invert instead.
Forgetting the restore step, leaving '#' markers on the final board.
Only seeding from one or two edges instead of all four.
Deep recursion on a near-all-'O' 200×200 board can overflow the stack — prefer BFS there.

03.2

Approach 2 of 3

Border BFS — Iterative Frontier

TimeO(m × n)SpaceO(m × n) worst-case queue

Offer when the board is large enough to risk recursion-stack overflow. Same O(m × n), explicit queue instead of the call stack.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Same inversion as DFS — mark border-reachable 'O's safe — but expand the frontier with an explicit queue instead of recursion.

2Hint 2Explore hint

First enqueue (and mark) every 'O' on the four borders. Then repeatedly dequeue a cell and enqueue its unmarked 'O' neighbours.

3Hint 3Explore hint

Mark cells at ENQUEUE time, not dequeue time, so the same cell is never queued twice.

A · Core idea

The logic is byte-for-byte the same as the DFS version — find what escapes to the border, capture the rest — but the traversal is iterative, which is what makes it safe at scale.

Why iterative matters here. A recursive border fill on a 200×200 board that is almost entirely 'O' can stack ~40,000 frames and overflow the call stack in stack-limited environments. BFS relocates that frontier into a heap-allocated queue, so the depth of exploration never touches the call stack.

Seed first, then expand. We make one initial pass over the four borders, and for each 'O' we find we mark it '#' and enqueue it. That primes the queue with every entry point to the outside. Then the main loop pops a cell, inspects its four orthogonal neighbours, and for each in-bounds 'O' it marks '#' and enqueues — extending the safe region outward layer by layer.

Mark on enqueue, never on dequeue. This is the one BFS detail that bites people. If you wait until a cell is dequeued to mark it, multiple neighbours can enqueue the same cell before it's processed, inflating the queue and re-doing work. Marking the instant you enqueue guarantees each cell is added exactly once.

Same final sweep. Once the queue drains, the board again has 'X' walls, '#' escapees, and trapped 'O's. The closing double-flip — 'O' → 'X', '#' → 'O' — finishes the job identically to the DFS approach.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

board = [[X,X,X,X],[X,O,O,X],[X,X,O,X],[X,O,X,X]]

seed borders

only (3,1) is an 'O' on an edge → mark '#', enqueue

Statequeue=[(3,1)]

Final result[[X,X,X,X],[X,X,X,X],[X,X,X,X],[X,O,X,X]]

C · Code with teaching comments

solution.javaJava

Border BFS — Iterative Frontier — reference

4 teaching notes

1
public void solve(char[][] board) {
2
    if (board == null || board.length == 0 || board[0].length == 0) {
3
        return;
4
    }
5
    int rows = board.length, cols = board[0].length;
6
    Queue<int[]> q = new LinkedList<>();
7
    // Seed: enqueue + mark every border 'O'.
8
    for (int r = 0; r < rows; r++) {
9
        // Seed the left column; the helper marks and enqueues only if the cell is an
10
        // 'O'.
11
        enqueueIfO(board, r, 0, q);
12
        enqueueIfO(board, r, cols - 1, q);
13
    }
14
    for (int c = 0; c < cols; c++) {
15
        enqueueIfO(board, 0, c, q);
16
        enqueueIfO(board, rows - 1, c, q);
17
    }
18
    int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
19
    while (!q.isEmpty()) {
20
        int[] cell = q.poll();
21
        for (int[] d : dirs) {
22
            enqueueIfO(board, cell[0] + d[0], cell[1] + d[1], q);
23
        }
24
    }
25
    for (int r = 0; r < rows; r++) {
26
        for (int c = 0; c < cols; c++) {
27
            if (board[r][c] == 'O') {
28
                board[r][c] = 'X';
29
            } else if (board[r][c] == '#') {
30
                board[r][c] = 'O';
31
            }
32
        }
33
    }
34
}
35
 
36
private void enqueueIfO(char[][] board, int r, int c, Queue<int[]> q) {
37
    if (r < 0 || r >= board.length || c < 0 || c >= board[0].length
38
            || board[r][c] != 'O') {
39
        return;
40
    }
41
    // Mark AT ENQUEUE so a cell can never be added to the queue twice.
42
    board[r][c] = '#'; // mark on enqueue
43
    q.offer(new int[]{r, c});
44
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.44 lines

D · Why it works and complexityO(m × n) timeO(m × n) worst-case queue spaceOpen the invariant and proofExplore the proof

DFS and BFS are interchangeable for reachability — both just need to touch every border-connected 'O'. BFS is the safer default at scale because its memory lives in an explicit queue, not in recursion depth that can blow the stack.

ComplexityO(m × n) time, O(m × n) worst-case queue space — Each cell enters and leaves the queue at most once → O(m × n). The final flip sweep is another O(m × n). The queue can hold up to a large frontier, O(m × n) in the worst case.

E · Edge cases and pitfalls6near-all-'O' 200×200 board — BFS handles it with a queue and never risks a stack overflow; DFS might recurse ~40k deep.Explore edge cases

Edge cases handled

near-all-'O' 200×200 boardBFS handles it with a queue and never risks a stack overflow; DFS might recurse ~40k deep.
board entirely 'X'Nothing is enqueued; the flip sweep changes nothing.
single columnEvery cell is on the border → all 'O's safe; unchanged.

Pitfalls

Marking visited at dequeue time — the same cell gets enqueued by multiple neighbours, inflating the queue.
Using a list with pop(0) as the queue — O(n) per pop; use a deque/LinkedList.
Forgetting bounds checks before reading board[nr][nc].

03.3

Approach 3 of 3 · Optimal

Union-Find with a Virtual Border Node

TimeO(m × n × α(m × n))SpaceO(m × n)

Mention as the connectivity-flavored alternative, especially if the interviewer steers toward Union-Find. Same asymptotic cost with near-constant α.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Model each cell as a node. Add one extra 'virtual' node that represents 'the outside / the border'.

2Hint 2Explore hint

Union every border 'O' with the virtual node, and union each 'O' with its 'O' neighbours below and to the right.

3Hint 3Explore hint

After all unions, an 'O' is safe iff it shares a root with the virtual node. Every other 'O' is captured.

A · Core idea

Union-Find reframes 'reachable from the border' as 'in the same set as a single virtual node that stands for the outside'.

The virtual node trick. Create one sentinel id (say rows * cols) that means 'connected to the border'. As we scan the grid, every 'O' that lies on an edge gets unioned with this sentinel. That collapses the question 'can this cell escape?' into 'does this cell's set contain the sentinel?' — a single find comparison at the end.

Building the rest of the connectivity. For each 'O', we union it with its 'O' neighbour directly below and directly to the right. Checking only down and right (rather than all four directions) is enough because every orthogonal adjacency is covered exactly once as we sweep the grid in row-major order — the up/left edges are handled when the other endpoint is processed. This halves the union calls without missing any connection.

The final classification. After the unions, we sweep once more. An 'O' is captured precisely when find(cell) != find(virtual) — i.e. it never joined the outside's set. Those flip to 'X'; everything else stays. Because we never used a temporary marker, there's no restore step.

Why path compression and the α bound. The find here flattens the tree as it walks (pointing each node at its grandparent), so repeated queries get cheaper. Combined over m × n cells, the total work is O(m × n × α(m × n)), where α is the inverse Ackermann function — at most 4 for any board you could ever allocate, so effectively linear. The flood-fill solutions are simpler to write under interview pressure; reach for Union-Find when the conversation is explicitly about disjoint-set structures or dynamic connectivity.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

board = [[X,X,X,X],[X,O,O,X],[X,X,O,X],[X,O,X,X]]

Interactive diagram

Picking the right approach

scan (3,1)

Active call / nodeSupporting contextReturned stateNot active

Border flood fill (DFS/BFS) is the default; Union-Find for a connectivity-flavored framing.

Final result[[X,X,X,X],[X,X,X,X],[X,X,X,X],[X,O,X,X]]

C · Code with teaching comments

solution.javaJava

Union-Find with a Virtual Border Node — optimal

4 teaching notes

1
public void solve(char[][] board) {
2
    if (board == null || board.length == 0 || board[0].length == 0) {
3
        return;
4
    }
5
    int rows = board.length, cols = board[0].length;
6
    // One extra sentinel id meaning 'the outside / border'.
7
    int virtual = rows * cols;
8
    int[] parent = new int[rows * cols + 1];
9
    for (int i = 0; i <= virtual; i++) {
10
        parent[i] = i;
11
    }
12
    for (int r = 0; r < rows; r++) {
13
        for (int c = 0; c < cols; c++) {
14
            if (board[r][c] != 'O') {
15
                continue;
16
            }
17
            int id = r * cols + c;
18
            if (r == 0 || r == rows - 1 || c == 0 || c == cols - 1) {
19
                union(parent, id, virtual);
20
            }
21
            if (r + 1 < rows && board[r + 1][c] == 'O') {
22
                union(parent, id, (r + 1) * cols + c);
23
            }
24
            if (c + 1 < cols && board[r][c + 1] == 'O') {
25
                union(parent, id, r * cols + (c + 1));
26
            }
27
        }
28
    }
29
    for (int r = 0; r < rows; r++) {
30
        for (int c = 0; c < cols; c++) {
31
            if (board[r][c] == 'O'
32
                    && find(parent, r * cols + c) != find(parent, virtual)) {
33
                board[r][c] = 'X';
34
            }
35
        }
36
    }
37
}
38
 
39
private int find(int[] parent, int x) {
40
    while (parent[x] != x) {
41
        parent[x] = parent[parent[x]]; // path compression
42
        x = parent[x];
43
    }
44
    return x;
45
}
46
 
47
private void union(int[] parent, int a, int b) {
48
    parent[find(parent, a)] = find(parent, b);
49
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.49 lines

D · Why it works and complexityO(m × n × α(m × n)) timeO(m × n) spaceOpen the invariant and proofExplore the proof

A single virtual node that represents 'the boundary' turns a reachability question into a set-membership question. That sentinel pattern recurs whenever 'connected to a special place' is the property you care about.

ComplexityO(m × n × α(m × n)) time, O(m × n) space — Each cell does a constant number of unions/finds; with path compression and union the amortized cost per operation is α (inverse Ackermann), effectively constant → O(m × n × α).

E · Edge cases and pitfalls6board entirely 'O' — Every 'O' chains to a border 'O' and thus to the virtual node → nothing captured.Explore edge cases

Edge cases handled

board entirely 'O'Every 'O' chains to a border 'O' and thus to the virtual node → nothing captured.
single enclosed 'O'It never unions with the virtual node → captured.
no 'O'No unions happen; the classification sweep changes nothing.

Pitfalls

Unioning in all four directions instead of just down+right — correct but does double the work.
Forgetting to size the parent array to rows*cols + 1 for the virtual node — off-by-one crash.
Comparing parent[a] == parent[b] instead of find(a) == find(b) — roots can be stale without a find.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic void solve(char[][] board) { if (board == null || board.length == 0 || board[0].length == 0) { return; } int rows = board.length, cols = board[0].length;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

public void solve(char[][] board) {
    if (board == null || board.length == 0 || board[0].length == 0) {
        return;
    }
    int rows = board.length, cols = board[0].length;
    int virtual = rows * cols;
    int[] parent = new int[rows * cols + 1];
    for (int i = 0; i <= virtual; i++) {
        parent[i] = i;
    }
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (board[r][c] != 'O') {
                continue;
            }
            int id = r * cols + c;
            if (r == 0 || r == rows - 1 || c == 0 || c == cols - 1) {
                union(parent, id, virtual);
            }
            if (r + 1 < rows && board[r + 1][c] == 'O') {
                union(parent, id, (r + 1) * cols + c);
            }
            if (c + 1 < cols && board[r][c + 1] == 'O') {
                union(parent, id, r * cols + (c + 1));
            }
        }
    }
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (board[r][c] == 'O'
                    && find(parent, r * cols + c) != find(parent, virtual)) {
                board[r][c] = 'X';
            }
        }
    }
}

private int find(int[] parent, int x) {
    while (parent[x] != x) {
        parent[x] = parent[parent[x]]; // path compression
        x = parent[x];
    }
    return x;
}

private void union(int[] parent, int a, int b) {
    parent[find(parent, a)] = find(parent, b);
}

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Forgetting to restore the safe markers

After the border fill, safe cells carry the temporary '#'. The final sweep must turn '#' back into 'O'; otherwise the output board is littered with stray markers and fails the judge.

Explore the code comparison

Don't write this

for r in range(rows):
    for c in range(cols):
        if board[r][c] == 'O':
            board[r][c] = 'X'
        # missing: '#' -> 'O' restore

Write this instead

for r in range(rows):
    for c in range(cols):
        if board[r][c] == 'O':
            board[r][c] = 'X'
        elif board[r][c] == '#':
            board[r][c] = 'O'

Solving the problem directly instead of inverting

Detecting enclosure from the inside means a flood fill that must report whether it ever touched an edge and only flip if it didn't — extra state, easy to get wrong. Marking border-reachable cells safe is simpler and robust.

Explore the code comparison

Don't write this

// fragile: fill returns false if it reaches the border
boolean escaped = floodAndReport(board, r, c);
if (!escaped) flipRegionToX(...);  // must re-walk the region

Write this instead

// invert: mark everything the border can reach, flip the rest
for (int r = 0; r < rows; r++) { dfs(board, r, 0); dfs(board, r, cols - 1); }
for (int c = 0; c < cols; c++) { dfs(board, 0, c); dfs(board, rows - 1, c); }
// then: leftover 'O' -> 'X', '#' -> 'O'

Marking BFS cells on dequeue instead of enqueue

If you only mark a cell when you pop it, several neighbours can enqueue the same cell first, so it is processed multiple times and the queue balloons.

Explore the code comparison

Don't write this

while q:
    r, c = q.popleft()
    board[r][c] = '#'   # too late: already enqueued by others
    for dr, dc in dirs:
        nr, nc = r + dr, c + dc
        if in_bounds(nr, nc) and board[nr][nc] == 'O':
            q.append((nr, nc))

Write this instead

def enqueue_if_o(r, c):
    if in_bounds(r, c) and board[r][c] == 'O':
        board[r][c] = '#'   # mark AT enqueue
        q.append((r, c))

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Invert the problem: flood-fill the safe (border-connected) region, flip the rest

Code pattern to memorize

for each border cell that is 'O':
    flood_fill → mark connected 'O's as '#'   # safe, escapes
for each cell:
    if 'O':  -> 'X'   # was enclosed
    if '#':  -> 'O'   # restore safe

Rules to remember

1Solve the complement: an 'O' survives only if it can reach the border, so mark border-reachable 'O's first.
2Use a temporary marker ('#') for safe cells so the final pass can distinguish 'escaped' from 'enclosed'.
3Seed the flood fill from all four edges — top/bottom rows and left/right columns.
4Final pass does two flips: leftover 'O' → 'X' (captured) and '#' → 'O' (restore). Don't forget the restore.
5This mutates the board in place and returns void — read the signature before coding.

Use this pattern when

Capture / enclose problems where 'touching the border' means safe
Grid flood fill where the answer is the cells you CAN'T reach from an edge
Region-flipping on a matrix of two states
Any 'connected to the outside' vs 'trapped inside' classification

Choose another pattern when

You need the COUNT of regions, not a flip → plain connected-components (Number of Islands)
Edges/connections arrive incrementally → Union-Find is the natural fit
Movement has weights or you need shortest distance → BFS/Dijkstra, not a simple fill

Interview takeaway

Surrounded Regions teaches the single most useful grid trick after Number of Islands: when 'enclosed' is hard to test directly, flip the question and flood-fill from the border instead. The same border-seeding idea powers Pacific Atlantic Water Flow and Number of Closed Islands.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternInversion + border flood fill. When 'trapped inside' is hard to test, flood-fill from the outside and keep what you didn't reach. Same family as Number of Islands, Pacific Atlantic Water Flow, and Number of Closed Islands; Union-Find with a virtual node is the connectivity-flavored alternative.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Number of Islands
The foundational grid flood fill — count connected components of land instead of inverting from the border.
Pacific Atlantic Water Flow
Same border-seeding idea, run twice (from each ocean), then intersect the reachable sets.
Number of Closed Islands
Coming soon
Flood-fill border-touching land first to disqualify it, then count the remaining fully-enclosed islands.
Max Area of Island
Coming soon
Same flood fill, but return the size of each region and track the maximum.

Same pattern

←

Snakes and Ladders

Continue · Next problem

Bellman-Ford Shortest Path

mediumGraphsLC #130Frequently asked

Surrounded Regions

LCPractice

Graphs · 12 of 34 · 11 min

Given an m x n matrix board containing 'X' and 'O', capture all regions that are 4-directionally surrounded by `'X'`.

A region is captured by flipping all 'O's into 'X's in that surrounded region.

Notice that an 'O' should not be flipped if it is on the border, or if it is connected (4-directionally) to an 'O' that is on the border.

Modify board in place; you do not return anything.

In plain English

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"]]
Note: The 'O' cluster in the middle is fully surrounded by 'X' → captured. The 'O' at (3,1) sits on the bottom border, so it (and anything connected to it) is safe and stays 'O'.

Example 2

Input: board = [["X"]]
Output: [["X"]]
Note: No 'O's at all — nothing to capture.

Example 3

Input: board = [["O","O"],["O","O"]]
Output: [["O","O"],["O","O"]]
Note: Every 'O' touches the border, so none are surrounded — the board is unchanged.

Constraints

m == board.length
n == board[i].length
1 ≤ m, n ≤ 200
board[i][j] is 'X' or 'O'

Clarifying questions4First question: Are diagonal cells considered connected?Explore questions

Q1.Are diagonal cells considered connected?
No — only the 4 orthogonal neighbours (up/down/left/right). I'd confirm, since 8-directional would change which regions count as enclosed.
Q2.Can I modify the board in place, and what do I return?
The signature returns void and expects in-place mutation. I'll use a temporary marker on safe cells and clean it up before finishing.
Q3.How big can the board get?
Up to 200×200 = 40,000 cells. A recursive DFS could approach that depth on a board that's almost all 'O', so I'd consider iterative BFS to avoid a stack overflow.
Q4.Is a single-row or single-column board possible?
Yes. In a 1×n or m×1 board every cell is on the border, so nothing is ever captured — my border seeding handles that automatically.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you spot that detecting 'fully surrounded' directly is awkward, and invert it to 'reachable from the border'. Also whether you mark safe cells with a temporary state and restore them cleanly.

Where candidates slip

Trying to detect enclosure with a flood fill that 'returns false if it hits the edge' — correct but fiddly and easy to get wrong. Or forgetting to restore the '#' markers back to 'O'.

How to stand out

Lead with the inversion ('mark what escapes, flip what's left'), give both DFS and BFS (BFS avoids stack overflow on huge boards), and mention the Union-Find-with-a-virtual-border-node formulation.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Border DFS — Mark Escapees, Flip the Rest	`O(m × n)`	`O(m × n) worst-case recursion stack`	Lead with this. Phrase it as 'I won't look for surrounded regions; I'll look for the ones that escape to the border, then flip whatever is left'.	Read
2	Border BFS — Iterative Frontier	`O(m × n)`	`O(m × n) worst-case queue`	Offer when the board is large enough to risk recursion-stack overflow. Same O(m × n), explicit queue instead of the call stack.	Read
3	Union-Find with a Virtual Border NodeOptimal	`O(m × n × α(m × n))`	`O(m × n)`	Mention as the connectivity-flavored alternative, especially if the interviewer steers toward Union-Find. Same asymptotic cost with near-constant α.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 3

Border DFS — Mark Escapees, Flip the Rest

TimeO(m × n)SpaceO(m × n) worst-case recursion stack

Lead with this. Phrase it as 'I won't look for surrounded regions; I'll look for the ones that escape to the border, then flip whatever is left'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Detecting 'this region is fully surrounded' from the inside is awkward — you'd have to track whether the fill ever touched an edge. Can you flip the question to make it easy?

2Hint 2Explore hint

An 'O' is safe exactly when it can reach the border. So flood-fill starting from every 'O' on the four edges and mark everything reachable as 'safe'.

3Hint 3Explore hint

After marking, sweep the whole board: any 'O' left was never reached from the border → it's enclosed, flip it to 'X'. Then turn your 'safe' markers back into 'O'.

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

board = [[X,X,X,X],[X,O,O,X],[X,X,O,X],[X,O,X,X]]

Interactive diagram

Why inverting the question is easier

scan borders

Active call / nodeSupporting contextReturned stateNot active

Border-reachable 'O's are safe; the captured region is everything the border fill never touches.

Final result[[X,X,X,X],[X,X,X,X],[X,X,X,X],[X,O,X,X]]

C · Code with teaching comments

solution.javaJava

Border DFS — Mark Escapees, Flip the Rest — reference

5 teaching notes

1
public void solve(char[][] board) {
2
    if (board == null || board.length == 0 || board[0].length == 0) {
3
        return;
4
    }
5
    int rows = board.length, cols = board[0].length;
6
    // Seed DFS from every 'O' on the four borders.
7
    for (int r = 0; r < rows; r++) {
8
        dfs(board, r, 0);
9
        dfs(board, r, cols - 1);
10
    }
11
    for (int c = 0; c < cols; c++) {
12
        dfs(board, 0, c);
13
        dfs(board, rows - 1, c);
14
    }
15
    // Flip: leftover 'O' is enclosed; '#' was safe.
16
    for (int r = 0; r < rows; r++) {
17
        for (int c = 0; c < cols; c++) {
18
            if (board[r][c] == 'O') {
19
                board[r][c] = 'X';
20
            } else if (board[r][c] == '#') {
21
                board[r][c] = 'O';
22
            }
23
        }
24
    }
25
}
26
 
27
private void dfs(char[][] board, int r, int c) {
28
    if (r < 0 || r >= board.length || c < 0 || c >= board[0].length
29
            || board[r][c] != 'O') {
30
        return;
31
    }
32
    // Temporary marker that means 'reachable from the border'; also acts as the visited
33
    // flag.
34
    board[r][c] = '#'; // mark safe
35
    dfs(board, r + 1, c);
36
    dfs(board, r - 1, c);
37
    dfs(board, r, c + 1);
38
    dfs(board, r, c - 1);
39
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.39 lines

D · Why it works and complexityO(m × n) timeO(m × n) worst-case recursion stack spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls7board entirely 'O' — Every cell is border-connected → all marked '#', all restored to 'O'. Nothing captured.Explore edge cases

Edge cases handled

board entirely 'O'Every cell is border-connected → all marked '#', all restored to 'O'. Nothing captured.
single row [[O,X,O]]Both 'O's are on the border → safe; board unchanged.
no 'O' at allNo fills seed; the flip sweep changes nothing.

Pitfalls

Trying to detect enclosure directly with a fill that returns a boolean — works but error-prone; invert instead.
Forgetting the restore step, leaving '#' markers on the final board.
Only seeding from one or two edges instead of all four.
Deep recursion on a near-all-'O' 200×200 board can overflow the stack — prefer BFS there.

03.2

Approach 2 of 3

Border BFS — Iterative Frontier

TimeO(m × n)SpaceO(m × n) worst-case queue

Offer when the board is large enough to risk recursion-stack overflow. Same O(m × n), explicit queue instead of the call stack.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Same inversion as DFS — mark border-reachable 'O's safe — but expand the frontier with an explicit queue instead of recursion.

2Hint 2Explore hint

First enqueue (and mark) every 'O' on the four borders. Then repeatedly dequeue a cell and enqueue its unmarked 'O' neighbours.

3Hint 3Explore hint

Mark cells at ENQUEUE time, not dequeue time, so the same cell is never queued twice.

A · Core idea

The logic is byte-for-byte the same as the DFS version — find what escapes to the border, capture the rest — but the traversal is iterative, which is what makes it safe at scale.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

board = [[X,X,X,X],[X,O,O,X],[X,X,O,X],[X,O,X,X]]

seed borders

only (3,1) is an 'O' on an edge → mark '#', enqueue

Statequeue=[(3,1)]

Final result[[X,X,X,X],[X,X,X,X],[X,X,X,X],[X,O,X,X]]

C · Code with teaching comments

solution.javaJava

Border BFS — Iterative Frontier — reference

4 teaching notes

1
public void solve(char[][] board) {
2
    if (board == null || board.length == 0 || board[0].length == 0) {
3
        return;
4
    }
5
    int rows = board.length, cols = board[0].length;
6
    Queue<int[]> q = new LinkedList<>();
7
    // Seed: enqueue + mark every border 'O'.
8
    for (int r = 0; r < rows; r++) {
9
        // Seed the left column; the helper marks and enqueues only if the cell is an
10
        // 'O'.
11
        enqueueIfO(board, r, 0, q);
12
        enqueueIfO(board, r, cols - 1, q);
13
    }
14
    for (int c = 0; c < cols; c++) {
15
        enqueueIfO(board, 0, c, q);
16
        enqueueIfO(board, rows - 1, c, q);
17
    }
18
    int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
19
    while (!q.isEmpty()) {
20
        int[] cell = q.poll();
21
        for (int[] d : dirs) {
22
            enqueueIfO(board, cell[0] + d[0], cell[1] + d[1], q);
23
        }
24
    }
25
    for (int r = 0; r < rows; r++) {
26
        for (int c = 0; c < cols; c++) {
27
            if (board[r][c] == 'O') {
28
                board[r][c] = 'X';
29
            } else if (board[r][c] == '#') {
30
                board[r][c] = 'O';
31
            }
32
        }
33
    }
34
}
35
 
36
private void enqueueIfO(char[][] board, int r, int c, Queue<int[]> q) {
37
    if (r < 0 || r >= board.length || c < 0 || c >= board[0].length
38
            || board[r][c] != 'O') {
39
        return;
40
    }
41
    // Mark AT ENQUEUE so a cell can never be added to the queue twice.
42
    board[r][c] = '#'; // mark on enqueue
43
    q.offer(new int[]{r, c});
44
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.44 lines

D · Why it works and complexityO(m × n) timeO(m × n) worst-case queue spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls6near-all-'O' 200×200 board — BFS handles it with a queue and never risks a stack overflow; DFS might recurse ~40k deep.Explore edge cases

Edge cases handled

near-all-'O' 200×200 boardBFS handles it with a queue and never risks a stack overflow; DFS might recurse ~40k deep.
board entirely 'X'Nothing is enqueued; the flip sweep changes nothing.
single columnEvery cell is on the border → all 'O's safe; unchanged.

Pitfalls

Marking visited at dequeue time — the same cell gets enqueued by multiple neighbours, inflating the queue.
Using a list with pop(0) as the queue — O(n) per pop; use a deque/LinkedList.
Forgetting bounds checks before reading board[nr][nc].

03.3

Approach 3 of 3 · Optimal

Union-Find with a Virtual Border Node

TimeO(m × n × α(m × n))SpaceO(m × n)

Mention as the connectivity-flavored alternative, especially if the interviewer steers toward Union-Find. Same asymptotic cost with near-constant α.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Model each cell as a node. Add one extra 'virtual' node that represents 'the outside / the border'.

2Hint 2Explore hint

Union every border 'O' with the virtual node, and union each 'O' with its 'O' neighbours below and to the right.

3Hint 3Explore hint

After all unions, an 'O' is safe iff it shares a root with the virtual node. Every other 'O' is captured.

A · Core idea

Union-Find reframes 'reachable from the border' as 'in the same set as a single virtual node that stands for the outside'.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

board = [[X,X,X,X],[X,O,O,X],[X,X,O,X],[X,O,X,X]]

Interactive diagram

Picking the right approach

scan (3,1)

Active call / nodeSupporting contextReturned stateNot active

Border flood fill (DFS/BFS) is the default; Union-Find for a connectivity-flavored framing.

Final result[[X,X,X,X],[X,X,X,X],[X,X,X,X],[X,O,X,X]]

C · Code with teaching comments

solution.javaJava

Union-Find with a Virtual Border Node — optimal

4 teaching notes

1
public void solve(char[][] board) {
2
    if (board == null || board.length == 0 || board[0].length == 0) {
3
        return;
4
    }
5
    int rows = board.length, cols = board[0].length;
6
    // One extra sentinel id meaning 'the outside / border'.
7
    int virtual = rows * cols;
8
    int[] parent = new int[rows * cols + 1];
9
    for (int i = 0; i <= virtual; i++) {
10
        parent[i] = i;
11
    }
12
    for (int r = 0; r < rows; r++) {
13
        for (int c = 0; c < cols; c++) {
14
            if (board[r][c] != 'O') {
15
                continue;
16
            }
17
            int id = r * cols + c;
18
            if (r == 0 || r == rows - 1 || c == 0 || c == cols - 1) {
19
                union(parent, id, virtual);
20
            }
21
            if (r + 1 < rows && board[r + 1][c] == 'O') {
22
                union(parent, id, (r + 1) * cols + c);
23
            }
24
            if (c + 1 < cols && board[r][c + 1] == 'O') {
25
                union(parent, id, r * cols + (c + 1));
26
            }
27
        }
28
    }
29
    for (int r = 0; r < rows; r++) {
30
        for (int c = 0; c < cols; c++) {
31
            if (board[r][c] == 'O'
32
                    && find(parent, r * cols + c) != find(parent, virtual)) {
33
                board[r][c] = 'X';
34
            }
35
        }
36
    }
37
}
38
 
39
private int find(int[] parent, int x) {
40
    while (parent[x] != x) {
41
        parent[x] = parent[parent[x]]; // path compression
42
        x = parent[x];
43
    }
44
    return x;
45
}
46
 
47
private void union(int[] parent, int a, int b) {
48
    parent[find(parent, a)] = find(parent, b);
49
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.49 lines

D · Why it works and complexityO(m × n × α(m × n)) timeO(m × n) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls6board entirely 'O' — Every 'O' chains to a border 'O' and thus to the virtual node → nothing captured.Explore edge cases

Edge cases handled

board entirely 'O'Every 'O' chains to a border 'O' and thus to the virtual node → nothing captured.
single enclosed 'O'It never unions with the virtual node → captured.
no 'O'No unions happen; the classification sweep changes nothing.

Pitfalls

Unioning in all four directions instead of just down+right — correct but does double the work.
Forgetting to size the parent array to rows*cols + 1 for the virtual node — off-by-one crash.
Comparing parent[a] == parent[b] instead of find(a) == find(b) — roots can be stale without a find.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Try it — Java· run a complete program; method snippets need a driver

private int find(int[] parent, int x) {
    while (parent[x] != x) {
        parent[x] = parent[parent[x]]; // path compression
        x = parent[x];
    }
    return x;
}

private void union(int[] parent, int a, int b) {
    parent[find(parent, a)] = find(parent, b);
}

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Forgetting to restore the safe markers

After the border fill, safe cells carry the temporary '#'. The final sweep must turn '#' back into 'O'; otherwise the output board is littered with stray markers and fails the judge.

Explore the code comparison

Don't write this

for r in range(rows):
    for c in range(cols):
        if board[r][c] == 'O':
            board[r][c] = 'X'
        # missing: '#' -> 'O' restore

Write this instead

for r in range(rows):
    for c in range(cols):
        if board[r][c] == 'O':
            board[r][c] = 'X'
        elif board[r][c] == '#':
            board[r][c] = 'O'

Solving the problem directly instead of inverting

Explore the code comparison

Don't write this

// fragile: fill returns false if it reaches the border
boolean escaped = floodAndReport(board, r, c);
if (!escaped) flipRegionToX(...);  // must re-walk the region

Write this instead

// invert: mark everything the border can reach, flip the rest
for (int r = 0; r < rows; r++) { dfs(board, r, 0); dfs(board, r, cols - 1); }
for (int c = 0; c < cols; c++) { dfs(board, 0, c); dfs(board, rows - 1, c); }
// then: leftover 'O' -> 'X', '#' -> 'O'

Marking BFS cells on dequeue instead of enqueue

If you only mark a cell when you pop it, several neighbours can enqueue the same cell first, so it is processed multiple times and the queue balloons.

Explore the code comparison

Don't write this

while q:
    r, c = q.popleft()
    board[r][c] = '#'   # too late: already enqueued by others
    for dr, dc in dirs:
        nr, nc = r + dr, c + dc
        if in_bounds(nr, nc) and board[nr][nc] == 'O':
            q.append((nr, nc))

Write this instead

def enqueue_if_o(r, c):
    if in_bounds(r, c) and board[r][c] == 'O':
        board[r][c] = '#'   # mark AT enqueue
        q.append((r, c))

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Invert the problem: flood-fill the safe (border-connected) region, flip the rest

Code pattern to memorize

for each border cell that is 'O':
    flood_fill → mark connected 'O's as '#'   # safe, escapes
for each cell:
    if 'O':  -> 'X'   # was enclosed
    if '#':  -> 'O'   # restore safe

Rules to remember

1Solve the complement: an 'O' survives only if it can reach the border, so mark border-reachable 'O's first.
2Use a temporary marker ('#') for safe cells so the final pass can distinguish 'escaped' from 'enclosed'.
3Seed the flood fill from all four edges — top/bottom rows and left/right columns.
4Final pass does two flips: leftover 'O' → 'X' (captured) and '#' → 'O' (restore). Don't forget the restore.
5This mutates the board in place and returns void — read the signature before coding.

Use this pattern when

Capture / enclose problems where 'touching the border' means safe
Grid flood fill where the answer is the cells you CAN'T reach from an edge
Region-flipping on a matrix of two states
Any 'connected to the outside' vs 'trapped inside' classification

Choose another pattern when

You need the COUNT of regions, not a flip → plain connected-components (Number of Islands)
Edges/connections arrive incrementally → Union-Find is the natural fit
Movement has weights or you need shortest distance → BFS/Dijkstra, not a simple fill

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Number of Islands
The foundational grid flood fill — count connected components of land instead of inverting from the border.
Pacific Atlantic Water Flow
Same border-seeding idea, run twice (from each ocean), then intersect the reachable sets.
Number of Closed Islands
Coming soon
Flood-fill border-touching land first to disqualify it, then count the remaining fully-enclosed islands.
Max Area of Island
Coming soon
Same flood fill, but return the size of each region and track the maximum.

Same pattern

←

Snakes and Ladders

Continue · Next problem

Bellman-Ford Shortest Path