loading

Surrounded Regions — Step-by-Step Visualization

mediumLeetCode #130ArrayBFSDFSUnion FindMatrix

You are 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. An 'O' is not captured if it is on the border, or if it is connected to an 'O' that is on the border.

Algorithm Pattern

Border-First Search (Pruning)

Key Idea

Instead of checking every 'O' to see if it's surrounded, we focus on the 'O's that are DEFINITELY NOT surrounded. These are the 'O's on the border and any 'O's connected to them. We can use DFS/BFS to mark these 'Safe' cells. Finally, any 'O' that isn't marked 'Safe' must be captured (flipped to 'X').

Step-by-Step Approach

  1. Traverse the borders of the matrix.
  2. If a border cell is an 'O', run a DFS to mark it and all connected 'O's as 'T' (temporary safe).
  3. After marking all safe regions, iterate through the entire board.
  4. Convert remaining 'O's to 'X' (captured).
  5. Convert 'T's back to 'O' (restored safe).

Common Gotchas

  • 4-directionally means up, down, left, right (not diagonal).
  • Correctly identifying the border cells is the first step.

Related Problems

← All problems