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)