Surrounded Regions

Problem Statement

You are given a 2-D matrix board containing 'X' and 'O' characters.

If a continuous, four-directionally connected group of 'O's is surrounded by 'X's, it is considered to be surrounded.

Change all surrounded regions of 'O's to 'X's and do so in-place by modifying the input board.

Example 1:

Input: board = [
  ["X","X","X","X"],
  ["X","O","O","X"],
  ["X","O","O","X"],
  ["X","X","X","O"]
]

Output: [
  ["X","X","X","X"],
  ["X","X","X","X"],
  ["X","X","X","X"],
  ["X","X","X","O"]
]

Explanation: Note that regions that are on the border are not considered surrounded regions.

You should aim for a solution with O(m * n) time and O(m * n) space, where m is the number of rows and n is the number of columns in the matrix.

Recommended Time and Space Complexity

You should aim for a solution with O(m * n) time and O(m * n) space, where m is the number of rows and n is the number of columns in the matrix.

Hint 1

We observe that we need to capture the regions that are not connected to the O’s on the border of the matrix. This means there should be no path connecting the O’s on the border to any O’s in the region. Can you think of a way to check the region connected to these border O’s?

Hint 2

We can use the Depth First Search (DFS) algorithm. Instead of checking the region connected to the border O’s, we can reverse the approach and mark the regions that are reachable from the border O’s. How would you implement this?

Hint 3

We run the DFS from every 'O' on the border of the matrix, visiting the neighboring cells that are equal to 'O' recursively and marking them as '#' to avoid revisiting. After completing all the DFS calls, we traverse the matrix again and capture the cells where matrix[i][j] == 'O', and unmark the cells back to 'O' where matrix[i][j] == '#'

Solution

Depth First Search

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

    def capture(r, c):
        if (r < 0 or c < 0 or r == rows or
            c == cols or board[r][c] != "O"
        ):
            return
        board[r][c] = "T"
        capture(r + 1, c)
        capture(r - 1, c)
        capture(r, c + 1)
        capture(r, c - 1)

    for r in range(rows):
        if board[r][0] == "O":
            capture(r, 0)
        if board[r][cols - 1] == "O":
            capture(r, cols - 1)

    for c in range(cols):
        if board[0][c] == "O":
            capture(0, c)
        if board[rows - 1][c] == "O":
            capture(rows - 1, c)

    for r in range(rows):
        for c in range(cols):
            if board[r][c] == "O":
                board[r][c] = "X"
            elif board[r][c] == "T":
                board[r][c] = "O"

Time complexity: O(m * n) Space complexity: O(m * n)