Approach Summary
DFS/BFS from border Os to mark safe cells. Then flip all remaining Os to X and restore safe cells to O.
How to Recognize This Pattern
- "Capture surrounded regions"
- Work backwards from the border — safe Os touch the edge
Complexity Analysis
Time Complexity
O(m × n)
Space Complexity
O(m × n)
Tags
Array DFS BFS Union-Find Matrix