Surrounded Regions
Last Updated: April 5, 2026
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 tricky part is figuring out what "surrounded" really 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 naturally leads to a key observation: instead of checking every 'O' region to see if it is surrounded, we can flip the question. Start from the border, find all 'O's reachable from the border, and mark them as safe. Everything else 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 is ideal. Anything quadratic like O((m n)^2) would be around 1.6 billion operations, which is too slow.board[i][j]is'X'or'O'→ Binary grid, no special values to worry about.
Approach 1: DFS from Every O Region
Intuition
The most direct approach is to 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.
So we scan the grid, and whenever we hit an unvisited 'O', we run DFS to discover the entire connected component. During the traversal, we collect all cells and track whether any of them is 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 works correctly, but it collects cells into a list before deciding whether to flip them. What if we could avoid that by being smarter about where we start our search?
Approach 2: Border DFS (Optimal)
Intuition
Here is the key insight: flip the question. Instead of trying to figure 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.
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').
Every 'O' on the board falls into exactly one of two categories: reachable from the border (safe) or not (surrounded). By flooding inward from the border, we precisely identify the safe set. The temporary 'S' marker acts as both a "visited" flag and a "safe" flag, so we need no separate data structure.
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 already optimal in time, but recursive DFS can hit stack overflow on very large boards. Union Find avoids recursion entirely.
Approach 3: Union Find
Intuition
Union Find gives us a different angle. Treat every cell as a node and union adjacent 'O' cells together. Create a virtual "border sentinel" node. Every 'O' on the border gets unioned with this sentinel. After processing, any 'O' connected to the sentinel is safe. Any 'O' not connected to the sentinel is surrounded and should be flipped.
This approach is fully iterative (no recursion), which avoids stack overflow concerns on large grids.
Union Find naturally models the connectivity question at the heart of this problem. By introducing a sentinel node that represents "the border," we turn "is this O reachable from the border?" into "is this O in the same connected component as the sentinel?" Path compression and union by rank keep each operation nearly O(1).
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.