[DSA][Graph] Surrounded Regions

Leetcode 130

You are given an m x n matrix board containing letters 'X' and 'O', capture regions that are surrounded:

• Connect: A cell is connected to adjacent cells horizontally or vertically.
• Region: To form a region connect every 'O' cell.
• Surround: A region is surrounded if none of the 'O' cells in that region are on the edge of the board. Such regions are completely enclosed by 'X' cells.

To capture a surrounded region, replace all 'O's with 'X's in-place within the original board. You do not need to return anything.

**[What can I ask?]

• Can the board be empty? NO - Does the board only contain ‘O’ and ‘X’? NO**

**[Key Idea]

• **Start BFS from the border cells and mark all connected ‘O’s with a temporary character. Then flip only the unmarked ‘O’s to ‘X’.

[Solution 1] Breadth First Search

class Solution:
    def solve(self, board: List[List[str]]) -> None:
        ROWS, COLS = len(board), len(board[0])
        noReverse = deque()

        direction = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        for i in range(ROWS):
            for j in range(COLS):
                if i == 0 or j == 0 or i == ROWS - 1 or j == COLS - 1:
                    if board[i][j] == "O":
                        board[i][j] = "-"
                        noReverse.append((i, j))

        def bfs():
            while noReverse:
                x, y = noReverse.popleft()
                for i in range(4):
                    dx = x + direction[i][0]
                    dy = y + direction[i][1]
                    if 0 <= dx < ROWS and 0 <= dy < COLS:
                        if board[dx][dy] == "O":
                            board[dx][dy] = "-"
                            noReverse.append((dx, dy))

        bfs()

        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"

This problem is similar in approach to the **Pacific Atlantic Water Flow* problem. In that problem, the goal was to find cells that are reachable from the outside (the oceans). In contrast, this problem requires identifying regions that are not reachable* from the border.

Directly checking for regions that cannot be reached from the outside can be complex. Instead, the approach can be reversed: first mark all regions that are reachable from the border, and then process the remaining cells.

A region that is not completely surrounded by ‘X’ has at least one ‘O’ connected to the border. Therefore, any ‘O’ connected to the border should not be flipped. To achieve this, BFS or DFS is performed starting from all border ‘O’s. All connected ‘O’s are expanded and temporarily marked with a special character (e.g., ‘-’) to distinguish them as safe regions.

After the traversal, any remaining ‘O’s are fully surrounded by ‘X’ and can be flipped to ‘X’. Finally, the temporary characters are reverted back to ‘O’, resulting in a board that satisfies the problem’s requirements.

⏱️ Time Complexity Each cell in the grid is checked once, and during BFS, each cell is visited at most once. Therefore, the overall time complexity is O(m × n).

🧠 Space Complexity A deque is used to store the coordinates of 'O' cells. In the worst case (for example, when all cells are 'O'), the space complexity is O(m × n).