Surrounded Regions medium

Problem Statement

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

A region is surrounded if it is completely surrounded by an 'X'. Any 'O' that is not on the border and is not connected to an 'O' on the border is captured.

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.

Example 2:

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

Steps and Explanation

The core idea is to identify and mark all 'O's that are connected to the border. These 'O's should not be flipped. We achieve this using Depth-First Search (DFS) or Breadth-First Search (BFS). The algorithm involves these steps:

1. Identify Border 'O's: Iterate through the first and last rows, and first and last columns of the board. If an 'O' is found, perform a Depth-First Search (DFS) starting from that 'O'.

2. Depth-First Search (DFS): The DFS function recursively explores all connected 'O's. During the traversal, it marks these connected 'O's with a special character (e.g., 'T'). This mark indicates that the 'O' is connected to the border and should not be flipped.

3. Flip Remaining 'O's: Iterate through the board again. Any 'O' that is not marked with 'T' is surrounded and should be flipped to 'X'.

4. Restore Marked 'O's: Replace all 'T's with 'O's to restore the original 'O's that were connected to the border.

Code

def solve(board):
    """
    Solves the Surrounded Regions problem using Depth-First Search.

    Args:
        board: A list of lists representing the board.
    """
    if not board:
        return

    rows, cols = len(board), len(board[0])

    # Mark border O's with 'T' using DFS
    def dfs(row, col):
        if row < 0 or row >= rows or col < 0 or col >= cols or board[row][col] != 'O':
            return
        board[row][col] = 'T'
        dfs(row + 1, col)
        dfs(row - 1, col)
        dfs(row, col + 1)
        dfs(row, col - 1)

    # Mark border O's
    for i in range(rows):
        dfs(i, 0)
        dfs(i, cols - 1)
    for j in range(cols):
        dfs(0, j)
        dfs(rows - 1, j)

    # Flip remaining O's to X's and restore marked O's
    for i in range(rows):
        for j in range(cols):
            if board[i][j] == 'O':
                board[i][j] = 'X'
            elif board[i][j] == 'T':
                board[i][j] = 'O'

Complexity

• Time Complexity: O(M*N), where M and N are the number of rows and columns in the board. We traverse the board multiple times.
• Space Complexity: O(MN) in the worst case, due to the recursive calls in DFS. The space usage depends on the depth of the recursion. In cases where there are many connected 'O's near the border, the space complexity could be closer to O(MN) However, if 'X's dominate, the space used could be significantly smaller. A BFS approach would have a better space complexity guarantee of O(min(M,N)) in terms of the queue.