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 (top, bottom, left, right).

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 should not be on the border.

Example 2:

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

Steps

1. Identify Border 'O's: Iterate through the top and bottom rows, and the leftmost and rightmost columns of the board. If an 'O' is found, mark it as a part of a safe region using Depth-First Search (DFS) or Breadth-First Search (BFS). We'll use DFS in this solution. We'll use a visited array to avoid revisiting cells.

2. Perform DFS: Starting from each border 'O', perform a depth-first search to mark all connected 'O's as safe. We'll use a visited array and a recursive helper function.

3. Flip Remaining 'O's: After the DFS, any 'O' that hasn't been marked as safe is surrounded and should be flipped to 'X'.

Explanation

The key idea is to identify 'O's that are connected to the border. These 'O's cannot be surrounded. We use DFS to find all connected components of 'O's starting from the border. Any 'O' not reached by the DFS is surrounded and can be safely flipped.

The visited array prevents infinite loops and ensures that we explore each connected component only once.

Code

function solve(board: string[][]): void {
    if (!board || board.length === 0) return;

    const rows = board.length;
    const cols = board[0].length;
    const visited = Array.from(Array(rows), () => Array(cols).fill(false));

    // Mark border 'O's as safe
    for (let i = 0; i < rows; i++) {
        dfs(board, i, 0, visited); //Left Border
        dfs(board, i, cols - 1, visited); //Right Border
    }
    for (let j = 0; j < cols; j++) {
        dfs(board, 0, j, visited); //Top Border
        dfs(board, rows - 1, j, visited); //Bottom Border
    }

    // Flip remaining 'O's to 'X'
    for (let i = 0; i < rows; i++) {
        for (let j = 0; j < cols; j++) {
            if (board[i][j] === 'O' && !visited[i][j]) {
                board[i][j] = 'X';
            }
        }
    }
};


function dfs(board: string[][], row: number, col: number, visited: boolean[][]): void {
    const rows = board.length;
    const cols = board[0].length;

    if (row < 0 || row >= rows || col < 0 || col >= cols || board[row][col] === 'X' || visited[row][col]) {
        return;
    }

    visited[row][col] = true;
    dfs(board, row + 1, col, visited);
    dfs(board, row - 1, col, visited);
    dfs(board, row, col + 1, visited);
    dfs(board, row, col - 1, visited);
}

Complexity

• Time Complexity: O(M*N), where M and N are the dimensions of the board. We visit each cell at most once.
• Space Complexity: O(MN) in the worst case, due to the visited array. The recursive calls in DFS also consume stack space, but this is proportional to the depth of the DFS which is at most MN in the worst-case scenario. Thus, overall space complexity is dominated by the visited array.