How do you solve Surrounded Regions?

Use DFS starting from all border cells that contain 'O'. Mark these and all connected 'O's with a temporary marker 'T'. Then iterate over the board to flip all remaining 'O's to 'X' (captured regions) and convert 'T's back to 'O' (safe regions). This approach guarantees correctness and efficiency.

What pattern does Surrounded Regions use?

The Pattern: DFS (Boundary-Connected Region Marking) The Heuristic: When a problem requires identifying regions connected to boundaries, invert the problem by starting DFS from the boundary to mark safe regions, then process the rest accordingly.

Surrounded Regions — DFS

Q: What is the time complexity of Surrounded Regions?

O(m * n). Each cell is visited at most once during the DFS marking and once during the final iteration to flip cells, resulting in linear time relative to the board size.

Problem

Given an m x n matrix board containing 'X' and 'O', capture all regions surrounded by 'X' by flipping all 'O's that are not connected to the border to 'X'.

m == board.length
n == board[i].length
1 ≤ m, n ≤ 200
board[i][j] is 'X' or 'O'

Example

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

The 'O's in the middle are surrounded by 'X' and flipped to 'X'. The 'O' at the bottom left corner is connected to the border, so it remains 'O'. The algorithm marks all 'O's connected to the border with a temporary marker 'T' using DFS, then flips all remaining 'O's to 'X', and finally restores 'T' back to 'O'.

Approach

Straightforward Solution

A naive approach would check each 'O' and perform a flood fill to determine if it is surrounded, which can be expensive and redundant, leading to O(m*n*(m+n)) time complexity.

Core Observation

Any 'O' connected to the border cannot be captured because it is not fully surrounded by 'X'. Therefore, the problem reduces to identifying and preserving all 'O's connected to the border.

Path to Optimal

Preview

The key insight is to invert the problem: instead of searching for surrounded regions, start from the border and mark all 'O's connected to the border as safe. This can be done efficiently with DFS or BFS…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Use DFS starting from all border cells that contain 'O'. Mark these and all connected 'O's with a temporary marker 'T'…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(m * n)

Each cell is visited at most once during the DFS marking and once during the final iteration to flip cells, resulting in linear time relative to the board size.

Space

O(m * n)

In the worst case, the recursion stack for DFS can grow up to O(m * n) if the entire board is filled with 'O's connected to the border. The in-place marking avoids extra data structures, but recursion stack space is required.

Solution

Python

1class Solution:
  def solve(self, board: list[list[str]]) -> None:
      ROWS, COLS = len(board), len(board[0])
4
      def capture(r, c):
          if r < 0 or c < 0 or r == ROWS or c == COLS or board[r][c] != "O":
              return
          
          board[r][c] = "T"
          capture(r + 1, c)
          capture(r - 1, c)
          capture(r, c + 1)
          capture(r, c - 1)
14
      for r in range(ROWS):
          for c in range(COLS):
              if board[r][c] == "O" and (r in [0, ROWS - 1] or c in [0, COLS - 1]):
                  capture(r, c)
      
      for r in range(ROWS):
          for c in range(COLS):
              if board[r][c] == "O":
                  board[r][c] = "X"
      
      for r in range(ROWS):
          for c in range(COLS):
              if board[r][c] == "T":
                  board[r][c] = "O"

Step-by-Step Solution

1

Mark Border-Connected 'O's Using DFS to Protect Safe Regions

5def capture(r, c):
  if r < 0 or c < 0 or r == ROWS or c == COLS or board[r][c] != "O":
      return
  board[r][c] = "T"
  capture(r + 1, c)
  capture(r - 1, c)
  capture(r, c + 1)
  capture(r, c - 1)
15for r in range(ROWS):
  for c in range(COLS):
      if board[r][c] == "O" and (r in [0, ROWS - 1] or c in [0, COLS - 1]):
          capture(r, c)

Objective

To identify and mark all 'O's connected to the border as safe by performing DFS from border cells.

Key Insight

Starting DFS from border 'O's ensures that all connected 'O's are marked as safe in a single pass. Marking them with a temporary character prevents revisiting and distinguishes safe 'O's from those that should be captured. This approach avoids redundant checks and efficiently isolates the regions that must remain unchanged.

Interview Quick-Check

Core Logic

DFS explores all 'O's connected to the border, marking them to prevent flipping, effectively separating safe regions from capturable ones.

State & Boundaries

The DFS base case checks for out-of-bounds indices and cells that are not 'O', ensuring recursion terminates correctly.

Common Pitfalls & Bugs

Failing to mark visited 'O's leads to infinite recursion or repeated work; using a temporary marker like 'T' prevents this.

Complexity

Each cell is visited at most once during DFS, ensuring O(m*n) time complexity.

2

Flip Unmarked 'O's to 'X' to Capture Surrounded Regions

To convert all 'O's not connected to the border into 'X's, effectively capturing surrounded regions.

3

Restore Marked 'T's Back to 'O's to Finalize Safe Regions

To revert the temporary marker 'T' back to 'O' to restore the original safe regions.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 4 Critical lines interviewers watch for.

Line 9 Critical

board[r][c] = "T"

Mark the current 'O' cell as 'T' to indicate it is safe.

This marking is the critical step that prevents infinite recursion and correctly identifies safe regions, enabling the algorithm to separate safe from capturable 'O's.

Line 6 Critical

if r < 0 or c < 0 or r == ROWS or c == COLS or board[r][c] != "O":

Check if the current cell is out of bounds or not an 'O'.

This base case prevents invalid access and stops recursion on cells that are either 'X' or already marked, ensuring correctness and termination.

Line 18 Critical

capture(r, c)

Invoke DFS to mark all connected safe 'O's starting from this border cell.

This call triggers the marking of all safe 'O's connected to the border, ensuring they are preserved.

Full line-by-line criticality + rationale for all 21 lines available on Pro.

Test Your Understanding

Why does starting DFS from the border 'O's guarantee that all safe 'O's are marked correctly?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Surrounded Regions from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Surrounded Regions drill

or drill a free problem

1	`class Solution:`
2	`def solve(self, board: list[list[str]]) -> None:`
3	`ROWS, COLS = len(board), len(board[0])`
4
5	`def capture(r, c):`
6	`if r < 0 or c < 0 or r == ROWS or c == COLS or board[r][c] != "O":`
7	`return`
8
9	`board[r][c] = "T"`
10	`capture(r + 1, c)`
11	`capture(r - 1, c)`
12	`capture(r, c + 1)`
13	`capture(r, c - 1)`
14
15	`for r in range(ROWS):`
16	`for c in range(COLS):`
17	`if board[r][c] == "O" and (r in [0, ROWS - 1] or c in [0, COLS - 1]):`
18	`capture(r, c)`
19
20	`for r in range(ROWS):`
21	`for c in range(COLS):`
22	`if board[r][c] == "O":`
23	`board[r][c] = "X"`
24
25	`for r in range(ROWS):`
26	`for c in range(COLS):`
27	`if board[r][c] == "T":`
28	`board[r][c] = "O"`

5	`def capture(r, c):`
6	`if r < 0 or c < 0 or r == ROWS or c == COLS or board[r][c] != "O":`
7	`return`
9	`board[r][c] = "T"`
10	`capture(r + 1, c)`
11	`capture(r - 1, c)`
12	`capture(r, c + 1)`
13	`capture(r, c - 1)`
15	`for r in range(ROWS):`
16	`for c in range(COLS):`
17	`if board[r][c] == "O" and (r in [0, ROWS - 1] or c in [0, COLS - 1]):`
18	`capture(r, c)`