Surrounded Regions

You are given an m x n matrix board containing letters 'X' and 'O', capture regions that are surrounded:

• Connect: A cell is connected to adjacent cells horizontally or vertically.
• Region: To form a region connect every 'O' cell.
• Surround: A region is surrounded if none of the 'O' cells in that region are on the edge of the board. Such regions are completely enclosed by 'X' cells.

To capture a surrounded region, replace all 'O's with 'X's in-place within the original board. You do not need to return anything.

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:

In the above diagram, the bottom region is not captured because it is on the edge of the board and cannot be surrounded.

Example 2:

Input: board = [[“X”]]

Output: [[“X”]]

Constraints:

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

Approach: DFS from the Boundary

Algorithm

1. Any 'O' connected to the board edge cannot be captured, so it must be preserved
2. Run DFS from every 'O' on the border, marking reachable cells with a temporary marker 'M'
3. Sweep the whole board: 'M' becomes 'O' (safe), and any remaining 'O' becomes 'X' (captured)

Time & Space Complexity

• Time Complexity: O(m * n) - every cell is visited a constant number of times
• Space Complexity: O(m * n) - worst-case recursion depth (or an explicit stack)

Java Implementation

public class SurroundedRegions {

    /**
     * Capture all regions surrounded by 'X' in-place.
     * @param board m x n board of 'X' and 'O'
     */
    public void solve(char[][] board) {
        int m = board.length;
        int n = board[0].length;

        for (int i = 0; i < m; i++) {
            if (board[i][0] == 'O') {
                dfs(board, i, 0);
            }
            if (board[i][n - 1] == 'O') {
                dfs(board, i, n - 1);
            }
        }
        for (int j = 0; j < n; j++) {
            if (board[0][j] == 'O') {
                dfs(board, 0, j);
            }
            if (board[m - 1][j] == 'O') {
                dfs(board, m - 1, j);
            }
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'M') {
                    board[i][j] = 'O';
                } else if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                }
            }
        }
    }

    private void dfs(char[][] board, int i, int j) {
        int m = board.length;
        int n = board[0].length;
        if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] != 'O') {
            return;
        }
        board[i][j] = 'M';
        dfs(board, i + 1, j);
        dfs(board, i - 1, j);
        dfs(board, i, j + 1);
        dfs(board, i, j - 1);
    }

    // Test method
    public static void main(String[] args) {
        SurroundedRegions sr = new SurroundedRegions();
        char[][] board = {
            {'X', 'X', 'X', 'X'},
            {'X', 'O', 'O', 'X'},
            {'X', 'X', 'O', 'X'},
            {'X', 'O', 'X', 'X'}
        };
        sr.solve(board);
        System.out.println("Output:");
        for (char[] row : board) {
            System.out.println(java.util.Arrays.toString(row));
        }
        // Expected: [X,X,X,X],[X,X,X,X],[X,X,X,X],[X,O,X,X]

        char[][] board2 = {{'X'}};
        sr.solve(board2);
        System.out.println(java.util.Arrays.toString(board2[0])); // Expected: [X]
    }
}

Example Walkthrough

For the 4x4 board:

1. Border 'O' at (3,1) is marked 'M'; its connected region has no other cells
2. Interior 'O's at (1,1), (1,2), (2,2) are not connected to the border
3. 'M' at (3,1) is restored to 'O'; the interior 'O's are flipped to 'X'

Key Points

1. Work Backwards: Instead of detecting surrounded regions, preserve the connected-to-edge ones
2. Temporary Marker: 'M' records safe cells before the final sweep
3. Edge Scan: Only 'O's on the four borders can be the start of safe regions
4. In-Place: No extra board copy needed; the marker makes a single two-pass transformation
5. Alternative: BFS with a queue or Union-Find achieves the same result