We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Surrounded Regions

Difficulty: Medium

Problem Description

You are given an m x n matrix board containing letters 'X' and 'O', capture regions that are surrounded. A cell is connected to adjacent cells horizontally or vertically. To capture a surrounded region, replace all 'O's with 'X's in-place within the original board.

Key Insights

  • A region of 'O's is considered surrounded if it has no path to the edge of the board.
  • The 'O's that are connected to the edge of the board cannot be surrounded.
  • We can use Depth-First Search (DFS) or Breadth-First Search (BFS) to traverse and mark the 'O's that are not surrounded.

Space and Time Complexity

Time Complexity: O(m * n) - where m is the number of rows and n is the number of columns in the board because we may need to traverse every cell. Space Complexity: O(m * n) - for recursion stack in the DFS approach or O(min(m, n)) for BFS using queue.

Solution

To solve the problem, we can use a DFS approach. We will traverse the board and start from the 'O's located on the edges, marking them as safe (a temporary marker like 'E'). After marking, we will traverse the board again to convert all unmarked 'O's to 'X's, and finally change the marked 'E's back to 'O's. This ensures that only the 'O's that are fully surrounded by 'X's are converted.

Code Solutions

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

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

    def dfs(r, c):
        if r < 0 or c < 0 or r >= rows or c >= cols or board[r][c] != 'O':
            return
        board[r][c] = 'E'  # Mark the 'O's connected to the edge
        dfs(r + 1, c)
        dfs(r - 1, c)
        dfs(r, c + 1)
        dfs(r, c - 1)

    # Start from the first and last row
    for c in range(cols):
        dfs(0, c)
        dfs(rows - 1, c)

    # Start from the first and last column
    for r in range(rows):
        dfs(r, 0)
        dfs(r, cols - 1)

    # Convert the remaining 'O's to 'X's and 'E's back to 'O's
    for r in range(rows):
        for c in range(cols):
            if board[r][c] == 'O':
                board[r][c] = 'X'
            elif board[r][c] == 'E':
                board[r][c] = 'O'
← Back to All Questions