LeetEye LeetEye
Medium Graph Traversal ~5 min

Surrounded Regions

graphs surrounded-regions

Problem

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.

Examples

Example 1
Input: board = [["X","X","X","X"],
Output: [["X","X","X","X"],
'O' at (3,1) is not surrounded (touches edge).
Key Insight

Reverse thinking: mark 'O's connected to boundary as "safe," then flip everything else.

Reverse: DFS from boundary 'O's to mark safe. Then flip all remaining 'O' to 'X'. Restore safe back to 'O'.

How to Approach This Problem

Pattern Recognition: When you see keywords like surrounded regions graphs, think Graph Traversal.

Step-by-Step Reasoning

1 An 'O' is surrounded if:
Answer: It's not connected to any boundary 'O'
If connected to boundary (directly or through other 'O's), it reaches the edge = not surrounded.
2 Checking from each 'O' whether it reaches boundary:
Answer: Is inefficient — O(m×n) per 'O'
Each 'O' might need to traverse to check. Better to mark from boundary.
3 Instead of finding surrounded, we:
Answer: Find 'O's connected to boundary (safe)
Mark safe 'O's first, then flip the rest.
4 We start DFS/BFS from:
Answer: All boundary 'O's
Only 'O's on the four edges. Any 'O' connected to them is safe.

Solution

def solve(board: List[List[str]]) -> None:
    if not board:
        return
    
    rows, cols = len(board), len(board[0])
    
    def dfs(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return
        if board[r][c] != &#039;O':
            return
        
        board[r][c] = &#039;T'  # Mark as safe (temporary)
        dfs(r + 1, c)
        dfs(r - 1, c)
        dfs(r, c + 1)
        dfs(r, c - 1)
    
    # Mark all 'O's connected to boundary
    for r in range(rows):
        dfs(r, 0)
        dfs(r, cols - 1)
    for c in range(cols):
        dfs(0, c)
        dfs(rows - 1, c)
    
    # Flip remaining 'O' to 'X', restore 'T' to 'O'
    for r in range(rows):
        for c in range(cols):
            if board[r][c] == &#039;O':
                board[r][c] = &#039;X'
            elif board[r][c] == &#039;T':
                board[r][c] = &#039;O'

Complexity Analysis

Time O(m × n)
Space O(m × n)

Master This Pattern

Build intuition with interactive MCQs. Practice Graph Traversal problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye