#130 Surrounded Regions

frequently reported atGoogle Bloomberg Uber ByteDance / TikTok

the problem

In plain words

A board holds 'X' and 'O'. Capture every region of 'O's that is completely surrounded by 'X's (4 directions) by flipping it to 'X'. Regions touching the border survive. Modify the board in place.

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

out [[X,X,X,X],[X,X,X,X],[X,X,X,X],[X,O,X,X]]

The bottom 'O' touches the border, so it is not captured.

in board = [[X]]

out [[X]]

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

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternReverse search from the border Grid flood fill

"Surrounded" is hard to test; "connected to the border" is easy. Mark every 'O' reachable from the border as safe — everything else gets captured.

solutions

From brute force to optimal

For each 'O', search its region; if the search never touches the border, flip it.

For each 'O', BFS through 'O's.
If any cell on the border is reached → safe.
Flip the unsafe cells after all checks.

timeO((m · n)²)

Every 'O' may re-explore a region of up to m·n cells.

spaceO(m · n)

Visited grid + queue per search, plus the flip list.

javajava.util.*

1class Solution {2    private static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};3 4    /** For each 'O', BFS to see if it can reach the border. If not, it is surrounded. */5    public void solve(char[][] board) {6        int rows = board.length, cols = board[0].length;7        List<int[]> flip = new ArrayList<>();8        for (int r = 0; r < rows; r++)9            for (int c = 0; c < cols; c++)10                if (board[r][c] == 'O' && !reachesBorder(board, r, c)) flip.add(new int[] {r, c});11        for (int[] cell : flip) board[cell[0]][cell[1]] = 'X'; // flip after all checks12    }13 14    private boolean reachesBorder(char[][] b, int sr, int sc) {15        int rows = b.length, cols = b[0].length;16        boolean[][] seen = new boolean[rows][cols];17        Deque<int[]> queue = new ArrayDeque<>();18        queue.offer(new int[] {sr, sc});19        seen[sr][sc] = true;20        while (!queue.isEmpty()) {21            int[] cell = queue.poll();22            int r = cell[0], c = cell[1];23            if (r == 0 || c == 0 || r == rows - 1 || c == cols - 1) return true;24            for (int[] d : DIRS) {25                int nr = r + d[0], nc = c + d[1];26                if (b[nr][nc] == 'O' && !seen[nr][nc]) { // not on border, so neighbours are in range27                    seen[nr][nc] = true;28                    queue.offer(new int[] {nr, nc});29                }30            }31        }32        return false;33    }34}

DFS from every border 'O' and tag its region 'S'. Then flip 'O' → 'X' and 'S' → 'O'.

Walk the 4 borders; DFS each 'O' found, marking 'S'.
Sweep the board: 'O' → 'X' (captured), 'S' → 'O' (restored).

timeO(m · n)

Each cell is marked at most once, then swept once.

spaceO(m · n)

Recursion depth in the worst case (no extra grid needed).

javajava.util.*

1class Solution {2    private static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};3 4    /** Flip the question: mark every 'O' connected to the border as safe; everything else is captured. */5    public void solve(char[][] board) {6        int rows = board.length, cols = board[0].length;7        for (int r = 0; r < rows; r++) {8            markSafe(board, r, 0);9            markSafe(board, r, cols - 1);10        }11        for (int c = 0; c < cols; c++) {12            markSafe(board, 0, c);13            markSafe(board, rows - 1, c);14        }15        for (int r = 0; r < rows; r++)16            for (int c = 0; c < cols; c++) {17                if (board[r][c] == 'O') board[r][c] = 'X';      // never reached from the border18                else if (board[r][c] == 'S') board[r][c] = 'O'; // restore safe cells19            }20    }21 22    private void markSafe(char[][] b, int r, int c) {23        if (r < 0 || c < 0 || r >= b.length || c >= b[0].length || b[r][c] != 'O') return;24        b[r][c] = 'S'; // temporary "safe" mark25        for (int[] d : DIRS) markSafe(b, r + d[0], c + d[1]);26    }27}

in the room

How to say it in the interview

talk track

Say: "I'll flip the question — find what's safe, not what's surrounded."
Mention a union-find variant with a virtual 'border' node as an alternative.

traps

Flipping cells during the brute-force checks — later checks then see a modified board.

what they ask next

Follow-ups

Can you do it with Union-Find?

Yes: add one virtual "border" node. Union every border 'O' with it and every 'O' with its 'O' neighbours. At the end, flip each 'O' whose root is not the border's root.

before you submit

Edge cases to test

Boards with only 1 or 2 rows/columns: every cell is on the border, so nothing is captured.
An 'O' region that touches the border at a single cell survives completely.
All 'X' → unchanged.

practise next