Problem Statement

You are given an m x n matrix board containing 'X' and 'O'. Capture all regions that are 4-directionally surrounded by 'X'.

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

Additional information

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

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' on the border and any 'O' connected to it will not be flipped.

Example 2:

Input: board = [["X"]]

Output: [["X"]]

Brute Force (Component-Building DFS)

Intuition

A highly literal way to solve this is to iterate through every cell on the board. When we find an 'O', we start a Depth-First Search (DFS) to map out the entire connected component of 'O's.

As we collect all the coordinates of this connected component, we also check if any of these coordinates touch the border (row 0, row M-1, col 0, or col N-1). Once the DFS finishes, if the component never touched a border, we know it is completely surrounded! We can then iterate through our collected coordinates and flip them all to 'X'.

Algorithm

1. If the board is empty, return immediately.
2. Store dimensions rows and cols.
3. Initialize a visited set to keep track of processed 'O's.
4. Loop through every row and column.
5. If board[r][c] == "O" and the cell is not in visited, launch an iterative DFS using a stack.
6. Inside the DFS:

• Maintain a component list of coordinates belonging to this group.
• Maintain a boolean flag touches_boundary set to False.
• Pop coordinates, add them to component.
• If the coordinate is on the boundary, set touches_boundary = True.
• Check 4 neighbors. If they are 'O' and unvisited, add to stack and visited.

7. After the DFS loop for that component finishes, if touches_boundary is False, loop through component and set those board cells to 'X'.

def solve(board: list[list[str]]) -> None:
    if not board or not board[0]:
        return
        
    rows, cols = len(board), len(board[0])
    visited = set()
    
    for r in range(rows):
        for c in range(cols):
            if board[r][c] == "O" and (r, c) not in visited:
                component = []
                touches_boundary = False
                
                # Iterative DFS
                stack = [(r, c)]
                visited.add((r, c))
                
                while stack:
                    curr_r, curr_c = stack.pop()
                    component.append((curr_r, curr_c))
                    
                    if curr_r == 0 or curr_r == rows - 1 or curr_c == 0 or curr_c == cols - 1:
                        touches_boundary = True
                        
                    for dr, dc in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
                        nr, nc = curr_r + dr, curr_c + dc
                        if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] == "O" and (nr, nc) not in visited:
                            visited.add((nr, nc))
                            stack.append((nr, nc))
                            
                # Capture the region if it's completely surrounded
                if not touches_boundary:
                    for cr, cc in component:
                        board[cr][cc] = "X"

Time & Space Complexity

• Time complexity: O(M * N)

• Reason: We iterate through all M * N cells. Each cell is added to the visited set and processed by the DFS stack at most once.

• Space complexity: O(M * N)

• Reason: The visited set, the DFS stack, and the component list can all grow up to the size of the entire board in the worst-case scenario (e.g., a board entirely filled with 'O's).

Reverse Boundary DFS - Optimal

Intuition

Instead of checking every single 'O' to see if it reaches the border, we can flip the logic: start at the borders!

We know that any 'O' on the border is entirely safe from being captured. Furthermore, any inner 'O' connected to a border 'O' is also safe.
So, we can run a DFS strictly starting from the 'O's sitting on the edges of the board. We temporarily change these "safe" 'O's into a special character, like 'T'.

Once the boundary searches finish spreading inwards, any 'O' left on the board is guaranteed to be completely surrounded and ready for capture. We just iterate over the board one last time, flipping remaining 'O's to 'X', and reverting our safe 'T's back to 'O'.

Algorithm

1. Store dimensions rows and cols.
2. Define a recursive helper dfs(r, c).

• If r or c are out of bounds, or if board[r][c] != "O", return immediately.
• Mark the cell as safe: board[r][c] = "T".
• Recursively call dfs on the 4 adjacent neighbors.

3. Step 1: Loop through the first and last rows. If you see an "O", call dfs(r, c).
4. Step 2: Loop through the first and last columns. If you see an "O", call dfs(r, c).
5. Step 3: Iterate over the entire board.

• If you see an "O", it means it was never reached by the boundary DFS. Capture it by setting it to "X".
• If you see a "T", it is safe. Unmark it by reverting it back to "O".

def solve(board: list[list[str]]) -> None:
    if not board or not board[0]:
        return
        
    rows, cols = len(board), 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
            
        # Mark as safe
        board[r][c] = "T"
        
        dfs(r + 1, c)
        dfs(r - 1, c)
        dfs(r, c + 1)
        dfs(r, c - 1)
        
    # Phase 1: Capture unsurrounded regions starting from the borders
    for r in range(rows):
        dfs(r, 0)
        dfs(r, cols - 1)
        
    for c in range(cols):
        dfs(0, c)
        dfs(rows - 1, c)
        
    # Phase 2: Capture surrounded regions (O -> X) and unmark safe regions (T -> 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"

Time & Space Complexity

• Time complexity: O(M * N)

• Reason: The algorithm makes two passes over the boundaries and a final pass over the entire board. Each cell is visited by the DFS at most once because it immediately changes "O" to "T", preventing duplicate work.

• Space complexity: O(M * N)

• Reason: We eliminated the massive visited set and component lists from the brute-force approach, saving space. However, in the worst case (a board entirely filled with 'O's), the recursion stack for the DFS will still grow to O(M * N).