130. Surrounded Regions

Description

Given an m x n matrix board containing 'X' and 'O', capture all regions surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in-place.

A region is surrounded if it's not connected to an 'O' on the border of the board.

Solutions

Solution 1: Depth-First Search (DFS)

This approach uses DFS to identify and mark 'O's that are connected to the border. These 'O's remain as 'O's; all other 'O's are flipped to 'X's.

Algorithm:

1. Iterate Border: Start by iterating through the top, bottom, and sides of the board. For every 'O' found on the border:
2. DFS: Perform a depth-first search starting from that 'O'. The DFS recursively explores adjacent 'O's, marking them with a special character (e.g., '.') to indicate they're connected to the border.
3. Second Pass: After the DFS, iterate through the board again. Replace all '.' characters with 'O's (these are the 'O's connected to the border). Replace all remaining 'O's with 'X's (these are the surrounded 'O's).

Time Complexity: O(M*N), where M and N are the dimensions of the board. We traverse the board twice.

Space Complexity: O(M*N) in the worst case. This is due to the recursive call stack of the DFS, which could reach a depth proportional to the size of the board if the board consists only of 'O's.

Code (Python):

def solve(board):
    if not board:
        return
 
    m, n = len(board), len(board[0])
 
    def dfs(i, j):
        if i < 0 or i >= m or j < 0 or j >= n or board[i][j] != 'O':
            return
        board[i][j] = '.'  # Mark as connected to border
        dfs(i + 1, j)
        dfs(i - 1, j)
        dfs(i, j + 1)
        dfs(i, j - 1)
 
    # Mark border O's
    for i in range(m):
        dfs(i, 0)
        dfs(i, n - 1)
    for j in range(n):
        dfs(0, j)
        dfs(m - 1, j)
 
    # Flip remaining O's
    for i in range(m):
        for j in range(n):
            if board[i][j] == 'O':
                board[i][j] = 'X'
            elif board[i][j] == '.':
                board[i][j] = 'O'
 

Code (Java):

class Solution {
    public void solve(char[][] board) {
        if (board == null || board.length == 0) return;
        int m = board.length, n = board[0].length;
 
        for (int i = 0; i < m; i++) {
            dfs(board, i, 0);
            dfs(board, i, n - 1);
        }
        for (int j = 0; j < n; j++) {
            dfs(board, 0, j);
            dfs(board, m - 1, j);
        }
 
        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] == '.') board[i][j] = 'O';
            }
        }
    }
 
    private void dfs(char[][] board, int i, int j) {
        int m = board.length, n = board[0].length;
        if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] != 'O') return;
        board[i][j] = '.';
        dfs(board, i + 1, j);
        dfs(board, i - 1, j);
        dfs(board, i, j + 1);
        dfs(board, i, j - 1);
    }
}

Other languages would follow a similar structure, employing recursive DFS to explore connected components.

Solution 2: Breadth-First Search (BFS)

BFS can be used instead of DFS; the algorithm remains essentially the same, replacing the recursive calls with a queue-based iteration.

Time Complexity: O(M*N)

Space Complexity: O(M*N) (due to the queue)

Solution 3: Union-Find

The Union-Find data structure can efficiently determine connected components.

Algorithm:

1. Create Union-Find: Initialize a Union-Find data structure. Create a dummy node representing the border.
2. Connect Border 'O's: Connect all 'O's on the border to the dummy node.
3. Connect Internal 'O's: Connect adjacent internal 'O's to each other using Union-Find.
4. Check Connectivity: After connecting all 'O's, check which 'O's are connected to the dummy node (border). Those are the 'O's to keep; the rest are surrounded and should be flipped to 'X'.

Time Complexity: O(MNα(M*N)) where α is the inverse Ackermann function, which is very close to a constant for practical purposes.

Space Complexity: O(M*N)

(Note: Implementing a Union-Find data structure is more involved and requires more code than the DFS/BFS approach. While theoretically efficient, for the size constraints of this problem (M, N <= 200), the difference in practical performance compared to DFS/BFS might be negligible.)