Problem Description

You have a 2D board (matrix) filled with letters 'X' and 'O'. Your task is to find all regions of 'O's that are completely surrounded by 'X's and convert them to 'X's.

A region is formed by connecting 'O' cells that are adjacent to each other horizontally or vertically (not diagonally). A region is considered "surrounded" if all paths from any 'O' in that region to the edge of the board are blocked by 'X's. In other words, if a region of 'O's doesn't touch the boundary of the board, it's surrounded.

The key insight is that any 'O' that is on the edge of the board, or is connected to an 'O' on the edge, cannot be surrounded and should remain as 'O'. All other 'O's should be converted to 'X'.

The solution uses a clever approach:

1. Start from all 'O's on the boundary of the board
2. Use DFS to mark all 'O's connected to the boundary (these cannot be surrounded) by temporarily changing them to '.'
3. After marking all non-surrounded 'O's, traverse the entire board:
   • Change all '.' back to 'O' (these were connected to the boundary)
   • Change all remaining 'O' to 'X' (these were surrounded)

The modification happens in-place, meaning you modify the original board directly without creating a new one.

For example, if you have a board where some 'O's form an island completely enclosed by 'X's, those 'O's would be converted to 'X'. But if even one 'O' in that group touches the edge, the entire connected group remains as 'O'.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: The problem involves a 2D board where we need to explore connected regions of 'O's. Each cell can be considered a node, and adjacent cells (horizontally or vertically) form edges. We're looking for connected components of 'O's.

Is it a tree?

• No: The structure is not a tree. It's a 2D grid where cells can form cycles (e.g., four 'O's forming a square would create a cycle), and there's no hierarchical parent-child relationship.

Is the problem related to directed acyclic graphs?

• No: The grid connections are undirected (if cell A is adjacent to cell B, then B is also adjacent to A), and cycles can exist.

Is the problem related to shortest paths?

• No: We're not looking for the shortest path between points. We need to identify and mark connected regions.

Does the problem involve connectivity?

• Yes: The core of the problem is about connectivity - finding which 'O's are connected to the boundary and which are completely surrounded.

Does the problem have small constraints?

• Yes: While the board can be reasonably sized (m x n matrix), we can efficiently explore it with DFS since we're only visiting each cell once.

DFS/backtracking?

• Yes: DFS is perfect for exploring connected components. We start from boundary 'O's and recursively explore all connected 'O's to mark them as "safe" from capture.

Conclusion: The flowchart leads us to use DFS (Depth-First Search) for solving this connectivity problem, which aligns perfectly with the solution approach of starting from boundary cells and exploring all connected regions.

Intuition

The key insight comes from thinking about the problem in reverse. Instead of trying to identify which 'O' regions are surrounded, we identify which 'O' regions are NOT surrounded.

Any 'O' that cannot be surrounded must have at least one path to the boundary of the board. This means if we start from the boundary and explore all connected 'O's, we'll find all the 'O's that cannot be captured. Everything else must be surrounded.

Think of it like water flowing from the edges of the board - any 'O' that the water can reach from the boundary cannot be surrounded. The 'O's that remain dry are the ones completely enclosed by 'X's.

This reverse thinking simplifies the problem significantly:

1. Instead of checking every 'O' region to see if it's surrounded (which would be complex), we only need to start from the boundary 'O's
2. We use DFS to "mark" all 'O's connected to the boundary (temporarily changing them to '.' to distinguish them)
3. After marking, we know that:
   • Any '.' was connected to the boundary → change back to 'O'
   • Any remaining 'O' was not connected to the boundary → must be surrounded → change to 'X'

The beauty of this approach is that we only need to traverse the board twice - once for the DFS marking from boundaries, and once for the final conversion. We avoid the complexity of trying to determine if each region is surrounded by checking all possible escape routes.

Solution Approach

The implementation uses Depth-First Search (DFS) to mark all 'O's that are connected to the boundary. Here's how the solution works step by step:

1. DFS Helper Function

The dfs function explores all connected 'O' cells starting from position (i, j):

• First checks if the current position is within bounds and contains an 'O'
• If valid, marks the cell with '.' (a temporary marker)
• Recursively explores all 4 adjacent cells (up, down, left, right)

The pairwise((-1, 0, 1, 0, -1)) creates pairs: (-1, 0), (0, 1), (1, 0), (0, -1) representing the four directions.

2. Mark Boundary-Connected 'O's

Starting from all boundary cells:

• Left and right columns: For each row i, call dfs(i, 0) and dfs(i, n-1)
• Top and bottom rows: For each column j, call dfs(0, j) and dfs(m-1, j)

This ensures we explore all 'O's connected to any boundary cell, marking them with '.'.

3. Final Conversion

Traverse the entire board one more time:

• If a cell contains '.', it was connected to the boundary → change it back to 'O'
• If a cell still contains 'O', it was never reached from the boundary → it's surrounded → change it to 'X'
• 'X' cells remain unchanged

