Surrounded Regions medium

Problem Statement

Given an m x n matrix board containing 'X' and 'O' (capital letters), capture all regions surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region.

A region is surrounded by 'X' if there are 'X's on its four sides.

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: Surrounded regions shouldn't be on the border.

Example 2

Input: board = [["X"]] Output: [["X"]]

Steps

1. Identify Border 'O's: Iterate through the border of the board. If you find an 'O', perform a Depth-First Search (DFS) or Breadth-First Search (BFS) starting from that 'O'. This DFS/BFS will mark all connected 'O's that are not surrounded. We'll use a marker character (e.g., 'T') to mark these 'O's.

2. Capture Surrounded Regions: Iterate through the entire board. Any 'O' that wasn't marked with 'T' in the previous step is surrounded and should be changed to 'X'.

3. Restore Marked 'O's: Change all 'T's back to 'O's.

Explanation

The key insight is that only 'O's that are not connected to the border are surrounded. By starting a search from the border, we can identify all 'O's that have a path to the edge and, therefore, are not surrounded. Those that remain unmarked are the ones to be captured.

Code (C++)

#include <vector>

using namespace std;

void solve(vector<vector<char>>& board) {
    if (board.empty() || board[0].empty()) return;

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

    // Step 1: Mark border 'O's
    for (int i = 0; i < m; ++i) {
        if (board[i][0] == 'O') dfs(board, i, 0);
        if (board[i][n - 1] == 'O') dfs(board, i, n - 1);
    }
    for (int j = 0; j < n; ++j) {
        if (board[0][j] == 'O') dfs(board, 0, j);
        if (board[m - 1][j] == 'O') dfs(board, m - 1, j);
    }

    // Step 2: Capture surrounded regions
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (board[i][j] == 'O') board[i][j] = 'X';
            else if (board[i][j] == 'T') board[i][j] = 'O'; //Step 3
        }
    }
}

void dfs(vector<vector<char>>& board, int i, int j) {
    int m = board.size();
    int n = board[0].size();

    if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] != 'O') return;

    board[i][j] = 'T'; //Mark as visited and not surrounded
    dfs(board, i + 1, j);
    dfs(board, i - 1, j);
    dfs(board, i, j + 1);
    dfs(board, i, j - 1);
}

Complexity

• Time Complexity: O(M*N), where M and N are the dimensions of the board. We visit each cell at most once during the DFS and the final board traversal.

• Space Complexity: O(M*N) in the worst case. This is due to the recursive call stack of the DFS. In the best case (few or no 'O's on the border), the space complexity will be much lower. Note that this space usage is also related to the depth of recursion; it's possible to reduce the space complexity to O(M+N) using BFS (iterative solution) instead of DFS.