Surrounded Regions

Problem

Given an m x n matrix board containing 'X' and 'O', capture all regions that are 4-directionally surrounded by 'X'.

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

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: Notice that an 'O' should not be flipped if:
- It is on the border, or
- It is adjacent to an 'O' that should not be flipped.
The bottom 'O' is on the border, so it is not flipped.

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

Solution

Approach: DFS from Border to Mark Safe Regions

The key insight is that any ‘O’ connected to the border cannot be captured. We mark these safe regions first, then flip all remaining ‘O’s.

Implementation

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

        m, n = len(board), len(board[0])

        def dfs(r, c):
            # Check bounds and if it's not 'O'
            if (r < 0 or r >= m or c < 0 or c >= n or
                board[r][c] != 'O'):
                return

            # Mark as safe (temporary marker)
            board[r][c] = 'S'

            # Mark all connected 'O's as safe
            dfs(r + 1, c)
            dfs(r - 1, c)
            dfs(r, c + 1)
            dfs(r, c - 1)

        # Mark all border-connected 'O's as safe
        # Check first and last rows
        for j in range(n):
            if board[0][j] == 'O':
                dfs(0, j)
            if board[m-1][j] == 'O':
                dfs(m-1, j)

        # Check first and last columns
        for i in range(m):
            if board[i][0] == 'O':
                dfs(i, 0)
            if board[i][n-1] == 'O':
                dfs(i, n-1)

        # Flip surrounded 'O's to 'X' and restore safe 'S's to 'O'
        for i in range(m):
            for j in range(n):
                if board[i][j] == 'O':
                    board[i][j] = 'X'
                elif board[i][j] == 'S':
                    board[i][j] = 'O'

Approach 2: BFS from Border

from collections import deque

class Solution:
    def solve(self, board: List[List[str]]) -> None:
        if not board:
            return

        m, n = len(board), len(board[0])

        def bfs(r, c):
            queue = deque([(r, c)])
            board[r][c] = 'S'

            while queue:
                row, col = queue.popleft()
                directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

                for dr, dc in directions:
                    nr, nc = row + dr, col + dc
                    if (0 <= nr < m and 0 <= nc < n and
                        board[nr][nc] == 'O'):
                        board[nr][nc] = 'S'
                        queue.append((nr, nc))

        # Mark border-connected regions as safe
        for j in range(n):
            if board[0][j] == 'O':
                bfs(0, j)
            if board[m-1][j] == 'O':
                bfs(m-1, j)

        for i in range(m):
            if board[i][0] == 'O':
                bfs(i, 0)
            if board[i][n-1] == 'O':
                bfs(i, n-1)

        # Final pass to flip
        for i in range(m):
            for j in range(n):
                if board[i][j] == 'O':
                    board[i][j] = 'X'
                elif board[i][j] == 'S':
                    board[i][j] = 'O'

Complexity Analysis

Time Complexity: O(m * n), where m and n are board dimensions. We visit each cell at most twice.
Space Complexity: O(m * n) in worst case for recursion stack or queue.

Key Insights

Border Protection: Any ‘O’ on the border or connected to a border ‘O’ cannot be captured.
Reverse Marking: Instead of finding captured regions, we find non-captured regions first (border-connected), then flip everything else.
Three-Pass Algorithm:
- Pass 1: Mark safe regions from borders
- Pass 2: Flip remaining ‘O’s to ‘X’
- Pass 3: Restore safe regions back to ‘O’
Temporary Marker: Using ‘S’ as a temporary marker distinguishes safe ‘O’s from to-be-captured ‘O’s.
In-Place Modification: The problem requires in-place modification, which our solution achieves by using the board itself for marking.