Surrounded Regions

1. Problem & Core Objective

Given an m × n board of 'X' and 'O', capture all regions surrounded by 'X' — flip every 'O' in such a region to 'X'. A region is surrounded if it does not touch the border.

X X X X          X X X X
X O O X    →     X X X X
X X O X          X X X X
X O X X          X O X X      ← this O touches the border, so it survives

Constraints: 1 <= m, n <= 200 · cells are 'X' or 'O'

What's actually being tested: inverting the condition. "Surrounded" is awkward to test directly — you'd have to explore a region and prove it never escapes. "Touches the border" is trivial to test, and every other region is surrounded by definition. It's the same reversal idea as question 6, applied to a membership test rather than a direction.

2. First-Principles Thought Process

Testing "surrounded" directly is awkward

To decide whether a region is surrounded you'd flood it, watching for any cell on the border. If none is found, flip the whole region.

That works, but it's two-phase: collect the region, decide, then possibly flip. And the decision can't be made until the flood completes, so you must hold the cells.

Invert it

A region is surrounded exactly when it doesn't touch the border. So:

1. Flood from every 'O' on the border, marking everything reachable as safe.
2. Every remaining 'O' is, by definition, surrounded — flip it.

Now the traversal never needs to decide anything. It just marks, and the decision becomes a trivial per-cell test afterwards.

Why this is strictly simpler

The border 'O's are a small, known seed set. One multi-source flood marks all survivors, and a single pass flips the rest. No region needs to be collected, and no post-hoc judgement is made.

It's the same shape as question 6: start from the thing that's easy to identify, and let the definition do the rest.

The marking trick

Rather than a separate boolean[][], temporarily rewrite safe cells as '#':

pass 1: flood border 'O' → '#'
pass 2: every 'O' → 'X'    (surrounded)
        every '#' → 'O'    (restore the survivors)

Two passes over the grid, O(m·n), no extra array. The sentinel must not collide with 'X' or 'O' — '#' is safe, and that's worth confirming rather than assuming.

3. Solution Paths

Approach 1 — Flood each region, decide, then flip (brute force)

public void solve(char[][] board) {
    int m = board.length, n = board[0].length;
    boolean[][] visited = new boolean[m][n];

    for (int r = 0; r < m; r++)
        for (int c = 0; c < n; c++) {
            if (board[r][c] != 'O' || visited[r][c]) continue;

            List<int[]> region = new ArrayList<>();
            boolean touchesBorder = collect(board, r, c, visited, region);
            if (!touchesBorder)
                for (int[] cell : region) board[cell[0]][cell[1]] = 'X';
        }
}

private boolean collect(char[][] b, int r, int c, boolean[][] vis, List<int[]> out) {
    if (r < 0 || r >= b.length || c < 0 || c >= b[0].length) return false;
    if (b[r][c] != 'O' || vis[r][c]) return false;

    vis[r][c] = true;
    out.add(new int[]{r, c});
    boolean border = r == 0 || c == 0 || r == b.length - 1 || c == b[0].length - 1;

    for (int[] d : DIRS) border |= collect(b, r + d[0], c + d[1], vis, out);
    return border;
}

• Time O(m · n) · Space O(m · n) for the region list plus the stack

Counter-questions on this approach

⭐ "Same complexity as the optimal. What's the objection?"

It has to collect every region into a list, because the flip decision can't be made until the flood finishes and reports whether any cell touched the border. So the cells must be held.

Inverting the condition removes that entirely: flood from the border, and every unmarked 'O' is surrounded by definition. No collection, no decision, no list.

⭐ "There's a subtle bug risk in border |= collect(...). What is it?"

Using || instead of | would short-circuit. Once one recursive call returns true, the remaining directions would never run — so part of the region would go unvisited and unmarked, and could be flooded again later as a separate region.

| forces all four calls to execute. It's a genuine trap: || is the reflexive choice for booleans and it silently corrupts the traversal here.

"Is the visited array necessary given cells are collected?"

Yes — without it the recursion would revisit cells and loop forever, since 'O' cells aren't modified during the flood. The optimal version avoids this by rewriting cells as it goes, so the character itself is the marker.

Approach 2 — Flood from the border, then flip (optimal)

private static final int[][] DIRS = {{1,0},{-1,0},{0,1},{0,-1}};

public void solve(char[][] board) {
    int m = board.length, n = board[0].length;

    for (int r = 0; r < m; r++) {                 // left and right edges
        markSafe(board, r, 0);
        markSafe(board, r, n - 1);
    }
    for (int c = 0; c < n; c++) {                 // top and bottom edges
        markSafe(board, 0, c);
        markSafe(board, m - 1, c);
    }

    for (int r = 0; r < m; r++)
        for (int c = 0; c < n; c++) {
            if (board[r][c] == 'O') board[r][c] = 'X';        // surrounded — capture
            else if (board[r][c] == '#') board[r][c] = 'O';   // safe — restore
        }
}

private void markSafe(char[][] b, int r, int c) {
    if (r < 0 || r >= b.length || c < 0 || c >= b[0].length) return;
    if (b[r][c] != 'O') return;                   // 'X' or already marked '#'

    b[r][c] = '#';                                 // mark BEFORE recursing
    for (int[] d : DIRS) markSafe(b, r + d[0], c + d[1]);
}

Trace — the example board:

Result matches ✓

• Time O(m · n) · Space O(m · n) worst-case recursion depth

Counter-questions on this approach

⭐ "Why is 'touches the border' equivalent to 'not surrounded'?"

By the problem's definition, a region is surrounded when it's completely enclosed by 'X'. Any region containing a border cell has at least one side facing outward, so it cannot be enclosed.

