Skip to main content
Talentd

Surrounded Regions - Solution & Explanation

MediumArrayDepth-First SearchBreadth-First SearchUnion Find29 min readAsked at: Amazon, Microsoft, Meta +9
Practice this problem

Problem Statement

You are given an m x n matrix board containing letters 'X' and 'O', capture regions that are surrounded:

  • Connect: A cell is connected to adjacent cells horizontally or vertically.
  • Region: To form a region connect every 'O' cell.
  • Surround: The region is surrounded with '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.length
  • n == board[i].length
  • 1 <= m, n <= 200
  • board[i][j] is 'X' or 'O'.

Approach Overview

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 1: Depth-First Search (DFS)

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'.

Code

CC++JavaPythonC#JavaScriptGoTypeScriptRust

C

C++

Java

Python

C#

JavaScript

Go

TypeScript

Rust

Complexity

Time Complexity: O(m * n), Space Complexity: O(m * n) due to the DFS recursion stack.

Try this approach in the editor →

Approach 2: Breadth-First Search (BFS)

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'.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(m * n), Space Complexity: O(m * n) for the queue's maximal use.

Try this approach in the editor →

Approach 3: Union-Find Set

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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—

Detailed Complexity Analysis

ApproachTimeSpaceWhen 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

Video Solution

Surrounded Regions - Graph - Leetcode 130 - Python • NeetCode • 142,395 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Surrounded Regions easy or hard?
Surrounded Regions is considered a medium difficulty problem. The challenge is recognizing that border-connected regions should not be flipped. Once that insight is clear, the problem reduces to a standard DFS or BFS grid traversal.
How to solve Surrounded Regions in O(n)?
Treat the grid as a graph and start DFS or BFS from all border 'O' cells. Mark every reachable 'O' as safe using a temporary marker. After traversal, flip all remaining 'O' cells to 'X' and restore the marked cells. Each cell is processed once, giving O(m*n) time.
What is the best approach for Surrounded Regions?
Depth-First Search (DFS) or Breadth-First Search (BFS) starting from border cells is the best approach. Instead of checking every region, mark all 'O' cells connected to the border as safe, then flip the remaining ones. This avoids redundant checks and runs in O(m*n) time.
What data structure is used in Surrounded Regions?
The solution typically uses a matrix traversal with DFS recursion or a BFS queue. Some implementations also use a Union-Find (Disjoint Set) structure to track connectivity between cells and border nodes.
What is the time complexity of Surrounded Regions?
The optimal DFS or BFS solution runs in O(m*n) time because every cell in the grid is visited at most once. Space complexity is O(m*n) in the worst case due to recursion stack or queue storage during traversal.
Surrounded Regions Python or Java solution approach?
Python and Java solutions usually implement DFS or BFS flood fill. Start from border cells containing 'O', mark connected cells, then iterate through the board to flip enclosed regions. Both languages achieve O(m*n) time complexity with similar logic.
Is Surrounded Regions asked at Google, Amazon, or Meta?
Surrounded Regions is a common medium-level grid traversal problem frequently asked in interviews at companies like Amazon, Google, and Meta. It tests understanding of graph traversal, connected components, and matrix boundary conditions.

Ready to solve this problem?

Practice Surrounded Regions with our built-in code editor and test cases.

Practice on FleetCode
Previous

Number of Islands

Next

Walls and Gates