332. In a board of "X" and "O", capture every region of "O" cells that is completely surrounded by "X" (flip it to "X").
MediumString algorithms
Technical
Show model answer
A region survives only if it touches the border. So flood fill (BFS or DFS) from every "O" on the border, marking reachable "O" cells as safe (for example, change them to "#"). Then sweep the board: remaining "O" cells are surrounded and become "X", and "#" cells go back to "O".
Every cell is visited a constant number of times, giving O(R·C) time; space is O(R·C) in the worst case for the BFS queue or recursion stack (use an explicit queue to avoid stack overflow on large boards). Union-find with a virtual "border" node is an alternative.