Surrounded Regions

• Difficulty: Medium
• Topics: Array, Depth-First Search, Breadth-First Search, Union Find, Matrix
• Link: https://leetcode.com/problems/surrounded-regions/

Problem Description

You are given an m x n matrix board containing letters 'X' and 'O', capture regions that are surrounded:

• Connect: A cell is connected to adjacent cells horizontally or vertically.
• Region: To form a region connect every 'O' cell.
• Surround: The region is surrounded with 'X' cells if you can connect the region with 'X' cells and none of the region cells are on the edge of the board.

To capture a surrounded region, replace all 'O's with 'X's in-place within the original board. You do not need to return anything.

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:

In the above diagram, the bottom region is not captured because it is on the edge of the board and cannot be surrounded.

Example 2:

Input: board = [[“X”]]

Output: [[“X”]]

Constraints:

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

Solution

1. Problem Deconstruction (500+ words)

Technical Reformulation: Given an m × n binary matrix where cells contain either ‘X’ (barrier) or ‘O’ (open region), identify all connected components of ‘O’ cells (using 4-directional adjacency) that are topologically isolated from the matrix boundary. For each such isolated component, perform an in-place mutation converting all ‘O’ → ‘X’. A connected component is considered boundary-adjacent if any of its cells satisfies i ∈ {0, m-1} ∨ j ∈ {0, n-1}.

Beginner-Friendly Version: Imagine a grid with two types of squares: walls (X) and open spaces (O). Groups of connected open spaces form “islands.” If an entire island is completely surrounded by walls and doesn’t touch the edge of the grid, we should fill it in with walls. But if any part of the island touches the grid’s edge, we leave it unchanged.

Mathematical Formulation: Let B be an m × n matrix over {X, O}. Define:

• Adjacency: (i,j) ∼ (k,l) iff |i-k| + |j-l| = 1
• Connected component C ⊆ {1…m} × {1…n} where ∀(i,j)∈C: B[i][j] = ‘O’ and the induced subgraph is connected
• Boundary: ∂B = {(i,j) : i∈{1,m} ∨ j∈{1,n}}
• Capture condition: C should be modified iff C ∩ ∂B = ∅

The transformation is: ∀(i,j) ∈ {C : C∩∂B=∅}, set B[i][j] = ‘X’

Constraint Analysis:

• m, n ≤ 200: Total cells ≤ 40,000, making O(mn) algorithms feasible (≈ 4×10⁴ operations)
• Grid size permits DFS/BFS without stack overflow concerns
• Minimum m,n = 1: Must handle degenerate 1×1 grids
• Binary alphabet {X,O}: No special character handling needed
• In-place modification: Cannot create full copy of board, but O(mn) auxiliary space acceptable
• Edge cases: Entire grid of X’s (no traversal needed), grid with all O’s (only boundary O’s survive), hollow rectangle pattern

2. Intuition Scaffolding

Real-World Metaphor: Imagine a flood filling a landscape with walls (X) and valleys (O). Water enters from the ocean (grid boundaries). Any valley connected to the ocean remains filled with water (O), while inland valleys without ocean access become dry land (X).

Gaming Analogy: Like territory capture in Go - groups with “liberty” (connection to edge) survive, while completely surrounded groups are captured. The board edge provides inherent liberty.

Mathematical Analogy: This is a connected component classification problem in graph theory, where we partition the ‘O’ cells into boundary-adjacent and interior components using a flood fill algorithm.

Common Pitfalls:

1. Attempting to check “surrounded” status per cell rather than per component
2. Modifying cells during traversal causing incorrect neighbor checks
3. Forgetting that diagonal connections don’t count
4. Missing edge cases where boundary O’s connect to interior regions
5. Using Union-Find without handling boundary connectivity efficiently
6. Assuming single-pass solutions exist (generally requires mark-and-replace)
7. Incorrectly treating corner cells as non-boundary

3. Approach Encyclopedia

Brute Force (Theoretical): For each ‘O’ cell, perform BFS/DFS to determine if it connects to boundary. If not, convert entire component.

# Pseudocode
for i in range(m):
    for j in range(n):
        if board[i][j] == 'O' and not connected_to_boundary(i, j):
            capture_component(i, j)

Complexity: O((mn)²) worst-case where each O triggers full grid traversal.

Boundary Propagation (Optimal):

