Solving Surrounded Regions in Python: Step-by-Step Guide

Solving Surrounded Regions in Python: Step-by-Step Guide

The "Surrounded Regions" problem is a classic graph traversal challenge that frequently appears in coding interviews and competitive programming. It tests your understanding of matrix traversal, depth-first search (DFS), breadth-first search (BFS), and the union-find data structure. In this tutorial, we will break down the problem, explore multiple solution strategies, and implement an efficient Python solution step by step.

What Is the Surrounded Regions Problem?

Given an m x n matrix board containing characters 'X' and 'O', the goal is to capture all regions that are fully surrounded by 'X' in all four directions (up, down, left, right). A region is considered "surrounded" if none of its 'O' cells lies on the border of the matrix. When a region is captured, all of its 'O' cells are flipped to 'X'.

Here is a visual 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

Notice that the 'O' at the bottom row remains unchanged because it touches the border, and therefore it is not surrounded. All other 'O' cells that are connected to it are also preserved.

Why This Problem Matters

This problem is more than an interview exercise. It models real-world scenarios such as:

• Flood fill algorithms used in image editing software like Photoshop.
• Game logic for board games like Go, where capturing surrounded stones is a core mechanic.
• Geographic information systems that determine enclosed regions on maps.
• Connected component analysis in computer vision and grid-based simulations.

Mastering this problem strengthens your ability to reason about grid connectivity, boundary conditions, and traversal algorithms — skills that transfer directly to many production systems.

Understanding the Core Insight

The naive approach would be to iterate over every 'O' in the matrix and check whether it is surrounded. However, this leads to redundant work and complex bookkeeping. A much cleaner insight is to flip the problem on its head:

Instead of finding surrounded regions, find the regions that are not surrounded. Any 'O' that is connected — directly or transitively — to a border 'O' cannot be captured. Once we mark all such "safe" cells, every remaining 'O' must be surrounded and can be flipped.

This transforms the problem into a graph traversal starting from the borders of the matrix.

Step-by-Step Algorithm

Here is the high-level plan:

• Iterate over every cell on the four borders of the matrix.
• Whenever we find an 'O' on the border, perform a DFS or BFS to mark all connected 'O' cells as safe using a temporary marker such as 'T'.
• After marking is complete, traverse the entire matrix.
• Convert every remaining 'O' to 'X' (these are the surrounded cells).
• Convert every 'T' back to 'O' (these are the safe cells).

Implementing the DFS Solution

Let us implement this approach using recursive DFS. We will define a helper function that marks border-connected cells, then apply the transformation logic.

from typing import List

def solve(board: List[List[str]]) -> None:
    """
    Do not return anything, modify board in-place instead.
    Captures all 'O' regions that are fully surrounded by 'X'.
    """
    if not board or not board[0]:
        return

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

    def dfs(r: int, c: int) -> None:
        # Base case: out of bounds or not an 'O'
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return
        if board[r][c] != 'O':
            return

        # Mark this cell as temporarily safe
        board[r][c] = 'T'

        # Explore all four directions
        dfs(r + 1, c)
        dfs(r - 1, c)
        dfs(r, c + 1)
        dfs(r, c - 1)

    # Step 1: Mark all border-connected 'O' cells
    for r in range(rows):
        for c in range(cols):
            # Only start DFS from border cells
            if (r == 0 or r == rows - 1 or c == 0 or c == cols - 1) and board[r][c] == 'O':
                dfs(r, c)

    # Step 2: Flip remaining 'O' to 'X', and restore 'T' 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'

This solution modifies the board in place and runs in O(m * n) time, where m is the number of rows and n is the number of columns. Each cell is visited at most a constant number of times. The space complexity is O(m * n) in the worst case due to the recursion stack, which could grow as large as the number of cells if the entire board is filled with 'O'.

Testing the Implementation

Let us verify the solution with a concrete test case:

if __name__ == "__main__":
    board = [
        ['X', 'X', 'X', 'X'],
        ['X', 'O', 'O', 'X'],
        ['X', 'X', 'O', 'X'],
        ['X', 'O', 'X', 'X'],
    ]

    solve(board)

    for row in board:
        print(' '.join(row))

Running this code produces the expected output:

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

The bottom-row 'O' survives because it touches the border, while the interior region is captured.

Implementing the BFS Alternative

Recursive DFS is elegant but can hit Python's recursion limit on very large boards. An iterative BFS approach avoids this issue entirely by using an explicit queue. Here is the equivalent implementation:

