#130

Medium

auto_awesomeArray plus Depth-First Search

LeetCode Problem Workspace

Surrounded Regions

Transform the matrix in-place by marking regions surrounded by 'X' as 'X', while keeping border-adjacent 'O's intact.

array depth first search breadth first search union find matrix

Problem Statement

You are given a 2D matrix, board, filled with 'X' and 'O' characters. The task is to capture all regions of 'O' that are completely surrounded by 'X'. A region is captured if it is entirely enclosed by 'X', and all enclosed 'O's are replaced with 'X'. You must solve this problem in-place without returning anything.

To solve the problem, first identify the 'O' regions connected to the borders. These regions are not surrounded and must remain unchanged. For all other 'O's, replace them with 'X'. The solution can be implemented using DFS, BFS, or Union-Find to manage the traversal and transformation of the board.

Examples

Example 1

Input: board = [["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"]]

In the above diagram, the bottom region is not captured because it is on the edge of the board and cannot be surrounded.

Example 2

Input: board = [["X"]]

Output: [["X"]]

Example details omitted.

Constraints

m == board.length
n == board[i].length
1 <= m, n <= 200
board[i][j] is 'X' or 'O'.

Solution Approach

DFS Approach

In this solution, you start by identifying 'O's on the borders of the board, as these are not surrounded. Using DFS, mark all 'O's connected to these border 'O's as safe. Afterward, iterate through the board again, replacing all remaining 'O's with 'X', as they represent surrounded regions. This approach ensures that only the enclosed 'O's are captured.

BFS Approach

This approach uses Breadth-First Search (BFS) to explore all border-adjacent 'O's. For each border 'O', enqueue it for BFS and mark all connected 'O's as safe. Then, iterate through the board and replace all remaining 'O's with 'X'. This BFS solution also ensures that border-adjacent 'O's remain unchanged while capturing surrounded regions.

Union-Find Approach

With Union-Find, you treat the board as a collection of nodes, where each 'O' is a node. Use the Union-Find structure to connect 'O's on the borders, ensuring these are not surrounded. After processing all border 'O's, iterate through the board and union the inner 'O's. Those that are not connected to the border will be surrounded and can be replaced by 'X'.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of the DFS and BFS solutions is O(m n), where m and n are the dimensions of the board, since each cell is visited once. The space complexity for DFS is O(m n) due to the recursive stack, while BFS and Union-Find solutions may require extra space for auxiliary structures such as queues or parent arrays. Both approaches depend on the board's size for their space requirements.

What Interviewers Usually Probe

Do you understand how Depth-First Search can be applied to matrix traversal?
Can you optimize the solution to handle the largest board sizes efficiently?
Will you be able to explain how BFS or Union-Find compares to DFS in solving this problem?

Common Pitfalls or Variants

Common pitfalls

Failing to properly mark border 'O's as safe, leading to incorrect regions being transformed.
Not managing the traversal stack or queue efficiently, causing stack overflow or excessive memory use for large boards.
Overlooking edge cases like small boards (1x1), single row/column, or when there are no surrounded regions at all.

Follow-up variants

What if the board size is extremely large, say up to 1000x1000? How would you approach optimizing the solution?
Can you solve the problem using an iterative DFS approach to avoid recursion limits in Python?
How would you modify the solution if 'O's could be adjacent diagonally instead of only horizontally/vertically?

FAQ

How does Depth-First Search help in solving Surrounded Regions?

DFS helps by marking all 'O's connected to the border as safe, ensuring only enclosed regions are changed. This makes traversal efficient while ensuring the correctness of the result.

What happens if I don't handle border 'O's correctly?

If border 'O's are not correctly identified and marked, surrounded regions might not be transformed, leading to an incorrect solution.

What are the trade-offs between DFS, BFS, and Union-Find for this problem?

DFS is straightforward but risks stack overflow for large boards. BFS is iterative and avoids this risk. Union-Find offers a more complex but highly efficient solution for union and find operations.

How does the board's size impact the solution's efficiency?

The size of the board impacts both time and space complexity. Larger boards require more memory and processing time, especially for recursive DFS or BFS operations.

Can you explain the time complexity of the solution?

The time complexity of both DFS and BFS is O(m*n), where m and n are the dimensions of the board. Every cell is visited at most once, making this a linear traversal.

terminal

Solution

Solution 1: Depth-First Search (DFS)

We can start from the boundary of the matrix, taking each 'O' on the matrix boundary as a starting point, and perform depth-first search. All 'O's found in the search are replaced with '.'.

class Solution:
    def solve(self, board: List[List[str]]) -> None:
        def dfs(i: int, j: int):
            if not (0 <= i < m and 0 <= j < n and board[i][j] == "O"):
                return
            board[i][j] = "."
            for a, b in pairwise((-1, 0, 1, 0, -1)):
                dfs(i + a, j + b)

        m, n = len(board), len(board[0])
        for i in range(m):
            dfs(i, 0)
            dfs(i, n - 1)
        for j in range(n):
            dfs(0, j)
            dfs(m - 1, j)
        for i in range(m):
            for j in range(n):
                if board[i][j] == ".":
                    board[i][j] = "O"
                elif board[i][j] == "O":
                    board[i][j] = "X"

Solution 2: Union-Find Set

We can also use a union-find set, connecting each 'O' on the matrix boundary with a super node $m \times n$, and connecting each 'O' in the matrix with the 'O's above, below, left, and right of it.

class Solution:
    def solve(self, board: List[List[str]]) -> None:
        def dfs(i: int, j: int):
            if not (0 <= i < m and 0 <= j < n and board[i][j] == "O"):
                return
            board[i][j] = "."
            for a, b in pairwise((-1, 0, 1, 0, -1)):
                dfs(i + a, j + b)

        m, n = len(board), len(board[0])
        for i in range(m):
            dfs(i, 0)
            dfs(i, n - 1)
        for j in range(n):
            dfs(0, j)
            dfs(m - 1, j)
        for i in range(m):
            for j in range(n):
                if board[i][j] == ".":
                    board[i][j] = "O"
                elif board[i][j] == "O":
                    board[i][j] = "X"

Continue Practicing

#200 number of islands #695 max area of island #778 swim in rising water