Surrounded Regions: Multiple Solutions and Complexity Analysis

Surrounded Regions: Multiple Solutions and Complexity Analysis

The Surrounded Regions problem is a classic graph traversal challenge frequently encountered in coding interviews and competitive programming. Given a 2D board containing the characters 'X' and 'O', the goal is to capture every region of 'O's that is fully surrounded by 'X's by flipping those 'O's into 'X's. A region is considered surrounded if none of its 'O' cells lie on the border of the board, since border cells cannot be enclosed on all four sides.

This tutorial walks through the problem in detail, presents multiple working solutions, analyzes their time and space complexity, and highlights best practices you can apply to similar grid-based problems.

Problem Statement

You are given an m x n matrix board containing 'X' and 'O'. Capture all regions that are 4-directionally surrounded by 'X'. A region is captured by flipping all 'O's into 'X's within that surrounded region. You must modify the board in-place.

Connectivity is defined in the four cardinal directions: up, down, left, and right. Any 'O' that is connected (directly or transitively) to a border 'O' is not surrounded and must remain unchanged.

Why This Problem Matters

• Graph traversal fundamentals: It reinforces DFS, BFS, and union-find on implicit graphs represented as grids.
• In-place mutation: It teaches how to carefully mutate state without auxiliary structures when needed.
• Border reasoning: The key insight—only border-connected 'O's survive—is a recurring pattern in grid problems (e.g., Pacific Atlantic Water Flow).
• Interview relevance: It appears frequently at companies testing graph and recursion skills.

Key Insight

Instead of trying to find surrounded regions directly (which is hard because you must verify enclosure on all sides), flip the problem around: find the regions that are NOT surrounded. Any 'O' connected to a border cell is safe. Once you mark those, every remaining 'O' must be surrounded and can be flipped to 'X'.

This transforms the problem into a graph reachability question starting from all border 'O' cells.

Solution 1: Depth-First Search from the Border

The DFS approach iterates over every border cell. Whenever it finds an 'O', it launches a DFS that marks all connected 'O' cells with a temporary marker (e.g., '#'). After the traversal, the board is cleaned up: '#' becomes 'O' (safe), and every remaining 'O' becomes 'X' (captured).

Implementation

public class SurroundedRegionsDFS {
    public void solve(char[][] board) {
        if (board == null || board.length == 0) return;
        int rows = board.length;
        int cols = board[0].length;

        // Mark all border-connected 'O's with '#'
        for (int r = 0; r < rows; r++) {
            if (board[r][0] == 'O') dfs(board, r, 0);
            if (board[r][cols - 1] == 'O') dfs(board, r, cols - 1);
        }
        for (int c = 0; c < cols; c++) {
            if (board[0][c] == 'O') dfs(board, 0, c);
            if (board[rows - 1][c] == 'O') dfs(board, rows - 1, c);
        }

        // Final pass: '#' -> 'O', 'O' -> 'X'
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (board[r][c] == 'O') board[r][c] = 'X';
                else if (board[r][c] == '#') board[r][c] = 'O';
            }
        }
    }

    private void dfs(char[][] board, int r, int c) {
        int rows = board.length;
        int cols = board[0].length;
        if (r < 0 || r >= rows || c < 0 || c >= cols) return;
        if (board[r][c] != 'O') return;

        board[r][c] = '#'; // mark as safe
        dfs(board, r + 1, c);
        dfs(board, r - 1, c);
        dfs(board, r, c + 1);
        dfs(board, r, c - 1);
    }
}

Complexity Analysis

• Time complexity: O(m * n). Each cell is visited at most once during DFS, and the final cleanup pass touches every cell once.
• Space complexity: O(m * n) in the worst case due to recursion stack depth. A board entirely filled with 'O's would produce a recursion depth proportional to the number of cells, which can cause a StackOverflowError on large inputs.

Solution 2: Breadth-First Search (Iterative)

BFS avoids the recursion depth issue entirely by using an explicit queue. The logic is identical to DFS—start from border 'O's and mark reachable cells—but the traversal order changes. BFS is generally safer for very large boards.

Implementation

import java.util.LinkedList;
import java.util.Queue;

public class SurroundedRegionsBFS {
    public void solve(char[][] board) {
        if (board == null || board.length == 0) return;
        int rows = board.length;
        int cols = board[0].length;
        Queue queue = new LinkedList<>();

        // Enqueue all border 'O's
        for (int r = 0; r < rows; r++) {
            if (board[r][0] == 'O') { board[r][0] = '#'; queue.offer(new int[]{r, 0}); }
            if (board[r][cols - 1] == 'O') { board[r][cols - 1] = '#'; queue.offer(new int[]{r, cols - 1}); }
        }
        for (int c = 0; c < cols; c++) {
            if (board[0][c] == 'O') { board[0][c] = '#'; queue.offer(new int[]{0, c}); }
            if (board[rows - 1][c] == 'O') { board[rows - 1][c] = '#'; queue.offer(new int[]{rows - 1, c}); }
        }

        int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            for (int[] d : dirs) {
                int nr = cell[0] + d[0];
                int nc = cell[1] + d[1];
                if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && board[nr][nc] == 'O') {
                    board[nr][nc] = '#';
                    queue.offer(new int[]{nr, nc});
                }
            }
        }

        // Final cleanup
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (board[r][c] == 'O') board[r][c] = 'X';
                else if (board[r][c] == '#') board[r][c] = 'O';
            }
        }
    }
}

