LeetCode Solutions Blog

Surrounded Regions

Number: 130

Difficulty: Medium

Paid? No

Problem Description

Given an m x n board containing letters 'X' and 'O', capture all regions surrounded by 'X'. A region is captured by flipping all 'O's into 'X's if the region is fully surrounded (i.e., none of its cells are on the board's border).

Key Insights

Regions connected to the border are not captured.
Use DFS/BFS from border 'O's to mark safe cells.
After marking, flip all remaining 'O's to 'X' and then revert the marked cells back to 'O'.

Space and Time Complexity

Time Complexity: O(m * n)
Space Complexity: O(m * n) in the worst case due to recursion stack or queue storage for DFS/BFS

Solution

The solution involves two main steps. First, traverse the board's borders and run a DFS or BFS from any encountered 'O', marking it (e.g., using '') to indicate that it should not be flipped. Next, go through each cell in the board: flip any remaining 'O' (i.e., not marked safe) to 'X' and change the temporary marker '' back to 'O'. This approach ensures only the regions completely surrounded by 'X' are captured.

Code Solutions

Python:

JavaScript:

C++:

Java:

def solve(board):
    if not board or not board[0]:
        return

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

    def dfs(r, c):
        # Return if out of bounds or current cell is not 'O'
        if r < 0 or c < 0 or r >= rows or c >= cols or board[r][c] != 'O':
            return
        # Mark the cell as safe
        board[r][c] = '*'
        # Explore four possible directions
        dfs(r + 1, c)
        dfs(r - 1, c)
        dfs(r, c + 1)
        dfs(r, c - 1)

    # Traverse the board borders
    for i in range(rows):
        if board[i][0] == 'O':
            dfs(i, 0)
        if board[i][cols - 1] == 'O':
            dfs(i, cols - 1)
    for j in range(cols):
        if board[0][j] == 'O':
            dfs(0, j)
        if board[rows - 1][j] == 'O':
            dfs(rows - 1, j)

    # Flip surrounded 'O's and restore safe cells
    for i in range(rows):
        for j in range(cols):
            if board[i][j] == 'O':
                board[i][j] = 'X'
            elif board[i][j] == '*':
                board[i][j] = 'O'