Surrounded Regions

Medium Top 250

Associated Patterns

Interviewed At (Company Tags)

AmazonGoogleMicrosoft

Problem Description

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 in that surrounded region.

Examples

Example 1:

Input: board = [[“X”,“X”,“X”,“X”],[“X”,“O”,“O”,“X”],[“X”,“X”,“O”,“X”],[“X”,“O”,“X”,“X”]] Output: [[“X”,“X”,“X”,“X”],[“X”,“X”,“X”,“X”],[“X”,“X”,“X”,“X”],[“X”,“O”,“X”,“X”]] Explanation: The bottom-left O is connected to the border, so it stays. The interior O region gets flipped.

Constraints

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

Think Backwards: Mark the Survivors First

Instead of finding surrounded regions (hard: you need to check if a region touches the border), find the unsurrounded regions first. Any 'O' touching the border is safe. Any 'O' connected to a safe cell is also safe. Everything else gets flipped.

Pass 1: from every border 'O', DFS/BFS and mark reachable 'O' cells as 'S' (safe). Pass 2: flip all remaining 'O' to 'X', then restore 'S' back to 'O'.

Solution: Reverse DFS from Borders

class Solution {
    public void solve(char[][] board) {
        int rows = board.length, cols = board[0].length;

        // mark all 'O' reachable from border as 'S' (safe)
        for (int r = 0; r < rows; r++) {
            dfs(board, r, 0);
            dfs(board, r, cols - 1);
        }
        for (int c = 0; c < cols; c++) {
            dfs(board, 0, c);
            dfs(board, rows - 1, c);
        }

        // flip: 'O' -> 'X' (surrounded), 'S' -> 'O' (safe)
        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] == 'S') board[r][c] = 'O';
            }
        }
    }

    private void dfs(char[][] board, int r, int c) {
        if (r < 0 || r >= board.length || c < 0 || c >= board[0].length || board[r][c] != 'O') {
            return;
        }
        board[r][c] = 'S'; // mark as safe
        dfs(board, r+1, c); dfs(board, r-1, c);
        dfs(board, r, c+1); dfs(board, r, c-1);
    }
}

class Solution:
    def solve(self, board: list[list[str]]) -> None:
        rows, cols = len(board), len(board[0])

        def dfs(r: int, c: int):
            if r < 0 or r >= rows or c < 0 or c >= cols or board[r][c] != 'O':
                return
            board[r][c] = 'S'  # mark as safe
            dfs(r+1, c); dfs(r-1, c); dfs(r, c+1); dfs(r, c-1)

        # mark border-connected 'O's as safe
        for r in range(rows):
            dfs(r, 0); dfs(r, cols - 1)
        for c in range(cols):
            dfs(0, c); dfs(rows - 1, c)

        # flip: surrounded 'O' -> 'X', safe 'S' -> 'O'
        for r in range(rows):
            for c in range(cols):
                if board[r][c] == 'O':
                    board[r][c] = 'X'
                elif board[r][c] == 'S':
                    board[r][c] = 'O'

#include <vector>

class Solution {
public:
    void solve(std::vector<std::vector<char>>& board) {
        int rows = board.size(), cols = board[0].size();

        for (int r = 0; r < rows; r++) { dfs(board, r, 0); dfs(board, r, cols-1); }
        for (int c = 0; c < cols; c++) { dfs(board, 0, c); dfs(board, rows-1, c); }

        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] == 'S') board[r][c] = 'O';
            }
        }
    }

private:
    void dfs(std::vector<std::vector<char>>& board, int r, int c) {
        if (r < 0 || r >= (int)board.size() || c < 0 || c >= (int)board[0].size()
                || board[r][c] != 'O') return;
        board[r][c] = 'S';
        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). Every cell is visited at most once.
Space Complexity: O(m * n) worst case for the recursion stack.

Where it breaks: a 200 x 200 board of all 'O' cells causes recursion depth of up to 40,000. Java’s default stack size might overflow. Use an explicit stack (BFS or iterative DFS) for very large inputs.

Common Mistakes

Trying to identify surrounded regions directly by checking borders. This requires flood fill + border check, which is equivalent in code but harder to reason about. The “mark safe, flip rest” approach is more intuitive.
Forgetting to run border DFS on all four edges (all rows in col 0 and col n-1, all cols in row 0 and row m-1).