Depth-First Search
Medium
Surrounded Regions
Capture regions that are fully surrounded by 'X'.
10 min read
Solve on LeetCodeExamples
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 / 7
X
X
X
X
X
O
O
X
X
X
O
X
X
O
X
X
Problem: Capture all regions surrounded by 'X'. Any 'O' on border (or connected to border) is safe.
1x
See the Logic in Motion
Stop memorizing code. Unlock the full interactive visualizer to master the logic step-by-step.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.