Difficulty: MediumGraphs

Surrounded Regions

Problem in Plain English

Flip every region of O cells that is fully enclosed by X cells into X, while leaving any O connected to the board edge untouched. The board is modified in place and nothing is returned.

Problem Statement

You are given an m x n matrix board holding 'X' and 'O'. Capture every region that is 4-directionally surrounded by 'X' by flipping all of its 'O' cells into 'X' cells.

Any 'O' cell connected to the border of the board, directly or through other 'O' cells, escapes capture. Modify the board in place and do not return anything.

Constraints

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

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"]]

The border (3,1) escapes capture and stays O, while the inland cells (1,1), (1,2) and (2,2) are surrounded and flip to X.

Example 2

Input: board = [["X"]]
Output: [["X"]]

The single cell is already X, so nothing changes.

Example 3

Input: board = [["O","X","X"],["X","O","X"],["X","X","X"]]
Output: [["O","X","X"],["X","X","X"],["X","X","X"]]

The corner O remains because it is on the border. The center O touches it only diagonally, so no allowed path connects them; all four side neighbours of the center are X and it is captured.

Example 4

Input: board = [["X","O","X"],["X","O","X"],["X","X","X"]]
Output: [["X","O","X"],["X","O","X"],["X","X","X"]]

The inland O at (1,1) reaches the top edge through (0,1), so both cells remain O. A cell need not itself lie on the border to escape.

Intuition

A region is a connected component of O cells joined by shared sides. It escapes capture exactly when some path in that component reaches a board edge; diagonal contact does not help. Example 1 has a three-cell inland component and the separate border cell (3,1). Testing each component for an escape works, but safe components may be traversed repeatedly. Reverse the question: start at border O cells, mark everything reachable as safe, and capture only what remains. Use an explicit stack so a 200 by 200 region does not exhaust the language call stack.

Approaches

Region Check Per Cell

Solution Details

Reveal Region Check Per Cell: intuition, complexity, and code

Intuition

For each remaining O encountered by the row scan, explore its component with a fresh visited set and explicit stack. Stop searching as soon as a border cell proves escape. Do not change any cell until escape has been ruled out; if the search finishes without touching a border, flip all visited cells. Captured components are erased once, but safe components are searched again from each of their cells, which creates the quadratic bottleneck.

Step-by-Step Logic

Scan the board in row-major order. For each remaining O seed, create a new seen set, push the seed, and set escapes to false. Example 1 first seeds (1,1); X positions are skipped.
Pop a cell from the explicit stack and test whether its row or column lies on a border. If it does, set escapes and stop this search. Keep the board unchanged while the outcome is uncertain.
Otherwise inspect four side neighbours in left, right, up, down order, marking each unseen O when pushed. Example 1 discovers (1,2) from (1,1), then (2,2). Last-in-first-out processing favours down when several neighbours are added.
If the stack empties with escapes false, flip every coordinate in seen. Example 1 changes (1,1), (1,2) and (2,2) to X together; their later scan positions are skipped.
If escapes is true, flip nothing and discard this search's marks. In Example 1 seed (3,1) immediately proves escape and stays O. Finish the scan in place; safe cells on larger boards may trigger repeated searches.

Why It Works

Before a search, all previously erased components were surrounded. Erasing one whole component cannot disconnect another O component because no side-adjacent O path joined them. During the search, seen contains only O cells reachable from the seed, and discovery marks prevent duplicate scheduling. A popped border cell proves the seed component escapes, so keeping every cell is correct even if the search stops early. If the stack empties without a border, path induction shows every cell of the component was visited and none touches an edge; flipping precisely seen captures that entire component. Thus the outer scan eventually captures each surrounded component and never changes an escaping component.

Dry Run

Region Check Per Cell: variable states at each step
Scan / pop	Stack, top at right	seen	escapes	Board change
Skip X positions before (1,1)	—	—	—	none
Seed (1,1)	[(1,1)]	{(1,1)}	false	none
Pop (1,1), discover right neighbour	[(1,2)]	{(1,1),(1,2)}	false	none
Pop (1,2), discover down neighbour	[(2,2)]	{(1,1),(1,2),(2,2)}	false	none
Pop (2,2), all neighbours X or seen	[]	{(1,1),(1,2),(2,2)}	false	none
Search exhausted; commit capture	[]	same three cells	false	all three O → X
Resume scan through (3,0)	—	new search not started	—	(1,2) and (2,2) now X; skip
Seed (3,1)	[(3,1)]	{(3,1)}	false	none
Pop (3,1), bottom border reached	[]	{(3,1)}	false → true	keep O; stop search
Skip final X cells	—	—	—	final rows XXXX;XXXX;XXXX;XOXX; return nothing