And connectivity is transitive: if any cell of a region touches the border, the whole region is safe, because the flood reaches all of it. So marking from the border marks exactly the non-surrounded regions, and the complement is exactly the surrounded ones.

That's why no decision is ever made — the definition partitions the cells for me.

⭐ "Why mark '#' before recursing?"

Same discipline as every flood fill: the four recursive calls include the cell I came from, and if it's still 'O' the recursion bounces between the two forever.

Marking first makes b[r][c] != 'O' true for those calls, so they return immediately. And it means the character itself is the visited marker — no boolean[][] needed.

⭐ "Why is '#' safe as a sentinel?"

Because the board contains only 'X' and 'O', so '#' can never be a legitimate value and b[r][c] != 'O' correctly rejects both 'X' and an already-marked cell.

That's a fact to check against the constraints rather than assume. If the board could contain '#', I'd need a separate boolean[][].

"Why does the final pass check 'O' before '#'?"

The order doesn't matter — they're mutually exclusive and the branches are independent. What matters is doing both in one pass, since flipping 'O' → 'X' first and then '#' → 'O' in a separate pass would be two sweeps for no benefit.

"Does seeding every border cell duplicate work?"

Most calls return immediately because the cell is 'X' or already '#'. Each cell is genuinely flooded at most once thanks to the marking, so the total is O(m · n) regardless of how many seeds there are.

"Stack depth at 200 × 200?"

A board of all 'O' is one 40,000-cell region, so the recursion could reach that depth and overflow. I'd use BFS or an explicit stack at this size — the same concern as in Number of Islands and question 6.

Comparison

4. Why the Optimal Wins

Both are O(m · n), so this is about structure, not speed.

The forward version must collect each region and make a judgement, because "surrounded" can only be decided after seeing the whole region. Inverting to "touches the border" makes the seed set trivially identifiable, so the traversal only marks and the classification falls out of the definition.

That removes the region list, the decision, and the separate visited array.

The framing worth keeping:

"Surrounded" is hard to test; "touches the border" is trivial. Flood from the easy set, and everything unmarked is the answer by definition.

Same reversal as question 6 — there it changed the direction of the search, here it changes which set you start from.

5. Java Prerequisites

Border seeding

for (int r = 0; r < m; r++) { markSafe(board, r, 0); markSafe(board, r, n-1); }
for (int c = 0; c < n; c++) { markSafe(board, 0, c); markSafe(board, m-1, c); }

Sentinel marking — the character is the visited flag:

if (b[r][c] != 'O') return;    // 'X' or already '#'
b[r][c] = '#';                 // mark BEFORE recursing

Verify the sentinel is outside the alphabet — here the board holds only 'X' and 'O'.

| vs || when combining recursive results. || short-circuits and would skip the remaining directions — a real bug if you need all of them to run.

Single restore pass — flip 'O' → 'X' and '#' → 'O' in the same sweep.

6. Interview Communication Guide

Clarifying questions: Modify the board in place (yes — void return)? Are diagonals connected (no)? Does a region touching the border survive entirely (yes — connectivity is transitive)? Can the board contain characters other than 'X' and 'O' (no — which is what makes '#' safe)?

The pitch

"Testing 'is this region surrounded?' directly is awkward — you'd flood the region watching for a border cell, hold all its cells, and only then decide whether to flip them.

So I invert the condition. A region is surrounded exactly when it doesn't touch the border. The border 'O's are trivially identifiable, so I flood from them and mark everything reachable as safe. Then every remaining 'O' is surrounded by definition — no decision needed.

That's valid because connectivity is transitive: if any cell of a region touches the border, flooding reaches the whole region, so the entire thing is safe.

For marking I temporarily rewrite safe cells as '#' rather than allocating a boolean[][]. The board only contains 'X' and 'O', so '#' can't collide — a fact worth checking against the constraints rather than assuming.

Then one final pass: 'O' becomes 'X' (captured), '#' becomes 'O' (restored).

I mark before recursing, as in every flood fill — otherwise the four calls include the cell I came from and the recursion bounces between them forever.

O(m·n): each cell is flooded at most once, plus one restore pass.

At 200 × 200 a board of all 'O' is one 40,000-cell region, so recursion could overflow — I'd use BFS or an explicit stack at that size.

One trap if you do write the forward version: combining the recursive results with || short-circuits and skips directions. It needs |."

Edge cases to volunteer:

Name the all-'O' board and the single cell. Both must be left completely unchanged, and a solution that flips first and asks later gets them wrong.

7. Follow-Up Questions — Modified Constraints

⭐ "Count the surrounded regions rather than flipping them."

After the border flood, run the island-counting loop over the remaining 'O's — each connected group is one surrounded region. Reuses Number of Islands directly on the complement set.

⭐ "Restore the board afterwards instead of capturing."

Keep a list of the cells you flipped and undo them. Or, since the transformation is deterministic, recompute — though that's O(m·n) again. Worth noting the operation is not self-inverse: once flipped, a region's original extent is lost.

"Diagonals count as connections."

Eight offsets in DIRS. More cells become border-connected, so fewer regions are captured — the opposite of what people usually expect from adding connectivity.

"What if the board could contain '#' legitimately?"

The sentinel collides, so the marking silently treats real '#' cells as safe. Use a separate boolean[][] instead. This is the general lesson about sentinels — verify they're outside the data's range, exactly as with -1 for heights and long bounds for BST validation.

"What if the grid were 10^4 × 10^4?"

10^8 cells — recursion is out, and even the queue needs care. Encode coordinates as a single int rather than allocating int[] per cell. The in-place '#' marking is a real advantage at this scale, since a boolean[][] would be another 100 MB.

"Capture regions surrounded by a specific character rather than 'X'."

Parameterise the wall character. The algorithm is unchanged — which is a good sign the border-inversion idea, not the specific characters, was doing the work.