Surrounded Regions medium

Problem Statement

Given an m x n matrix board containing 'X' and 'O' (uppercase), 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 edges (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 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 by 'X's. We'll use a marker character (e.g., 'T') to indicate these 'O's.

2. Flip the Remaining 'O's: Iterate through the entire board. Any 'O' that is not marked with 'T' is surrounded and should be flipped to 'X'.

3. Restore the Markers: Finally, replace all 'T's back to 'O's.

Explanation

The key idea is to use DFS/BFS to identify connected components of 'O's that reach the border. These components are not surrounded. Any 'O' that is not part of a border-connected component must be surrounded.

Using DFS/BFS is efficient because it avoids redundant checks. We only need to visit each cell once (or a small number of times depending on the implementation).

Code (C#)

using System;

public class Solution {
    public void Solve(char[][] board) {
        if (board == null || board.Length == 0) return;

        int m = board.Length;
        int n = board[0].Length;

        // Step 1: Identify border 'O's and mark connected components
        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: Flip remaining 'O's
        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';
            }
        }
    }

    private void DFS(char[][] board, int i, int j) {
        int m = board.Length;
        int n = board[0].Length;

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

        board[i][j] = 'T'; // Mark as visited
        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.
• Space Complexity: O(M * N) in the worst case, due to the recursive calls in the DFS. In the best case (all 'X's), the space complexity is O(1). The space used by the recursive calls can be reduced to O(max(M,N)) using iterative DFS or BFS.