algoadvance

Given an m x n matrix board containing 'X' and 'O', capture all regions that are surrounded by 'X'. A region is captured by flipping all 'O's into 'X's in that surrounded region.

Example

Input:

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' connected to an border 'O' cannot be flipped to 'X'. Any 'O' that is not on the border or not connected to a border 'O' will be flipped to 'X'. Two cells are connected if they are adjacent cells connected horizontally or vertically.

Clarifying Questions

1. Does the input matrix always contain at least one cell?
   • Yes, the input matrix board will contain at least one cell.
2. Will the board always be rectangular in shape?
   • Yes, the input matrix board will always be rectangular.
3. Can the board contain invalid characters other than ‘X’ or ‘O’?
   • No, the board will only contain the characters ‘X’ and ‘O’.

Strategy

1. Traverse the board and start a Depth-First Search (DFS) from all 'O's located on the border.
2. Mark these 'O's and all connected 'O's (i.e., that are not surrounded by 'X') with a temporary marker, for example, 'T'.
3. After marking, traverse the entire board again:
   • Convert all 'T' (temporary marker) back to 'O'.
   • Convert all other 'O' (which are surrounded by 'X') to 'X'.

Code

Here is the Python code to solve the problem:

def solve(board):
    if not board or not board[0]:
        return

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

    def dfs(r, c):
        if r < 0 or c < 0 or r >= rows or c >= cols or board[r][c] != 'O':
            return
        board[r][c] = 'T'  # Temporary marker
        dfs(r-1, c)
        dfs(r+1, c)
        dfs(r, c-1)
        dfs(r, c+1)

    # Step 1: Perform DFS for 'O's on the border
    for i in range(rows):
        if board[i][0] == 'O':
            dfs(i, 0)
        if board[i][cols-1] == 'O':
            dfs(i, cols-1)

    for j in range(cols):
        if board[0][j] == 'O':
            dfs(0, j)
        if board[rows-1][j] == 'O':
            dfs(rows-1, j)

    # Step 2: Flip all the 'O's to 'X' and all 'T's back to 'O'
    for r in range(rows):
        for c in range(cols):
            if board[r][c] == 'O':
                board[r][c] = 'X'
            elif board[r][c] == 'T':
                board[r][c] = 'O'

# Example Usage:
board = [
    ['X', 'X', 'X', 'X'],
    ['X', 'O', 'O', 'X'],
    ['X', 'X', 'O', 'X'],
    ['X', 'O', 'X', 'X']
]
solve(board)
print(board)
# Output:
# [['X', 'X', 'X', 'X'],
#  ['X', 'X', 'X', 'X'],
#  ['X', 'X', 'X', 'X'],
#  ['X', 'O', 'X', 'X']]

Time Complexity

• The time complexity of this approach is O(m * n), where m is the number of rows and n is the number of columns in the board because each cell is visited a constant number of times.
• The space complexity is dominated by the recursion stack of DFS, which in the worst case can go up to O(m * n).

This approach efficiently marks non-surrounded ‘O’s and flips only those that are truly surrounded by ‘X’s, providing an optimal solution to the problem.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?