Surrounded Regions

1. Step 1: Initialize Solution.solve

   Replace the empty starter with the first real state owned by Solution.solve. A small, named state is easier to verify than a complete algorithm. Establish it before adding the branch or loop that changes it.

2. Step 2: Assemble the primary transition

   Extend the initialized state with the next contiguous part of the popular solution. The transition explains how one input element or operation changes the state; boundaries are easier to reason about after this invariant is visible.

3. Step 3: Pass the Preserve Boundary Component case

   Complete the readable core algorithm for one representative Interview case. Separating boundary preservation from interior capture makes the invariant visible before the final flip.

4. Step 4: Harden the Captured Center boundary

   Repair the reviewed boundary and pass the complete submission contract. An O is uncapturable exactly when connected to a boundary O. BFS marks all and only those cells, so the final pass flips precisely enclosed regions and restores every protected cell.

• Diagonal contact with a boundary does not protect a region.
• trees and graphs

• LeetCode 130 — Surrounded Regions

• Visit Each Grid Component(opens in a new tab)

  Visit Each Grid Component isolates a cell is marked visited before being added to the frontier, so every active cell contributes to exactly one component. That focused state discipline is required when implementing surrounded regions as a complete Interview Problem.

BFS from every boundary O, marking reachable cells safe. Then flip remaining O to X and restore safe markers to O.

Why it works: An O is uncapturable exactly when connected to a boundary O. BFS marks all and only those cells, so the final pass flips precisely enclosed regions and restores every protected cell.

class Solution:
    def solve(self, board):
        """
        Checkpoint 1: initialize the state owned by this Interview contract.
        Checkpoint 2: assemble the primary transition without hiding the boundary.
        """
        if not board:
            return board
        rows, columns = len(board), len(board[0])
        def preserve(row, column):
            if not (0 <= row < rows and 0 <= column < columns):
                return
            if board[row][column] != 'O':
                return
            board[row][column] = 'S'
            for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                preserve(row + dr, column + dc)
        for row in range(rows):
            preserve(row, 0)
            preserve(row, columns - 1)
        for column in range(columns):
            preserve(0, column)
            preserve(rows - 1, column)
        for row in range(rows):
            for column in range(columns):
                board[row][column] = 'O' if board[row][column] == 'S' else 'X'
        return board

• Number of Islands(opens in a new tab)