FAANGPrep Sprint

Surrounded Regions

Capture regions that are fully surrounded by 'X'.

MediumSolve on LeetCode

Examples

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

Explain:

The 'O' at the bottom is connected to the border, so it's not surrounded. The center island is surrounded and flipped.

Problem Understanding

Given an m x n 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.

Key Insight: An 'O' is NOT surrounded if connects to an 'O' on the boundary.

Algorithm Strategy (Reverse Thinking)

Instead of searching for surrounded regions (hard), let's search for Unsurrounded regions (easy).

Border Check: Any 'O' on the border is safe. Any 'O' connected to a border 'O' is also safe.
Phase 1 (Mark Safe): Call DFS on every cell of the 4 borders. DFS returns at once unless the cell is an 'O', and marks every 'O' it reaches as 'T' (temporarily safe).
Phase 2 (Flip): Iterate over the entire grid.
- If cell is 'O' (Unmarked) -> It's trapped. Flip to 'X'.
- If cell is 'T' (Marked) -> It's safe. Flip back to 'O'.

Visualization

T = REACHED FROM THE BORDER · RED = CAPTURED · GREEN = SAFE

BORDER — LEFT COLUMN

Pass

1 · border

Captured

call stack

No dfs running

Border, left column: call dfs(0, 0)

dfs(0, 0): 'X' — return

board

Two passes. First, DFS runs from every border cell — each row's left and right cell, then each column's top and bottom cell — and marks every 'O' it reaches as 'T'. Corner cells are called twice, once from their row and once from their column; when a corner is an 'O', the second call finds it already 'T' and returns. Then one pass over the whole board captures every 'O' still unmarked (red) and restores every 'T' to 'O' (green).