Surrounded Regions medium

Problem Statement

Given an m x n matrix board containing 'X' and 'O' (representing cells in a board), capture all regions surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region.

A region is surrounded by 'X' if there are 'X's on the border of the board or regions with 'X's surrounding it.

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: Surrounded regions should not be on the border, which means that any 'O' that is on the border of the board should not be flipped to 'X'. Any 'O' that is not on the border and it is surrounded by 'X' will be flipped to 'X'. If it is not surrounded, it is left as 'O'.

Example 2:

Input: board = [["X"]]
Output: [["X"]]

Steps to Solve

1. Identify Border 'O's: Perform a Depth-First Search (DFS) or Breadth-First Search (BFS) starting from all 'O's on the border of the board. Mark these 'O's and their connected 'O's as safe (e.g., using a different character like 'S'). These 'O's are not surrounded.

2. Capture Surrounded 'O's: Iterate through the board. If you encounter an 'O' that is not marked as safe ('S'), change it to 'X'.

3. Restore Safe 'O's: Change all the 'S' marks back to 'O's.

Explanation

The key idea is to identify and protect 'O's that are connected to the border. These 'O's cannot be surrounded. We use DFS to efficiently explore connected components of 'O's starting from the border. Any 'O' not reached by this DFS must be surrounded and can be flipped.

Code (Java)

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

        int m = board.length;
        int n = board[0].length;

        // Step 1: Mark border 'O's as safe ('S')
        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);
        }

        // Step 2: Capture surrounded 'O's
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'O') board[i][j] = 'X';
                else if (board[i][j] == 'S') board[i][j] = 'O'; //Step 3
            }
        }
    }

    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] = 'S';
        dfs(board, i + 1, j);
        dfs(board, i - 1, j);
        dfs(board, i, j + 1);
        dfs(board, i, j - 1);
    }
}

Complexity Analysis

• Time Complexity: O(M*N), where M and N are the dimensions of the board. We visit each cell at most once in the DFS.

• Space Complexity: O(M*N) in the worst case. This is due to the recursive calls of DFS, which could potentially occupy space proportional to the size of the board (although this is less likely given it's a connected component). In practice, it often uses less space because many cells are 'X' or already marked 'S'.