A capture service on a Go-like raster flips groups that have no path to the edge: 'O' is the group, 'X' is the wall. The intern, for every 'O', walked neighbors asking whether that cell could reach a border, and wrote 'O' → 'X' while the walk was still running — no third mark. A 4×4 fixture in staging hung: two adjacent 'O's bounced, or a border-connected cell was already 'X' when its neighbor asked. They added a local seen set but still restarted a full “can I reach the edge?” flood from every 'O'. Staging returned in milliseconds. A million-cell ocean that touched one border cell in production was still walking when the request timed out.

Surrounded Regions asks you to flip every ‘O’ that cannot walk to the border. Same four-direction paint as Flood Fill and Number of Islands; those start from a given seed or every unseen land cell. This one starts from the rim. This is an interview writeup, not a layout lecture. The graphs post owns the layout; the DFS post owns the walk. Here we only care about four neighbor deltas, a temporary safe mark, and capturing what the border flood did not paint.

The problem

Given a char[][] board of 'X' and 'O', capture every surrounded region: flip those 'O's to 'X'. Two 'O's are the same region when you can walk four directions — up, down, left, right — not diagonals. An 'O' connected to the border is not surrounded and stays 'O'. Capture means mutate the board in place.

X X X X
X O O X
X X O X
X O X X     →  X X X X
               X X X X
               X X X X
               X O X X

X O X
X O X
X X X     →  X O X
               X O X
               X X X

X X X
X O X
X X X     →  X X X
               X X X
               X X X

First board: the blob at (1,1), (1,2), (2,2) has no path to the rim; (3,1) sits on the last row and stays. Second: the column of 'O's touches the top edge. Third: one interior 'O', four 'X' walls.

Note: Off-board is not a path. Bounds-check first, then skip 'X' and already-marked cells. A 4-direction int[][] dirs table is the neighbor list; do not special-case four ifs unless the board asks you to name them. A cell on the first or last row or column is already unsurrounded.

Searching from every O is the honest brute force

Do not flip while a search is still running on the same board without a mark. Writing 'O' → 'X' as you walk destroys the path you are still asking about: a later neighbor of a border-connected cell sees 'X' and reports “surrounded.” An unmarked neighbor walk never returns either — from an 'O', step to a neighbor 'O', step back, repeat. Staging’s hang was that bounce.

The honest version marks inside one search with a local set so the walk terminates, asks whether that component touches the rim, throws the marks away, and only then flips that one cell if the answer was no. Correct. Quadratic.

void solveRestart(char[][] board) {
    int m = board.length;
    int n = board[0].length;
    int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            if (board[r][c] == 'O'
                    && !reachesBorder(board, r, c, dirs, new HashSet<>())) {
                board[r][c] = 'X';
            }
        }
    }
}

boolean reachesBorder(char[][] board, int r, int c, int[][] dirs, Set<Integer> seen) {
    if (r < 0 || r >= board.length || c < 0 || c >= board[0].length) {
        return false;
    }
    if (board[r][c] != 'O' || !seen.add(r * board[0].length + c)) {
        return false;
    }
    boolean border = r == 0 || r == board.length - 1 || c == 0 || c == board[0].length - 1;
    for (int[] d : dirs) {
        border |= reachesBorder(board, r + d[0], c + d[1], dirs, seen);
    }
    return border;
}

At a 4×4 fixture this is a rounding error. On one border-touching ocean of V cells you restart a V-cell flood V times: you paid a full walk per ‘O’ for a question that only needs one walk from the rim.

Mark the shore, then flip what is left

Any 'O' that should survive is 4-connected to some border 'O'. Flood from every border 'O' first and paint those cells 'S' (safe). Whatever is still 'O' cannot reach the rim: flip it to 'X'. Restore 'S' → 'O'.

X X X X
X O O X
X X O X
X O X X

border (3,1) is O → S
  no O neighbors

X X X X
X O O X
X X O X
X S X X

leftover O → X, then S → O

X X X X
X X X X
X X X X
X O X X

A corridor to the rim is the same paint: seed (0,1), the flood walks into the interior, and there is nothing left to capture.

X O X X
X O O X
X X X X

border (0,1) → S, floods (1,1), (1,2)
leftover O: none
restore S → O

Walk the four border strips, not every cell, to start. markSafe already no-ops on 'X' and 'S', so corners may be seeded twice. Four deltas, bounds-check, skip anything that is not 'O' — the Java is that paint, then one scan to flip and restore.

void solve(char[][] board) {
    int m = board.length;
    int n = board[0].length;
    int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    for (int r = 0; r < m; r++) {
        markSafe(board, r, 0, dirs);
        markSafe(board, r, n - 1, dirs);
    }
    for (int c = 0; c < n; c++) {
        markSafe(board, 0, c, dirs);
        markSafe(board, m - 1, c, dirs);
    }
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            if (board[r][c] == 'O') {
                board[r][c] = 'X';
            } else if (board[r][c] == 'S') {
                board[r][c] = 'O';
            }
        }
    }
}

void markSafe(char[][] board, int r, int c, int[][] dirs) {
    if (r < 0 || r >= board.length || c < 0 || c >= board[0].length || board[r][c] != 'O') {
        return;
    }
    board[r][c] = 'S';
    for (int[] d : dirs) {
        markSafe(board, r + d[0], c + d[1], dirs);
    }
}

Time is O(mn) — each cell is painted at most once, and each painted cell looks at four neighbors. Space is O(mn) for the call stack on a board of 'O's that all touch the rim. A million-cell shore is a million frames; an iterative ArrayDeque is the same bound without blowing the JVM stack.

Note: Paint safe first, then capture. Flip leftover 'O' → 'X' before the rim flood and you capture cells that still had a path to the edge. Leave 'S' on the board and the prompt’s 'X'/'O' alphabet is wrong. Using 'X' as the safe mark is the intern’s bug wearing a disguise — you still need a third state.

What interviewers usually poke next

  • Iterative flood. Same 'O' → 'S' paint, an ArrayDeque of cells. BFS (offer / poll) or explicit DFS (push / pop). Not java.util.Stack. Not ArrayList.remove(0).
  • Flood Fill. Recolor one component from a given seed. Same four deltas and a mark; the seeds here are every border 'O'.
  • Number of Islands. Count starts and sink land. Same walk; this prompt captures the cells the rim flood did not mark.
  • One row or one column. Every cell is on the border. The flood paints all 'O's safe; the leftover scan flips nothing.
  • Read-only board, or Union-Find. If mutation is forbidden, a boolean[][] safe is the mark. A dummy “border” node with union-to-neighbor is the same idea; say so only if they ask for it.

You are done with this problem when you can say, out loud, why a per-'O' border search is quadratic, why flipping during an unmarked walk corrupts the board, and why flooding the rim first turns capture into a leftover flip.