Complexity Analysis

• Time complexity: O(m * n). Each cell is enqueued and processed at most once.
• Space complexity: O(m * n) in the worst case for the queue, but with no recursion stack risk. In practice, the queue size is bounded by the perimeter of the current frontier, which is often much smaller than the total cell count.

Solution 3: Union-Find (Disjoint Set Union)

Union-Find offers an elegant alternative. The idea is to introduce a virtual "dummy" node representing the outside of the board. Every border 'O' is unioned with the dummy node. Every interior 'O' is unioned with its adjacent 'O' neighbors. After processing, any 'O' that shares a root with the dummy node is safe; all others are captured.

Implementation

public class SurroundedRegionsUF {
    private int[] parent;
    private int[] rank;

    public void solve(char[][] board) {
        if (board == null || board.length == 0) return;
        int rows = board.length;
        int cols = board[0].length;
        int dummy = rows * cols;
        parent = new int[rows * cols + 1];
        rank = new int[rows * cols + 1];
        for (int i = 0; i <= dummy; i++) parent[i] = i;

        int[][] dirs = {{1, 0}, {0, 1}}; // right and down are enough to connect neighbors

        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (board[r][c] != 'O') continue;
                int idx = r * cols + c;
                if (r == 0 || r == rows - 1 || c == 0 || c == cols - 1) {
                    union(idx, dummy);
                }
                for (int[] d : dirs) {
                    int nr = r + d[0];
                    int nc = c + d[1];
                    if (nr < rows && nc < cols && board[nr][nc] == 'O') {
                        union(idx, nr * cols + nc);
                    }
                }
            }
        }

        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (board[r][c] == 'O' && find(r * cols + c) != find(dummy)) {
                    board[r][c] = 'X';
                }
            }
        }
    }

    private int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }

    private void union(int x, int y) {
        int rx = find(x);
        int ry = find(y);
        if (rx == ry) return;
        if (rank[rx] < rank[ry]) parent[rx] = ry;
        else if (rank[rx] > rank[ry]) parent[ry] = rx;
        else { parent[ry] = rx; rank[rx]++; }
    }
}

Complexity Analysis

• Time complexity: O(m * n * α(m * n)), where α is the inverse Ackermann function, which is effectively constant for any practical input size. So this is essentially O(m * n).
• Space complexity: O(m * n) for the parent and rank arrays.

Union-Find is slightly more complex to implement but shines when the problem evolves into dynamic connectivity queries—for example, if cells could be added or flipped incrementally and you needed to answer "is this cell safe?" repeatedly.

Comparing the Solutions

• DFS: Simplest to write and reason about. Risk of stack overflow on large boards. Best for small to medium inputs.
• BFS: Same logic as DFS but avoids recursion limits. Recommended default choice for production code.
• Union-Find: More code, but flexible and extensible. Useful when the problem may grow to include dynamic updates.

Best Practices

• Always check border cells first. The entire problem hinges on border connectivity. Skipping this insight leads to incorrect brute-force solutions.
• Use a temporary marker. Mutating 'O' to '#' during traversal avoids needing a separate visited array and keeps space usage low.
• Prefer BFS for large inputs. Recursion depth in DFS is bounded by the JVM stack, which can be exceeded on boards with long connected regions.
• Handle edge cases explicitly. Empty boards, single-row boards, and single-column boards should be handled up front to avoid index errors.
• Test with all-'O' boards. A board filled entirely with 'O's is the worst case for both time and space, and it exposes stack overflow bugs in DFS implementations.
• Avoid modifying the board during the final pass incorrectly. Make sure the cleanup pass distinguishes between '#' (safe) and 'O' (captured) before flipping.

Common Pitfalls

• Forgetting diagonal connectivity is not allowed. The problem specifies 4-directional connectivity. Including diagonals produces wrong answers.
• Marking visited too late. In BFS, mark a cell as visited when you enqueue it—not when you dequeue it. Otherwise, the same cell can be enqueued multiple times, degrading performance.
• Using a separate visited matrix unnecessarily. While correct, it doubles memory usage. The in-place marker technique is cleaner.
• Not handling the dummy node correctly in Union-Find. The dummy node must have a unique index that does not collide with any real cell index.

Conclusion

The Surrounded Regions problem is a deceptively simple exercise that rewards careful thinking about graph reachability and border conditions. By reframing the question from "find surrounded regions" to "find regions connected to the border," you unlock clean, efficient solutions using DFS, BFS, or Union-Find. BFS is the most robust choice for general use due to its immunity to stack overflow, while Union-Find offers extensibility for more complex variants. Mastering this problem builds intuition that transfers directly to other grid-based graph challenges such as number of islands, walls and gates, and pacific atlantic water flow.