LeetCode 130: Surrounded Regions — Step-by-Step Visual Trace

#leetcode #python #algorithms

Medium — Depth-First Search | Matrix | Graph Traversal | Flood Fill

The Problem

Given a 2D board containing 'X' and 'O', capture all regions of 'O' that are completely surrounded by 'X' by flipping them to 'X'. Regions connected to the border cannot be captured.

Approach

Use DFS to mark all 'O' cells connected to the border as 'E' (escaped). Then traverse the entire board: flip remaining 'O' cells to 'X' (captured) and restore 'E' cells back to 'O' (escaped). This reverse approach identifies uncapturable regions first.

Time: O(m×n) · Space: O(m×n)

Code

class Solution:
    def solve(self, board: List[List[str]]) -> None:


        def dfs(row, col):
            if (
                row < 0
                or row >= len(board)
                or col < 0
                or col >= len(board[0])
                or board[row][col] != "O"
            ):
                return

            board[row][col] = "E"  # Mark as visited but not surrounded

            # Check adjacent cells
            dfs(row + 1, col)  # Check down
            dfs(row - 1, col)  # Check up
            dfs(row, col + 1)  # Check right
            dfs(row, col - 1)  # Check left

        # Traverse the boundary and mark connected 'O' cells as 'E'
        for row in range(len(board)):
            if board[row][0] == "O":
                dfs(row, 0)
            if board[row][len(board[0]) - 1] == "O":
                dfs(row, len(board[0]) - 1)

        for col in range(len(board[0])):
            if board[0][col] == "O":
                dfs(0, col)
            if board[len(board) - 1][col] == "O":
                dfs(len(board) - 1, col)

        # Mark internal 'O' cells as 'X' and restore 'E' cells to 'O'
        for row in range(len(board)):
            for col in range(len(board[0])):
                if board[row][col] == "O":
                    board[row][col] = "X"
                elif board[row][col] == "E":
                    board[row][col] = "O"