You are given an m x n matrix board containing letters 'X' and 'O', capture regions that are surrounded:
'O' cell.'X' cells if you can connect the region with 'X' cells and none of the region cells are on the edge of the board.To capture a surrounded region, replace all 'O's with 'X's in-place within the original board. You do not need to return anything.
Example 1:
Input: board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
Output: [["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]
Explanation:
In the above diagram, the bottom region is not captured because it is on the edge of the board and cannot be surrounded.
Example 2:
Input: board = [["X"]]
Output: [["X"]]
Constraints:
m == board.lengthn == board[i].length1 <= m, n <= 200board[i][j] is 'X' or 'O'.Problem Overview: You are given an m x n board containing 'X' and 'O'. Any region of 'O' that is completely surrounded by 'X' must be flipped to 'X'. Cells connected to the border cannot be captured because they are not fully enclosed.
Approach 1: Depth-First Search (DFS) from Borders (O(m*n) time, O(m*n) space)
The key insight: instead of searching for surrounded regions, mark the regions that cannot be captured. Start DFS from every 'O' on the board boundary. During DFS, traverse in four directions and temporarily mark all reachable 'O' cells as safe (commonly with a marker like '#'). After processing all borders, iterate through the grid: flip remaining 'O' cells to 'X' because they are surrounded, and restore the marked safe cells back to 'O'. DFS works well here because it naturally explores connected components in a matrix. The recursion stack or visited structure contributes O(m*n) worst‑case space.
Approach 2: Breadth-First Search (BFS) from Borders (O(m*n) time, O(m*n) space)
This approach uses a queue instead of recursion but follows the same border-first strategy. Push every boundary 'O' into a queue and run BFS. For each cell, check its four neighbors and enqueue any unvisited 'O'. Mark them as safe during traversal. Once BFS finishes, scan the grid again to flip the remaining 'O' cells to 'X'. BFS avoids deep recursion and can be preferable in languages with strict recursion limits. The algorithm still touches each cell at most once, giving O(m*n) time complexity and O(m*n) queue space in the worst case. This approach is a classic application of Breadth-First Search on grid graphs.
Approach 3: Union-Find (Disjoint Set) (O(m*n * α(n)) time, O(m*n) space)
Model the board as a graph where each cell is a node. Use a Union Find structure to group adjacent 'O' cells. Introduce a virtual node representing the border. Any 'O' on the boundary is unioned with this node. Interior 'O' cells are unioned with neighboring 'O' cells. After building the sets, scan the board and flip any 'O' not connected to the border root. The amortized complexity is nearly linear due to path compression and union by rank. This approach is conceptually clean but requires extra bookkeeping compared to DFS/BFS.
Recommended for interviews: DFS or BFS from the borders is the expected solution. It demonstrates that you recognized the core trick: mark non-capturable regions instead of trying to detect enclosed ones. A brute-force region check would repeatedly scan components and becomes inefficient. Border traversal with Depth-First Search or BFS solves the problem in a single pass with O(m*n) time.
This approach uses Depth-First Search (DFS) to mark all 'O's connected to the boundary as safe. These 'O's cannot be converted to 'X' because they are on the boundary or connected to the boundary. The rest of the 'O's can be safely converted to 'X'.
In this C implementation, we perform a DFS from each 'O' on the boundary, marking connected 'O's as 'A'. After marking, we iterate the board again to flip all 'O's to 'X' and revert 'A' back to 'O'.
C++
Java
Python
C#
JavaScript
Time Complexity: O(m * n), Space Complexity: O(m * n) due to the DFS recursion stack.
This approach uses Breadth-First Search (BFS) utilizing a queue to explore 'O's connected to the boundary. This approach is iterative and avoids deep recursion, keeping the method stack usage low.
In this C implementation using BFS, a queue holds nodes to explore. Marking 'O's as 'A' when connected to border starts from queues, flipping others to 'X'.
C++
Java
Python
C#
JavaScript
Time Complexity: O(m * n), Space Complexity: O(m * n) for the queue's maximal use.
| Approach | Complexity |
|---|---|
| Depth-First Search (DFS) | Time Complexity: O(m * n), Space Complexity: O(m * n) due to the DFS recursion stack. |
| Breadth-First Search (BFS) | Time Complexity: O(m * n), Space Complexity: O(m * n) for the queue's maximal use. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Depth-First Search (DFS) from Borders | O(m*n) | O(m*n) | Most common interview solution; simple for exploring connected regions in a grid |
| Breadth-First Search (BFS) | O(m*n) | O(m*n) | Preferred when avoiding recursion depth limits or when iterative traversal is required |
| Union-Find (Disjoint Set) | O(m*n * α(n)) | O(m*n) | Useful when modeling connectivity problems across many union operations |
G-14. Surrounded Regions | Replace O's with X's | C++ | Java • take U forward • 231,780 views views
Watch 9 more video solutions →Practice Surrounded Regions with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor