Surrounded Regions 🧠

LeetCode Link: Surrounded Regions

Difficulty: Medium

Problem Explanation 📝

Problem: LeetCode 130 - Surrounded Regions

Description: Given an m x n matrix board containing 'X' and 'O', capture all regions that are surrounded by 'X'. A region is captured by flipping all 'O's into 'X's in that surrounded region.

Intuition: To capture the surrounded regions, we need to identify the regions that are connected to the borders of the matrix. The regions that are not connected to the borders are the ones that need to be captured. We can use a depth-first search (DFS) approach to identify and mark the regions that are connected to the borders, and then iterate through the matrix to capture the remaining regions.

Approach:

1. Traverse the borders of the matrix and perform a DFS to mark the regions that are connected to the borders:

• If a cell is 'O', perform a DFS to mark all its neighboring 'O' cells as connected to the border.

2. Iterate through the entire matrix:

• If a cell is 'O' and not marked as connected to the border, capture it by changing it to 'X'.
• If a cell is marked as connected to the border, restore it to 'O'.

3. The regions that are not marked as connected to the border are the captured regions.

⌛ Time Complexity: The time complexity is O(m * n), where m is the number of rows and n is the number of columns in the matrix. We visit each cell once.

💾 Space Complexity: The space complexity is O(m * n), where m is the number of rows and n is the number of columns in the matrix. This is the space used for the recursion stack during the DFS traversal.

Solutions 💡

Cpp 💻

class Solution {
  public:
    void solve(vector<vector<char>> &board) {
        if (board.empty()) {
            return;
        }

        int m = board.size();
        int n = board[0].size();

        // Traverse the top and bottom borders
        for (int col = 0; col < n; ++col) {
            dfs(board, 0, col);
            dfs(board, m - 1, col);
        }

        // Traverse the left and right borders
        for (int row = 0; row < m; ++row) {
            dfs(board, row, 0);
            dfs(board, row, n - 1);
        }

        // Capture the remaining regions
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (board[i][j] == 'O') {
                    board[i][j] = 'X';  // Capture the region
                } else if (board[i][j] == '#') {
                    board[i][j] = 'O';  // Restore the region
                }
            }
        }
    }

  private:
    void dfs(vector<vector<char>> &board, int row, int col) {
        int m = board.size();
        int n = board[0].size();

        if (row < 0 || row >= m || col < 0 || col >= n || board[row][col] != 'O') {
            return;
        }

        board[row][col] = '#';  // Mark the cell as connected to the border
        dfs(board, row - 1, col);  // Up
        dfs(board, row + 1, col);  // Down
        dfs(board, row, col - 1);  // Left
        dfs(board, row, col + 1);  // Right
    }
};

Python 🐍

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

        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"