Surrounded Regions (LeetCode 130)

The problem

You get a grid of 'X' and 'O'. A region of 'O' cells (connected up, down, left, right) is captured if it is completely surrounded by 'X', which means none of its cells touches the edge of the grid. Flip every captured 'O' to 'X' and leave the rest alone.

Input:            Output:
X X X X           X X X X
X O O X           X X X X
X X O X           X X X X
X O X X           X O X X

The three Os in the middle form a region with no cell on the border, so they’re captured. The O in the bottom row sits on the edge, so it survives.

How to think about it

Start with brute force. For every 'O', flood-fill its region and check whether any cell in it touches the border. If not, flip the region. Done carelessly, you re-explore the same region from each of its cells, which is O((R·C)²). Even done carefully, you need two kinds of marks (seen-and-safe, seen-and-captured).

The key insight: flip the question. Instead of asking “is this region surrounded?”, ask ”which Os can reach the border?”. Those are exactly the survivors. Every other O is captured. And finding cells that can reach the border is easy: start a flood fill from every 'O' on the border and mark everything it reaches. A region that touches the edge gets fully marked from that edge cell. A surrounded region is never reached.

Two passes and you’re done. First pass: flood from the four borders, turning every reachable 'O' into a temporary '#' (safe). Second pass: scan the grid. '#' goes back to 'O', and anything else, including the unmarked 'O's, becomes 'X'.

Which pattern is this? Graph flood fill, started from the boundary. The tell is “regions that are or aren’t connected to the edge”. Pacific Atlantic Water Flow uses the same reverse trick.

Approach

1. If the board is empty, return it.
2. Flood-fill from every cell in the first and last column, and the first and last row. dfs stops at the edge of the grid or at anything that isn’t 'O', and marks 'O' as '#'.
3. Scan every cell: '#' becomes 'O', everything else becomes 'X'.

Solution

def solve_surrounded(board):
    if not board: return board
    R, C = len(board), len(board[0])
    def dfs(r, c):
        if r < 0 or c < 0 or r >= R or c >= C or board[r][c] != 'O': return
        board[r][c] = '#'                              # reachable from the border: safe
        dfs(r+1, c); dfs(r-1, c); dfs(r, c+1); dfs(r, c-1)
    for r in range(R):
        dfs(r, 0); dfs(r, C-1)                         # left and right borders
    for c in range(C):
        dfs(0, c); dfs(R-1, c)                         # top and bottom borders
    for r in range(R):
        for c in range(C):
            board[r][c] = 'O' if board[r][c] == '#' else 'X'   # safe stays, rest is captured
    return board
# solve_surrounded([["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]])
#   -> [["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]

Dry run

On the example board:

If an inner region connects to the edge, the fill follows it in. With a column of Os at (1,1), (2,1), (3,1) on a 4×3 board, the fill from (3,1) marks all three, and none are captured.

Complexity

• Time: O(R·C). Every cell is marked at most once by the border fills, and the final scan touches each cell once.
• Space: O(R·C) in the worst case for the recursion stack, if most of the board is one snaking O region. An explicit stack or BFS queue avoids Python’s recursion limit.

Edge cases and pitfalls

• Empty board is returned as is. A single row or column: every cell is on the border, so nothing is captured.
• All O stays all O: the border fill reaches every cell.
• Flipping during the fill. If you start flipping inner Os before every border fill has run, you may capture a region that a later border fill would have saved. Mark first, flip after.
• Diagonals don’t connect. An O touching a border O only diagonally is still captured.

Related problems

• Number of Islands (LeetCode 200): the base flood fill, started from every cell.
• Pacific Atlantic Water Flow (LeetCode 417): two border flood fills, then intersect.
• Walls and Gates (LeetCode 286): start the search from many sources at once.