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 filled with 'X' and 'O'. Any region of 'O' completely surrounded by 'X' must be captured by flipping all its cells to 'X'. The catch: if an 'O' is connected to the border, that entire region cannot be captured.
Approach 1: Depth-First Search (DFS) from Borders (O(m*n) time, O(m*n) space)
The key insight is that only regions fully enclosed by 'X' should be flipped. Instead of checking every region individually, mark the safe cells first. Iterate over the grid borders and start a depth-first search whenever you find an 'O'. During DFS, mark all connected 'O' cells as temporary (for example '#') to indicate they are connected to the border and must remain unchanged.
After the DFS traversal finishes, iterate through the entire board. Any remaining 'O' must be surrounded, so flip it to 'X'. Convert the temporary marks back to 'O'. Each cell is visited at most once, giving O(m*n) time complexity with recursion stack space up to O(m*n) in the worst case. This approach fits naturally with problems involving matrix traversal and connected components.
Approach 2: Breadth-First Search (BFS) Flood Fill (O(m*n) time, O(m*n) space)
This approach uses a queue instead of recursion. Scan the borders and push all border 'O' cells into a queue. Perform a breadth-first search, expanding in four directions (up, down, left, right). Every reachable 'O' gets marked as safe using the same temporary marker.
Once BFS finishes, run a final pass across the grid. Flip all remaining 'O' cells to 'X' and restore the marked cells. BFS avoids recursion depth issues and can be easier to control in languages where stack overflow is a concern. The algorithm still processes each cell once, resulting in O(m*n) time and queue space up to O(m*n).
Approach 3: Union-Find (Disjoint Set) (O(m*n * α(n)) time, O(m*n) space)
Another option models the board as a graph. Each 'O' cell belongs to a disjoint set. A virtual node represents the border. Union all border 'O' cells with this node, then union adjacent 'O' cells together. After building the structure, any cell not connected to the border node must be surrounded and can be flipped.
This method works well for connectivity problems but adds extra overhead and implementation complexity compared to DFS or BFS.
Recommended for interviews: DFS from border cells is the expected solution. It demonstrates that you recognized the key insight: protected regions are those connected to the boundary. BFS is equally valid and often preferred when recursion limits are a concern. Explaining why checking borders first simplifies the problem signals strong graph and grid traversal intuition.
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
C++
Java
Python
C#
JavaScript
Go
TypeScript
Rust
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'.
Time Complexity: O(m * n), Space Complexity: O(m * n) for the queue's maximal use.
We can also use a union-find set, connecting each 'O' on the matrix boundary with a super node m times n, and connecting each 'O' in the matrix with the 'O's above, below, left, and right of it.
Then we traverse this matrix, for each position, if it is 'O' and it is not connected to the super node, then we replace it with 'X'.
The time complexity is O(m times n times \alpha(m times n)), and the space complexity is O(m times n). Here, m and n are the number of rows and columns in the matrix, respectively, and \alpha is the inverse Ackermann function.
Python
Java
C++
Go
TypeScript
| 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. |
| Union-Find Set | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Depth-First Search (DFS) | O(m*n) | O(m*n) | Standard interview solution for grid traversal and region capture problems |
| Breadth-First Search (BFS) | O(m*n) | O(m*n) | Preferred when avoiding recursion stack limits or implementing iterative flood fill |
| Union-Find (Disjoint Set) | O(m*n * α(n)) | O(m*n) | Useful when solving multiple connectivity queries or practicing union-find patterns |
G-14. Surrounded Regions | Replace O's with X's | C++ | Java • take U forward • 331,760 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