Introduction

Surrounded Regions is one of the most important Matrix DFS and BFS interview problems.

You are given:

 board[][]

Goal:

Convert all surrounded O's into X's

Rule:

Any O connected to the boundary cannot be captured.

Example

X X X XX O O X
X X O X
X O X X

Output:

X X X XX X X X
X X X X
X O X X

Key Observation

Do NOT find:

Captured O's

Instead find:

Safe O's

Safe O's are:

Boundary O's and Connected O's

Algorithm

1. Traverse boundary.2. Find boundary O's.
3. Run DFS/BFS.
4. Mark safe cells.
5. Convert remaining O's to X's.
6. Restore safe cells.

Dry Run

Input:

X X X X
X O O X
X X O X
X O X X

Safe Cell:

 Bottom Boundary O

Captured Cells:

Middle O Region

Answer:

X X X X
X X X X
X X X X
X O X X

Approach : DFS

Explanation

  1. Start from boundary O's.
  2. Mark them as safe.
  3. Visit connected O's.
  4. Convert remaining O's.
  5. Restore safe cells.

Practice

Complexity Analysis

DFSTime Complexity: O(m × n)
Space Complexity: O(m × n)

BFS
Time Complexity: O(m × n)
Space Complexity: O(m × n)

Why This Problem is Important

  • BFS
  • DFS
  • Matrix Traversal
  • Boundary Traversal
  • Connected Components

Common Beginner Mistakes

  • Capturing boundary O's
  • Forgetting safe marking
  • Boundary traversal errors
  • Missing restoration step
  • Infinite recursion

Interview Tip

Always explain:

Find safe O's not captured O's.

Start DFS/BFS from boundary cells.

Related Questions

  • Number of Islands
  • Flood Fill
  • Pacific Atlantic Water Flow
  • Rotting Oranges
  • Walls and Gates

Final Takeaway

Surrounded Regions is a classic boundary DFS/BFS problem.

It teaches:

  • Boundary Traversal
  • Matrix DFS
  • Matrix BFS
  • Connected Components

Mastering Surrounded Regions makes advanced grid traversal interview questions significantly easier.