Hide sidebar
leetcode/DSA courseSystem Design

Surrounded Regions

Surrounded Regions

GraphsDFS
MediumLeetCode #130
30 min

Problem Statement

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.

Example

Example 1:

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

Solution

The key insight is that any 'O' that is connected to the border of the board cannot be surrounded. All other 'O's must be surrounded by 'X's.

So, we can iterate along the four borders of the matrix. If we find an 'O', we perform a Depth-First Search (DFS) or Breadth-First Search (BFS) to find all connected 'O's and mark them with a temporary character (e.g., 'T'). After checking all borders, we iterate through the entire board one last time. Any remaining 'O's are flipped to 'X's, and any 'T's are flipped back to 'O's.

Algorithm Steps

  • Iterate through the top and bottom rows. If a cell is 'O', start a DFS to mark all connected 'O's as 'T'.
  • Iterate through the left and right columns. If a cell is 'O', do the same.
  • Iterate through the entire board:
  • If a cell is 'O', flip it to 'X'.
  • If a cell is 'T', flip it back to 'O'.

Surrounded Regions Visualization

Progress1 / 1
Ready to start.
X
X
X
X
X
O
O
X
X
X
O
X
X
O
X
X
Code Example

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])
        
        def dfs(r, c):
            if r < 0 or r >= m or c < 0 or c >= n or board[r][c] != 'O':
                return
            board[r][c] = 'T' # Temporary mark
            dfs(r + 1, c)
            dfs(r - 1, c)
            dfs(r, c + 1)
            dfs(r, c - 1)

        # 1. Capture unsurrounded regions (border 'O's)
        for r in range(m):
            for c in range(n):
                if (r == 0 or r == m - 1 or c == 0 or c == n - 1) and board[r][c] == 'O':
                    dfs(r, c)
        
        # 2. Flip surrounded 'O's to 'X' and restore 'T's to 'O'
        for r in range(m):
            for c in range(n):
                if board[r][c] == 'O':
                    board[r][c] = 'X'
                elif board[r][c] == 'T':
                    board[r][c] = 'O'