Surrounded Regions

Surrounded Regions

What is this problem about?

The Surrounded Regions interview question involves a 2D board containing 'X' and 'O' characters. Your task is to capture all regions that are "surrounded" by 'X'. A region is surrounded if it is completely enclosed by 'X's and does not have any path of 'O's that leads to the edge of the board. Capturing a region means changing all 'O's in that region to 'X's.

Why is this asked in interviews?

This is a classic "Medium" problem asked by almost every major tech company, including Apple, Microsoft, and Meta. It tests your knowledge of graph traversal algorithms like Breadth-First Search (BFS) or Depth-First Search (DFS). Specifically, it evaluates whether you can think "outside the box"—instead of finding surrounded regions directly, it's often easier to find the "not surrounded" regions (those connected to the boundary) and then flip everything else.

Algorithmic pattern used

The primary algorithmic pattern is BFS/DFS on a Matrix or Union Find. The most efficient strategy is:

1. Iterate through all 'O's on the boundaries of the board.
2. Perform a DFS or BFS from each boundary 'O' to mark all connected 'O's as "Safe" (e.g., change them to a temporary character like '#').
3. After the traversal, any remaining 'O' on the board must be surrounded. Flip these to 'X'.
4. Finally, flip the '#' characters back to 'O'.

Example explanation

Board: X X X X X O O X X X O X X O X X

1. Boundary 'O' at (3, 1). Mark it and its connected 'O's. But (3,1) is only connected to 'X's. So just (3,1) -> #.
2. Other 'O's at (1,1), (1,2), (2,2) are not connected to any boundary 'O'.
3. Flip remaining 'O's to 'X'.
4. Flip # back to 'O'. Result: X X X X X X X X X X X X X O X X

Common mistakes candidates make

A frequent mistake is performing a DFS on every 'O' and trying to track if it hits a boundary. This can be complex and leads to redundant work. Another error is not handling the recursion depth in DFS, which can lead to stack overflow on very large boards (in such cases, BFS or iterative DFS is preferred).

Interview preparation tip

For the Surrounded Regions coding problem, practice the "boundary traversal" technique. It’s a common pattern for matrix problems where edge cases dictate the solution. Also, familiarize yourself with the Union Find interview pattern, as it provides an alternative way to solve this problem by connecting nodes to a "dummy" boundary node.