In a board of X and O, flip every O that belongs to a region not connected to the border into X. O cells connected to the border stay.
Before you code
Deciding for each region whether it touches the border is awkward. The complement is easy: flood from every border O, and whatever the flood reaches is safe.
Hints
- DFS or BFS from each O on the border, marking reached cells as safe (for example, change them to S).
- Scan the board: remaining O become X, and S become O again.
- Each cell is visited a constant number of times.
Production & complexity notes
When solving Surrounded regions on LeetCode (medium), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Cycles and connected components to reinforce the underlying pattern.
What it practices
Separating components by whether they touch a boundary, from Cycles and connected components.