from collections import deque
from typing import List

def solve_bfs(board: List[List[str]]) -> None:
    if not board or not board[0]:
        return

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

    # Collect all border 'O' cells into the queue
    for r in range(rows):
        for c in range(cols):
            if (r == 0 or r == rows - 1 or c == 0 or c == cols - 1) and board[r][c] == 'O':
                board[r][c] = 'T'
                queue.append((r, c))

    # BFS to mark all connected 'O' cells as safe
    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    while queue:
        r, c = queue.popleft()
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] == 'O':
                board[nr][nc] = 'T'
                queue.append((nr, nc))

    # Final transformation pass
    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'

The BFS version has the same time complexity of O(m * n) but avoids recursion depth issues. For production code or platforms with strict memory limits, this is often the safer choice.

Union-Find Approach

For those interested in an alternative data structure, the union-find (disjoint set) approach offers another perspective. The idea is to create a virtual node representing the "border" and union every border 'O' with this virtual node. Then, for every interior 'O', union it with adjacent 'O' cells. Finally, any 'O' that shares a root with the virtual node is safe.

from typing import List

class UnionFind:
    def __init__(self, n: int):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x: int) -> int:
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x: int, y: int) -> None:
        px, py = self.find(x), self.find(y)
        if px == py:
            return
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1

def solve_union_find(board: List[List[str]]) -> None:
    if not board or not board[0]:
        return

    rows, cols = len(board), len(board[0])
    dummy = rows * cols  # virtual node for border
    uf = UnionFind(rows * cols + 1)

    def index(r: int, c: int) -> int:
        return r * cols + c

    for r in range(rows):
        for c in range(cols):
            if board[r][c] != 'O':
                continue
            # Connect border cells to the dummy node
            if r == 0 or r == rows - 1 or c == 0 or c == cols - 1:
                uf.union(index(r, c), dummy)
            # Connect to right and down neighbors
            if r + 1 < rows and board[r + 1][c] == 'O':
                uf.union(index(r, c), index(r + 1, c))
            if c + 1 < cols and board[r][c + 1] == 'O':
                uf.union(index(r, c), index(r, c + 1))

    for r in range(rows):
        for c in range(cols):
            if board[r][c] == 'O' and uf.find(index(r, c)) != uf.find(dummy):
                board[r][c] = 'X'

While union-find is slightly more complex to implement, it demonstrates how disjoint set structures can model connectivity problems elegantly. Its time complexity is approximately O(m * n * α(m * n)), where α is the inverse Ackermann function, which is effectively constant for all practical inputs.

Best Practices

When implementing this solution in real projects or interviews, keep the following best practices in mind:

• Always handle edge cases first. Check for empty boards or boards with a single row or column before proceeding with the main logic.
• Prefer BFS for large inputs. Python's default recursion limit is around 1000, which DFS can easily exceed on large matrices. Use sys.setrecursionlimit() only as a last resort.
• Modify in place when possible. The problem typically expects in-place modification. Avoid allocating a full copy of the board unless memory constraints allow it.
• Use clear temporary markers. Choosing a marker like 'T' that cannot appear in the original input prevents subtle bugs during the transformation phase.
• Write unit tests. Test with all-'X' boards, all-'O' boards, single-cell boards, and boards where every 'O' touches the border.
• Document your helper functions. Clearly state what the DFS or BFS function does, what it modifies, and what its preconditions are.

Common Pitfalls to Avoid

Even experienced developers can stumble on this problem. Watch out for these mistakes:

• Forgetting diagonal connectivity. The problem specifies four-directional connectivity. Do not accidentally include diagonal neighbors.
• Starting DFS from interior cells. Only border 'O' cells should initiate traversal. Starting from interior cells defeats the purpose of the algorithm.
• Not restoring the temporary marker. If you forget to convert 'T' back to 'O', your output will contain invalid characters.
• Mutating the board while iterating incorrectly. Ensure your final pass handles both transformations in a single loop or two clearly separated loops to avoid race conditions.

Conclusion

The Surrounded Regions problem is a powerful exercise in graph traversal and boundary reasoning. By reframing the question from "find surrounded regions" to "find safe regions connected to the border," we unlock a clean and efficient solution that works with DFS, BFS, or union-find. The key takeaway is that recognizing the structural insight — that border connectivity determines safety — transforms a seemingly complex problem into a straightforward traversal task. Whether you are preparing for interviews or building grid-based applications, mastering this pattern will serve you well across a wide range of connected-component problems.