130.Surrounded_Regions(Medium).md

130. Surrounded Regions (Medium)

Date and Time: Aug 8, 2024, 22:49 (EST)

Link: https://leetcode.com/problems/surrounded-regions/

Question:

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: The region is surrounded with 'X' cells if you can connect the region with 'X' cells and none of the region cells are on the edge of the board.

A surrounded region is captured by replacing all 'O's with 'X's in the input matrix board.

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"]]

Explanation:

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"]]

Constraints:

• m == board.length

• n == board[i].length

• 1 <= m, n <= 200

• board[i][j] is 'X' or 'O'.

Walk-through:

1. We know the edges of the board are the only places that we can't capture surrounded regions. So we first loop over the first row, the last row, the first column, and the last column to check if there is any 'O' on these edges, if yes, we change these 'O' and their neighbors to a temporary 'T'.

We can find their neighbors by running dfs and save these positions (r, c) into a set().

2. Now, the rest of the 'O' on board can be sure to be captured. So we loop over the board to set 'O' to be 'X'.

3. We change back all the 'T' into 'O' from set().

Python Solution:

class Solution:
    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        visited, queue = set(), []
        tRegions = set()
        rows, cols = len(board), len(board[0])

        def bfs(r, c):
            queue.append((r, c))
            visited.add((r, c))
            while queue:
                row, col = queue.pop()
                board[row][col] = 'T'
                tRegions.add((row, col))
                directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]
                for dr, dc in directions:
                    r, c = row + dr, col + dc
                    if r in range(rows) and c in range(cols) and board[r][c] == 'O':
                        queue.append((r, c))
                        visited.add((r, c))

        # Checking each col's first and last element            
        for c in range(len(board[0])):
            if board[0][c] == 'O':
                bfs(0, c)
            if board[rows-1][c] == 'O':
                bfs(rows-1, c)

        # Checking each row's first and last element
        for r in range(rows):
            if board[r][0] == 'O':
                bfs(r, 0)
            if board[r][cols-1] == 'O':
                bfs(r, cols-1)

        # Capture all 'O' to 'X'
        for r in range(rows):
            for c in range(cols):
                if board[r][c] == 'O':
                    board[r][c] = 'X'
        
        # Change all 'T' back into 'O'
        for r, c in tRegions:
            board[r][c] = 'O'

Time Complexity: $O(m * n)$
Space Complexity: $O(m * n)$

Python Optimized Solution:

class Solution:
    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        rows, cols = len(board), len(board[0])
        tRegions = set()
        # Run dfs to find all neighbors
        def dfs(r, c):
            if (r not in range(rows) or c not in range(cols) or board[r][c] != 'O'):
                return
            tRegions.add((r, c))
            board[r][c] = 'T'
            dfs(r+1, c)
            dfs(r-1, c)
            dfs(r, c+1)
            dfs(r, c-1)

        # Find all edges
        for r in range(rows):
            for c in range(cols):
                if (r in [0, rows-1] or c in [0, cols-1] and board[r][c] == 'O'):
                    dfs(r, c)
        
        for r in range(rows):
            for c in range(cols):
                if board[r][c] == 'O':
                    board[r][c] = 'X'
        
        for r, c in tRegions:
            board[r][c] = 'O'