def solve(board):
    if not board: return
    
    m, n = len(board), len(board[0])
    # Mark boundary-connected O's with temporary marker
    for i in range(m):
        for j in [0, n-1]:  # First and last columns
            if board[i][j] == 'O': mark_region(i, j)
    for j in range(n):
        for i in [0, m-1]:  # First and last rows  
            if board[i][j] == 'O': mark_region(i, j)
    
    # Convert: surviving O's → X, temporary → O
    for i in range(m):
        for j in range(n):
            if board[i][j] == 'O': board[i][j] = 'X'
            elif board[i][j] == 'T': board[i][j] = 'O'

def mark_region(i, j):
    queue = deque([(i, j)])
    board[i][j] = 'T'
    while queue:
        x, y = queue.popleft()
        for dx, dy in [(1,0), (-1,0), (0,1), (0,-1)]:
            nx, ny = x+dx, y+dy
            if 0 <= nx < m and 0 <= ny < n and board[nx][ny] == 'O':
                board[nx][ny] = 'T'
                queue.append((nx, ny))

Complexity Proof:

• Time: Each cell processed at most twice (marking + conversion) = O(2mn) ∈ O(mn)
• Space: Queue stores O(mn) in worst-case (all O’s connected to boundary)
• DFS alternative has O(mn) recursion depth, but BFS preferred for grid traversal

Visualization:

Initial:        After Marking:    Final:
X X X X         X X X X         X X X X
X O O X         X T T X         X X X X  
X X O X         X X T X         X X X X
X O X X         X T X X         X O X X

Boundary O's propagate inward via BFS, 
marking connected region with 'T'

4. Code Deep Dive

from collections import deque

class Solution:
    def solve(self, board: List[List[str]]) -> None:
        if not board or not board[0]:
            return
        
        m, n = len(board), len(board[0])
        
        # 1. Mark boundary-connected regions with temporary 'B'
        def dfs(i, j):
            if 0 <= i < m and 0 <= j < n and board[i][j] == 'O':
                board[i][j] = 'B'  # Boundary-connected
                # Recursively mark neighbors
                dfs(i+1, j); dfs(i-1, j); dfs(i, j+1); dfs(i, j-1)
        
        # Start DFS from boundary cells
        for i in range(m):
            dfs(i, 0); dfs(i, n-1)  # Left and right boundaries
        for j in range(n):
            dfs(0, j); dfs(m-1, j)  # Top and bottom boundaries
        
        # 2. Convert: interior O's → X, boundary markers → O  
        for i in range(m):
            for j in range(n):
                if board[i][j] == 'O':
                    board[i][j] = 'X'
                elif board[i][j] == 'B':
                    board[i][j] = 'O'

Edge Case Handling:

• Example 1: Bottom ‘O’ connects to boundary, so preserved via ‘B’ marker
• 1×1 grid [‘X’]: No O’s, no modification
• All O’s grid: Boundary O’s marked ‘B’, interior O’s become X’s
• Hollow rectangle: Only the outer shell survives

5. Complexity War Room

Hardware-Aware Analysis:

• 200×200 grid = 40,000 cells ≈ 320KB memory (8 bytes/cell estimate)
• Fits comfortably in L2/L3 cache (typical 256KB-8MB)
• BFS queue worst-case: 40,000 pointers ≈ 320KB, manageable
• DFS recursion depth: 40,000 might cause stack overflow, favoring iterative BFS

Industry Comparison Table:

Approach	Time	Space	Readability	Interview Viability
Brute Force	O((mn)²)	O(mn)	9/10	❌ Fails large cases
Boundary-DFS	O(mn)	O(mn)	8/10	✅ Clear logic
Boundary-BFS	O(mn)	O(mn)	7/10	✅ Robust for large m,n
Union-Find	O(mnα(mn))	O(mn)	6/10	⚠️ Over-engineered

6. Pro Mode Extras

Variants Section:

• 8-directional capture: Modify adjacency to include diagonals
• K-surrounded: Capture regions with ≥ K layers of X’s from boundary
• Dynamic updates: Support incremental X placements with efficient recomputation
• Multi-board: Process multiple boards with shared boundary conditions

Interview Cheat Sheet:

• First Mention: “This is a connected components problem with boundary conditions”
• Key Insight: “Work backwards from boundary O’s rather than checking interior regions”
• Complexity: Always state both time and space, justify auxiliary usage
• Testing: Verify edge cases: empty input, all X’s, all O’s, single row/column
• Optimization: Discuss BFS vs DFS trade-offs for specific constraints