Surrounded Regions

Capture regions that are fully surrounded by 'X'.

10 min read

Solve 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): Iterate over the 4 borders of the grid. If you find an 'O', launch DFS and mark it as 'T' (Temporary 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

Step 1 / 1

Visualization data missing

Initializing...

Custom Input

Scan Borders -> Mark Safe.
Scan Interior -> Flip Trapped.

Stop Guessing, Start Mastering.

Build the FAANG intuition. Master this pattern with optimized implementations, visual dry runs, and our curated collection of high-yield problems.