Surrounded Regions

MediumGraphs · Border DFS🧩 Graph DFS LeetCode #130 ↗Updated Oct 30, 2026

Problem

A board of 'X' and 'O' is given. A group of 4-directionally connected 'O's is captured if none of its cells lies on the board's edge; capture it by turning all of its cells into 'X'. Modify the board in-place; groups touching the edge stay as they are.

InputXXXX / XOOX / XXOX / XOXXOutputXXXX / XXXX / XXXX / XOXX

InputXOutputX

1 ≤ m, n ≤ 200 · board[i][j] is 'X' or 'O' · modify in-place, return nothing

Try it yourself

Java

class Solution {
    public void solve(char[][] board) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Invert the question: instead of asking which regions are surrounded, find the ones that are not — every 'O' reachable from an edge 'O' survives; everything else gets flipped.

PatternGraph DFS

Instinct Connected regions, all paths, reachability, cloning or 2-colouring a graph or grid: dive from a node, mark it, recurse into unvisited neighbours.

Memory hack Mark before you march: go deep, paint as you go, and back up only when every door is already painted.

Open the Graph DFS guide →

Approaches

Brute ForceBFS from Every 'O' to Look for the Edge

Time O((m·n)²)Space O(m·n)

For each 'O', BFS through its region with a fresh visited array; if the search ever stands on an edge cell the cell is safe, otherwise remember it. Flip the remembered cells at the end so earlier flips can't affect later searches.

Java

public void solve(char[][] board) {
    List<int[]> flip = new ArrayList<>();
    for (int r = 0; r < board.length; r++)
        for (int c = 0; c < board[0].length; c++)
            if (board[r][c] == 'O' && !reachesEdge(board, r, c)) flip.add(new int[]{r, c});
    for (int[] f : flip) board[f[0]][f[1]] = 'X';
}
private boolean reachesEdge(char[][] b, int r0, int c0) {
    int m = b.length, n = b[0].length;
    int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    boolean[][] seen = new boolean[m][n];
    Deque<int[]> q = new ArrayDeque<>(List.of(new int[]{r0, c0}));
    seen[r0][c0] = true;
    while (!q.isEmpty()) {
        int[] cur = q.poll();
        int r = cur[0], c = cur[1];
        if (r == 0 || c == 0 || r == m - 1 || c == n - 1) return true;
        for (int[] d : dirs) { // inner cell: neighbours are in bounds
            int x = r + d[0], y = c + d[1];
            if (b[x][y] == 'O' && !seen[x][y]) { seen[x][y] = true; q.add(new int[]{x, y}); }
        }
    }
    return false;
}

Direct translation of the rule, but a region of k cells is explored k times.

BetterUnion-Find with a Virtual “Edge” Node

Time O(m·n·log(m·n))Space O(m·n)

Add one extra node safe. Union every edge 'O' with it, and every 'O' with its right/down 'O' neighbour. Afterwards an 'O' survives iff it is in safe's set.

Java

int[] parent;
public void solve(char[][] board) {
    int m = board.length, n = board[0].length, safe = m * n; // virtual edge node
    parent = new int[m * n + 1];
    for (int i = 0; i <= safe; i++) parent[i] = i;
    for (int r = 0; r < m; r++)
        for (int c = 0; c < n; c++) {
            if (board[r][c] != 'O') continue;
            int id = r * n + c;
            if (r == 0 || c == 0 || r == m - 1 || c == n - 1) union(id, safe);
            if (r + 1 < m && board[r + 1][c] == 'O') union(id, id + n);
            if (c + 1 < n && board[r][c + 1] == 'O') union(id, id + 1);
        }
    for (int r = 0; r < m; r++)
        for (int c = 0; c < n; c++)
            if (board[r][c] == 'O' && find(r * n + c) != find(safe)) board[r][c] = 'X';
}
int find(int x) {
    while (parent[x] != x) x = parent[x] = parent[parent[x]]; // path halving
    return x;
}
void union(int a, int b) { parent[find(a)] = find(b); }

No recursion, one scan to build sets; the extra parent array and log factor make it heavier.

OptimalDFS from the Border, then Flip

Time O(m·n)Space O(m·n) stack

DFS from every edge 'O' and mark its region '#' (safe). One final sweep: '#' → 'O', any remaining 'O' → 'X'. Each cell is marked at most once.

Java

public void solve(char[][] board) {
    int m = board.length, n = board[0].length;
    for (int r = 0; r < m; r++) { mark(board, r, 0); mark(board, r, n - 1); }
    for (int c = 0; c < n; c++) { mark(board, 0, c); mark(board, m - 1, c); }
    for (int r = 0; r < m; r++)
        for (int c = 0; c < n; c++)
            board[r][c] = board[r][c] == '#' ? 'O' : 'X'; // leftover 'O' is captured
}
private void mark(char[][] b, int r, int c) {
    if (r < 0 || c < 0 || r >= b.length || c >= b[0].length || b[r][c] != 'O') return;
    b[r][c] = '#'; // connected to the edge: safe
    mark(b, r + 1, c); mark(b, r - 1, c);
    mark(b, r, c + 1); mark(b, r, c - 1);
}

Linear, in-place, tiny code; use an explicit stack/BFS if recursion depth is a concern.

At a glance

Level	Approach	Time	Space
Brute Force	BFS from Every 'O' to Look for the Edge	`O((m·n)²)`	`O(m·n)`
Better	Union-Find with a Virtual “Edge” Node	`O(m·n·log(m·n))`	`O(m·n)`
Optimal	DFS from the Border, then Flip	`O(m·n)`	`O(m·n) stack`

Common pitfalls

Flipping an 'O' before knowing if its region reaches the edge.
Forgetting to turn '#' back into 'O'.
Recursive find without rank can overflow the stack.

Interview tips

Lead with: find what is not surrounded.
A temp marker '#' replaces a visited grid.
Same border-first trick: LC 1020, LC 417.

Pattern

Flood fill from the border → cells are safe iff connected to the boundary.

My notes saved in this browser