Surrounded Regions

Difficulty: Medium Source: NeetCode

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.

An 'O' is not flipped if it is on the border or is connected to an 'O' on the border (directly or indirectly).

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"]]

Constraints:

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

Prerequisites

Before attempting this problem, you should be comfortable with:

• DFS / BFS on grids — flood fill from border cells
• Flood fill with markers — temporarily marking safe cells to distinguish them from surrounded ones

1. Brute Force (Check each O’s connectivity)

Intuition

For each 'O' cell, run DFS/BFS to check if it can reach the border. If it can, it’s safe; otherwise, flip it to 'X'. This is correct but redundant — many O’s share the same connected component and we’d recheck the same cells multiple times.

Algorithm

1. For each 'O' cell: run BFS to see if the border is reachable via connected O’s.
2. If border is not reachable, flip to 'X'.

Solution

from collections import deque

def solve(board: list[list[str]]) -> None:
    rows, cols = len(board), len(board[0])

    def reaches_border(start_r, start_c):
        queue = deque([(start_r, start_c)])
        visited = {(start_r, start_c)}
        while queue:
            r, c = queue.popleft()
            if r == 0 or r == rows-1 or c == 0 or c == cols-1:
                return True
            for dr, dc in [(1,0),(-1,0),(0,1),(0,-1)]:
                nr, nc = r+dr, 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))
                    queue.append((nr, nc))
        return False

    for r in range(rows):
        for c in range(cols):
            if board[r][c] == 'O' and not reaches_border(r, c):
                board[r][c] = 'X'


board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
solve(board)
for row in board:
    print(row)
# ['X','X','X','X'], ['X','X','X','X'], ['X','X','X','X'], ['X','O','X','X']

Complexity

• Time: O(M² * N²) — one BFS per O cell
• Space: O(M * N)

2. Border DFS / Mark-and-Flip

Intuition

Invert the thinking: instead of checking which O’s are surrounded, find which O’s are safe (connected to the border). Start DFS/BFS from every O on the border and mark all connected O’s as safe (e.g., temporarily replace with 'S'). After the traversal, anything still 'O' is surrounded — flip it to 'X'. Finally, restore 'S' back to 'O'.

Algorithm

1. For every 'O' on the border, run DFS marking connected O’s as 'S' (safe).
2. Scan the entire board: 'O' → 'X', 'S' → 'O', 'X' → 'X'.

Solution

def solve(board: list[list[str]]) -> None:
    rows, cols = len(board), len(board[0])

    def dfs(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols or board[r][c] != 'O':
            return
        board[r][c] = 'S'  # mark as safe
        dfs(r+1, c); dfs(r-1, c); dfs(r, c+1); dfs(r, c-1)

    # Mark all O's connected to any border O as safe
    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':
                dfs(r, c)

    # Flip: O → X (surrounded), S → O (safe), X stays X
    for r in range(rows):
        for c in range(cols):
            if board[r][c] == 'O':
                board[r][c] = 'X'
            elif board[r][c] == 'S':
                board[r][c] = 'O'


board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
solve(board)
for row in board:
    print(row)
# ['X','X','X','X'], ['X','X','X','X'], ['X','X','X','X'], ['X','O','X','X']

board2 = [["X"]]
solve(board2)
print(board2)  # [['X']]

Complexity

• Time: O(M * N) — each cell visited at most once during DFS
• Space: O(M * N) worst-case recursion stack

Common Pitfalls

Forgetting to process all four borders. The border O’s are on all four sides: top row, bottom row, left column, right column. It’s easy to handle corners twice — that’s fine, the DFS will return immediately since the cell is already marked 'S'.

Processing interior O’s directly. Only trigger DFS from border O’s. Interior O’s get marked transitively if they’re connected to a border O.

Choosing a unique safe marker. Use a character that doesn’t appear in the original board (like 'S' or 'T') to avoid confusion. Restore it in the final pass.