130. Surrounded Regions

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

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.

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

Approach 1: Brute Force

Intuition

• DFS traversal from the edges
• Directions Array

Algorithm

1. Create a visited matrix initialized to false.
2. Traverse through the entire board.
3. If the cell is on edge & have value == 'O' call dfs function for it.
4. dfs recursive function
   1. Base case
      1. Out of bounds
      2. Cell value already X
      3. Visited == true
      4. return
   2. Set visited for the cell to be true
   3. Recurse case
      1. Loop through the directions array
      2. Create new row & new col
      3. Call dfs on new row & col
5. Traverse through the entire board
   1. If the cell is not visited, change it to X

Code

class Solution {
public:
    const vector<pair<int, int>> directions = {
        {-1, 0},
        {1, 0},
        {0, -1},
        {0, 1},
    };

    void dfs(int row, int col, vector<vector<bool>>& visited, 
        vector<vector<char>>& board, int rows, int cols) {
            if (row < 0 || row >= rows ||
                col < 0 || col >= cols ||
                board[row][col] == 'X' ||
                visited[row][col] == true) return;
            
            visited[row][col] = true;

            for (auto direction : directions) {
                int nr = row + direction.first;
                int nc = col + direction.second;

                dfs(nr, nc, visited, board, rows, cols);
            }
        }
    void solve(vector<vector<char>>& board) {
        int rows = board.size(), cols = board[0].size();
        vector<vector<bool>> visited(rows, vector<bool>(cols,false));

        for (int i = 0 ; i < rows; i++) {
            for (int j = 0 ; j < cols ; j++) {
                if ((i == 0 || i == rows - 1
                    || j == 0 || j == cols - 1)
                    && board[i][j] == 'O') {
                        dfs(i, j, visited, board, rows, cols);
                    }
            }
        }

        for (int i = 0 ; i < rows ; i++) {
            for (int j = 0 ; j < cols ; j++) {
                if (!visited[i][j]) {
                    board[i][j] = 'X';
                }
            }
        }
    }
};

Complexity Analysis

• Time Complexity: $O(n\ast m)$
• Space Complexity: $O(n\ast m)$

Approach 2: Optimal

Intuition

• Traversal from the edges
• Directions array

Algorithm

1. Traverse through the entire board.
2. If the cell is on edge & have value == 'O' call dfs function for it.
3. dfs recursive function
   1. Base case
      1. Out of bounds
      2. Cell value already X
      3. Cell value already #
      4. return
   2. Set cell value to #
   3. Recurse case
      1. Loop through the directions array
      2. Create new row & new col
      3. Call dfs on new row & col
4. Traverse through the entire board
   1. If the cell is '#' change it to O
   2. Else replace cell with X

Code

class Solution {
public:
    const vector<pair<int, int>> directions = {
        {-1, 0},
        {1, 0},
        {0, -1},
        {0, 1},
    };

    void dfs(int row, int col,  
        vector<vector<char>>& board, int rows, int cols) {
            if (row < 0 || row >= rows ||
                col < 0 || col >= cols ||
                board[row][col] == 'X' ||
                board[row][col] == '#' ) return;
            
            board[row][col] = '#';

            for (auto direction : directions) {
                int nr = row + direction.first;
                int nc = col + direction.second;

                dfs(nr, nc, board, rows, cols);
            }
        }
    void solve(vector<vector<char>>& board) {
        int rows = board.size(), cols = board[0].size();

        for (int i = 0 ; i < rows; i++) {
            for (int j = 0 ; j < cols ; j++) {
                if ((i == 0 || i == rows - 1
                    || j == 0 || j == cols - 1)
                    && board[i][j] == 'O') {
                        dfs(i, j, board, rows, cols);
                    }
            }
        }

        for (int i = 0 ; i < rows ; i++) {
            for (int j = 0 ; j < cols ; j++) {
                if (board[i][j] == '#') {
                    board[i][j] = 'O';
                } else {
                    board[i][j] = 'X';
                }
            }
        }
    }
};

Complexity Analysis

• Time Complexity: $O(n\ast m)$
• Space Complexity: $O(1)$ not considering stack space
  • $O(n\ast m)$ considering stack space