Watch 10 video solutions for Surrounded Regions, a medium level problem involving Array, Depth-First Search, Breadth-First Search. This walkthrough by take U forward has 231,780 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |