Back to Problems

Surrounded Regions

Medium
DFS

Given an m x n matrix board containing 'X' and 'O', capture all regions that are 4-directionally surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region.

Key Insight: Instead of finding surrounded regions directly, find the regions that are NOT surrounded (connected to the border) and mark them as safe. Everything else gets captured.

Algorithm:

  1. Start DFS from all 'O's on the border
  2. Mark all 'O's connected to border as "safe" (use a temporary marker like 'S')
  3. After all border-connected regions are marked:
    • Remaining 'O's are surrounded -> flip to 'X'
    • 'S' cells are not surrounded -> flip back to 'O'

Why this works: An 'O' is NOT surrounded if and only if there's a path of 'O's connecting it to the border. DFS from border cells finds exactly these.

Example:

X X X X      X X X X
X O O X  ->  X X X X
X X O X      X X X X
X O X X      X O X X

The bottom 'O' touches the border, so it's not captured. The interior 'O's are all captured.

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: The surrounded region (middle O's) is captured. The O on the bottom border remains.

Example 2

Input: board = [["X"]]
Output: [["X"]]
Explanation: Single cell board with X stays X.

Constraints

  • •m == board.length
  • •n == board[i].length
  • •1 <= m, n <= 200
  • •board[i][j] is 'X' or 'O'.
Show Hints (4)
Hint 1: Think reverse: which O's should NOT be captured?
Hint 2: O's connected to the border cannot be surrounded. Start your search there.
Hint 3: Use a temporary marker to distinguish "safe" O's from those to be captured.
Hint 4: After marking safe cells, do a second pass to finalize the board.
Loading editor...

Test Results

Click "Run" to execute your code against test cases

AI Tutor

Socratic guidance - I'll ask questions, not give answers

AI Tutor
Hello! I'm your AI tutor, here to guide you through this problem using the Socratic method. I won't give you direct answers, but I'll ask questions and provide hints to help you discover the solution yourself. What's your first instinct when you look at this problem? What approach comes to mind?