Time and Space Complexity:

• Time: O(m × n) where m and n are the dimensions of the board. We visit each cell at most twice.
• Space: O(m × n) in the worst case for the recursion stack (if all cells are 'O' and connected).

The algorithm modifies the board in-place, using the board itself as a visited marker (by temporarily changing 'O' to '.'), which eliminates the need for a separate visited array.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Initial Board:

X X X X
X O O X
X X O X
X O X X

Step 1: Check boundary cells and mark connected 'O's

Starting from the boundaries:

• Top row (row 0): All 'X', nothing to mark
• Bottom row (row 3): Found 'O' at position (3,1)
• Left column (column 0): All 'X', nothing to mark
• Right column (column 3): All 'X', nothing to mark

When we find the 'O' at (3,1), we start DFS:

• Mark (3,1) as '.'
• Check its 4 neighbors:
  • Up (2,1): It's 'X', stop
  • Down: Out of bounds, stop
  • Left (3,0): It's 'X', stop
  • Right (3,2): It's 'X', stop

Board after marking boundary-connected 'O's:

X X X X
X O O X
X X O X
X . X X

The 'O' at (3,1) is now marked as '.' because it touches the boundary. The 'O's at positions (1,1), (1,2), and (2,2) remain as 'O' because they're not connected to any boundary.

Step 2: Final conversion

Traverse the entire board:

• Position (0,0): 'X' → remains 'X'
• Position (0,1): 'X' → remains 'X'
• ...continuing for all 'X' cells...
• Position (1,1): 'O' → not connected to boundary → change to 'X'
• Position (1,2): 'O' → not connected to boundary → change to 'X'
• Position (2,2): 'O' → not connected to boundary → change to 'X'
• Position (3,1): '.' → was connected to boundary → change back to 'O'

Final Board:

X X X X
X X X X
X X X X
X O X X

The three 'O's that formed an island in the middle were surrounded and converted to 'X'. The 'O' at the bottom edge remained 'O' because it touched the boundary.

Solution Implementation

Time and Space Complexity

Time Complexity: O(m × n) where m is the number of rows and n is the number of columns in the board.

The algorithm performs the following operations:

• DFS calls from the border cells: The DFS is initiated from all border cells, which are 2m + 2n - 4 cells (approximately O(m + n)).
• Each cell in the board is visited at most once during the DFS traversal, as once a cell is marked as ".", it won't be revisited.
• The final nested loop to convert cells runs through all m × n cells exactly once.
• Therefore, the overall time complexity is O(m × n).

Space Complexity: O(m × n) where m is the number of rows and n is the number of columns in the board.

The space complexity comes from:

• The recursive DFS call stack: In the worst case, if all cells are connected "O"s starting from a border, the recursion depth could be O(m × n). This happens when the DFS traverses through all cells in a snake-like pattern.
• No additional data structures are used besides the implicit recursion stack.
• Therefore, the space complexity is O(m × n) due to the recursion stack depth.

Common Pitfalls

1. Stack Overflow with Deep Recursion

The recursive DFS implementation can cause a stack overflow when dealing with large boards where most cells are 'O' and connected. Python's default recursion limit (typically 1000) can be exceeded.

Solution: Convert the recursive DFS to an iterative approach using an explicit stack:

def mark_border_connected(row: int, col: int) -> None:
    stack = [(row, col)]
    while stack:
        r, c = stack.pop()
        if not (0 <= r < rows and 0 <= c < cols and board[r][c] == "O"):
            continue
        board[r][c] = "."
        for dx, dy in [(-1, 0), (0, 1), (1, 0), (0, -1)]:
            stack.append((r + dx, c + dy))

2. Forgetting to Check All Border Cells

A common mistake is only checking corners or missing some border cells, especially when the board has only one row or one column.

Solution: Ensure your border traversal covers all edge cases:

• For a 1×n or m×1 board, some cells are on multiple borders simultaneously
• The current implementation handles this correctly by checking all four borders separately

3. Using the Same Marker as Original Values

Using 'O' or 'X' as temporary markers during DFS can cause cells to be processed multiple times or skipped entirely.

Solution: Always use a distinct temporary marker (like '.' in the solution) that doesn't conflict with the original values.

4. Modifying Board During Iteration

Attempting to capture surrounded regions while simultaneously exploring from borders can lead to incorrect results.

Solution: Follow the two-phase approach:

1. First, mark all border-connected cells completely
2. Then, perform the final conversion in a separate pass

5. Incorrect Direction Vectors

Hardcoding direction vectors incorrectly (e.g., [(1, 0), (0, 1), (-1, 0), (0, -1)] in wrong order or with wrong values) won't cause obvious errors but might miss some connected cells.

Solution: Define directions clearly and consistently:

directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]  # up, right, down, left
# Or use named tuples for clarity
UP, RIGHT, DOWN, LEFT = (-1, 0), (0, 1), (1, 0), (0, -1)