Surrounded Regions
Understanding the Problem
We have a 2D grid of 'X' and 'O' characters. We need to find every region of connected 'O's that is completely enclosed by 'X's on all sides, and flip those 'O's to 'X's. But any 'O' that sits on the border of the board, or any 'O' connected to a border 'O', must stay as 'O'.
The subtle part is what "surrounded" means. An 'O' region is surrounded only if there is no path from any cell in that region to the edge of the board. If even one cell in the region touches the border, the entire region is safe.
This suggests a cleaner formulation. Instead of checking every 'O' region to see if it is surrounded, flip the question: start from the border, find all 'O's reachable from the border, and mark them as safe. Everything that is still 'O' after that must be surrounded, so we flip it.
Key Constraints:
1 <= m, n <= 200→ The grid can have up to 40,000 cells. An O(m n) solution handles this comfortably. A quadratic O((m n)^2) scan would be around 1.6 billion operations, which is too slow.- A recursive flood fill can recurse as deep as the number of cells. On a 200 x 200 board that is up to 40,000 stack frames, which is the main reason to consider an iterative alternative.
Approach 1: DFS from Every O Region
Intuition
Find every connected region of 'O's and check whether any cell in that region sits on the border. If no cell touches the border, the region is surrounded and we flip it. If even one cell touches the border, the whole region stays.
We scan the grid, and whenever we reach an unvisited 'O', we run DFS to discover the entire connected component. During the traversal, we collect every cell and track whether any of them lies on the border. After the DFS finishes, if the region does not touch the border, we flip all collected cells to 'X'.
Algorithm
- Create a
visitedmatrix of the same size as the board. - Iterate through every cell in the board.
- When we find an unvisited
'O', run DFS to collect all cells in that connected region. During the DFS, track whether any cell is on the border. - After the DFS finishes, if no cell in the region touches the border, flip all collected cells to
'X'. - Repeat until all cells have been processed.
Example Walkthrough
Code
- Time Complexity: O(m * n). We visit every cell at most once during DFS traversals. Collecting and flipping regions is bounded by the total number of cells.
- Space Complexity: O(m n). The visited matrix takes O(m n) space. The recursion stack can go as deep as m * n in the worst case.
This approach collects each region into a list before deciding whether to flip it, and it needs a separate visited matrix. The next approach removes both by starting the search from the border instead of the interior.
Approach 2: Border DFS (Optimal)
Intuition
Instead of figuring out which 'O' regions are surrounded, figure out which ones are not surrounded and protect them. Any 'O' reachable from the border is safe. Everything else gets captured. This removes the need to collect regions or track which ones touch the edge, since reachability from the border already encodes that.
Walk along all four borders. Whenever we find an 'O', run DFS from it to mark all connected 'O's as safe using a temporary marker 'S'. After processing all borders, sweep the entire board: any remaining 'O' is surrounded (flip to 'X'), and any 'S' is safe (restore to 'O').
An 'O' is safe exactly when it can reach the border through other 'O's, which is the same as being reachable from a border 'O' (the relation is symmetric). The border flood fill marks precisely that set, so every unmarked 'O' left after the flood is surrounded. The 'S' marker doubles as the visited flag and the safe flag, which is why no separate matrix is needed.
Algorithm
- Iterate along all four borders of the board (top row, bottom row, left column, right column).
- For each border cell that contains
'O', run DFS to mark it and all connected'O's as'S'(safe). - After all border DFS runs complete, sweep the entire board:
- Change every
'O'to'X'(surrounded, capture it). - Change every
'S'back to'O'(safe, restore it).
Example Walkthrough
Code
- Time Complexity: O(m * n). The border DFS visits each cell at most once. The final sweep touches each cell exactly once.
- Space Complexity: O(m n). The recursion stack can go as deep as m n in the worst case. No extra matrix needed since we modify the board in-place.
The Border DFS is optimal in time, but a recursive flood fill can overflow the call stack on a large board where the 'O's form one long snake. Union Find solves the same connectivity question with an iterative scan.
Approach 3: Union Find
Intuition
Model the problem as connectivity. Treat every cell as a node and union adjacent 'O' cells together. Add one virtual border sentinel node, and union every border 'O' with it. After processing, an 'O' is safe if and only if it shares a component with the sentinel. Any 'O' in a different component is surrounded and gets flipped.
The grid scan that builds the components is iterative, so it avoids deep recursion across the board. The only recursion left is inside find, where union by rank keeps the trees shallow.
Algorithm
- Create a Union Find structure with
m * n + 1nodes. The last node is the border sentinel. - Iterate through every cell. For each
'O': - If it is on the border, union it with the sentinel.
- Union it with any adjacent
'O'cells (check right and down to avoid redundant unions). - Sweep the board. For each
'O', check if it is connected to the sentinel. If not, flip it to'X'.
Example Walkthrough
Code
- Time Complexity: O(m n alpha(m n)). Each union/find operation takes O(alpha) amortized time. For practical purposes, alpha < 5, so this is effectively O(m n).
- Space Complexity: O(m n). The parent and rank arrays each take O(m n) space. No recursion stack overhead.