Complexity Analysis

Time Complexity

O((m * n)^2)

Space Complexity

O(m * n)

Let N = mn. Up to N remaining O cells start searches, each of which can visit O(N) cells, so worst-case time is O(N²), using expected constant-time hash-set operations. Early escape helps common boards but a long safe corridor can still be searched from many seeds. The seen set and explicit stack hold O(N) cells at peak; each discarded search can allocate another set, so cumulative allocation may be O(N²). Captured regions are flipped only after a full no-escape search. Both outer board and inner row objects are preserved. There is no input-dependent recursion stack.

Code

Solution.java

1import java.util.ArrayDeque;2import java.util.HashSet;3
4class Solution {5    public void solve(char[][] board) {6        int rows = board.length, cols = board[0].length;7        int[][] dirs = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};8        for (int r = 0; r < rows; r++) {9            for (int c = 0; c < cols; c++) {10                if (board[r][c] != 'O') continue;11                HashSet<Integer> seen = new HashSet<>();12                ArrayDeque<Integer> stack = new ArrayDeque<>();13                seen.add(r * cols + c);14                stack.addLast(r * cols + c);15                boolean escapes = false;16                while (!stack.isEmpty()) {17                    int cell = stack.removeLast();18                    int cr = cell / cols, cc = cell % cols;19                    // One border witness is enough; no board writes have occurred yet.20                    if (cr == 0 || cr == rows - 1 || cc == 0 || cc == cols - 1) {21                        escapes = true;22                        break;23                    }24                    for (int[] d : dirs) {25                        int nr = cr + d[0], nc = cc + d[1];26                        if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;27                        int next = nr * cols + nc;28                        // Claim before pushing so converging paths cannot add duplicates.29                        if (board[nr][nc] == 'O' && seen.add(next)) stack.addLast(next);30                    }31                }32                // Only a completed no-escape search may destroy the component.33                if (!escapes) for (int cell : seen) board[cell / cols][cell % cols] = 'X';34            }35        }36    }37}

Hints

Hint 1

A border cell can never be surrounded, so every region touching the border is safe by definition.

Hint 2

A safe region spreads through connected cells, so one flood from the borders marks every escapee, not just the border cells themselves.

Hint 3

Stamp the escapees with a temporary mark, flip every unmarked cell, then wash the stamps back to their original value.

Edge Cases

If either dimension is at most 2, every cell lies on a border, so nothing can be captured. This includes a 2 by 200 board; a vague comparison with 3 by 3 is insufficient.
An all-X board is unchanged. An all-O board is also unchanged because every cell connects to a border.
A single inland O surrounded by four X neighbours is captured, even if it touches a border O diagonally.
A winding O path to any edge protects its entire component, including cells far from the border.
At the 200 by 200 maximum, large enclosed components are captured and large escaping components survive without recursive stack overflow.
Both approaches modify existing rows, return nothing, remove all temporary marks, and are idempotent: a second call leaves the final board unchanged.

Common Mistakes and Interview Tips

Using diagonal neighbours falsely protects the center in Example 3. Only four side directions belong to the graph.
Flipping cells before determining escape can destroy a path to the border. The baseline defers all changes; the optimal approach first marks all safe cells.
Marking only border cells misses interior members of escaping components. Traverse their entire O component.
Leaving T marks in the output violates the board contract. Restore them with an else-if branch after capture decisions.
Calling input marking constant-space ignores the explicit stack. Recursive DFS can fail on long 200 by 200 regions; use the published iterative code.
Interview tip: an inland location alone does not imply capture. State the equivalence between escape and a path to a border O before explaining the reverse traversal.

Key Takeaway

When only the components sealed off from the boundary matter, flood inward from the boundary once and treat everything untouched as sealed.