Introduction

In this blog post, we will explore how to solve the LeetCode problem "130" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

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. 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. 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'.

Explanation

Here's an efficient solution to the "Surrounded Regions" problem:

• Identify Uncaptured Regions: Start by identifying 'O's that are connected to the boundary of the board. These 'O's (and the region they belong to) cannot be captured. We can use Depth-First Search (DFS) or Breadth-First Search (BFS) to find these boundary-connected regions.
• Mark Uncaptured Regions: Mark these uncaptured 'O's temporarily with a different character (e.g., '#') to distinguish them from the 'O's that can be captured.

• Capture Remaining Regions: Iterate through the board again. Change all remaining 'O's (which are the surrounded ones) to 'X's. Then, change the temporary '#' characters back to 'O's.

• Runtime Complexity: O(m * n), where m is the number of rows and n is the number of columns in the board.

• Storage Complexity: O(m n) in the worst case (if the entire board is 'O's) due to the recursion stack of DFS. BFS would also be O(m\n) in the worst case.

Code

    class Solution:
    def solve(self, board: list[list[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        if not board:
            return

        rows, cols = len(board), len(board[0])

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

            board[row][col] = '#'  # Mark as temporarily uncaptured

            dfs(row + 1, col)
            dfs(row - 1, col)
            dfs(row, col + 1)
            dfs(row, col - 1)

        # Find 'O's connected to the boundary and mark them
        for i in range(rows):
            if board[i][0] == 'O':
                dfs(i, 0)
            if board[i][cols - 1] == 'O':
                dfs(i, cols - 1)

        for j in range(cols):
            if board[0][j] == 'O':
                dfs(0, j)
            if board[rows - 1][j] == 'O':
                dfs(rows - 1, j)

        # Capture remaining 'O's and revert temporary marks
        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'