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 - LeetCode Solution

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

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. After marking, flip all unmarked 'O's to 'X' and restore the marked ones back to 'O'. This approach ensures each cell is visited at most once, achieving O(m*n) time.

Optimal Approach

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.

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

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

20for r in range(ROWS):
  for c in range(COLS):
      if board[r][c] == "O":
          board[r][c] = "X"

Objective

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

Key Insight

After marking safe 'O's, any remaining 'O' must be fully surrounded by 'X's and thus should be flipped. This step finalizes the capture by scanning the entire board and flipping unmarked 'O's to 'X's, ensuring correctness without revisiting the DFS logic.

Interview Quick-Check

Core Logic

Flipping unmarked 'O's to 'X's captures all surrounded regions without affecting safe regions.

State & Boundaries

Iterate over the entire board to ensure no 'O' is missed.

Common Pitfalls & Bugs

Forgetting to flip all unmarked 'O's leads to incorrect results where surrounded regions remain unflipped.

3

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

25for r in range(ROWS):
  for c in range(COLS):
      if board[r][c] == "T":
          board[r][c] = "O"

Objective

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

Key Insight

The temporary marker 'T' distinguishes safe 'O's during processing. Restoring them back to 'O' completes the transformation, ensuring the board reflects the correct captured and safe regions. This final pass cleans up the board state without additional DFS or complex logic.

Interview Quick-Check

Core Logic

Restoring 'T' to 'O' recovers the original safe regions after surrounded regions have been captured.

State & Boundaries

A full board scan ensures all marked cells are restored.

Common Pitfalls & Bugs

Neglecting this step leaves temporary markers in the final output, violating problem requirements.

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.

Line 23 Critical

board[r][c] = "X"

Flip the captured 'O' to 'X'.

This line performs the actual capture by converting surrounded 'O's to 'X's, finalizing the transformation.

Line 17 Core

if board[r][c] == "O" and (r in [0, ROWS - 1] or c in [0, COLS - 1]):

Check if the current cell is a border 'O'.

Only 'O's on the border or connected to the border are safe; this condition identifies starting points for DFS marking.

Line 22 Core

if board[r][c] == "O":

Check if the current cell is an unmarked 'O' to be captured.

Only 'O's not marked as safe ('T') should be flipped to 'X', capturing surrounded regions.

Line 28 Core

board[r][c] = "O"

Restore the marked cell back to 'O'.

This final step cleans up the board, ensuring the safe regions are correctly represented as 'O's in the output.

Line 7 Core

return

Return immediately if base case conditions are met.

Early return avoids unnecessary recursion and stack overflow by pruning invalid or already processed paths.

Line 10 Core

capture(r + 1, c)

Recursively call DFS on the cell below.

Exploring downward neighbors ensures all connected 'O's are marked as safe, fully traversing the connected region.

Line 11 Core

capture(r - 1, c)

Recursively call DFS on the cell above.

Exploring upward neighbors complements the traversal, ensuring no connected safe 'O' is missed.

Line 12 Core

capture(r, c + 1)

Recursively call DFS on the cell to the right.

Exploring right neighbors completes the four-directional search for connected safe 'O's.

Line 13 Core

capture(r, c - 1)

Recursively call DFS on the cell to the left.

Exploring left neighbors ensures full coverage of the connected safe region.

Line 27 Core

if board[r][c] == "T":

Check if the current cell is marked as safe ('T').

Identifies cells that were temporarily marked to distinguish safe 'O's during processing.

Line 5 Standard

def capture(r, c):

Define the recursive DFS function to mark safe 'O's.

Encapsulating the DFS logic in a helper function allows clean recursive exploration of connected 'O's starting from the border.

Line 15 Standard

for r in range(ROWS):

Iterate over each row index.

This loop initiates the process of scanning the board's border rows and columns for 'O's to start DFS.

Line 16 Standard

for c in range(COLS):

Iterate over each column index.

Nested loop allows scanning every cell in the board to identify border 'O's.

Line 20 Standard

for r in range(ROWS):

Iterate over each row index for flipping phase.

This loop prepares to scan the entire board to flip captured 'O's to 'X's.

Line 21 Standard

for c in range(COLS):

Iterate over each column index for flipping phase.

Nested loop ensures every cell is checked for flipping.

Line 25 Standard

for r in range(ROWS):

Iterate over each row index for restoration phase.

This loop prepares to restore all temporarily marked safe cells back to 'O'.

Line 26 Standard

for c in range(COLS):

Iterate over each column index for restoration phase.

Nested loop ensures all marked cells are restored.

Line 3 Basic

ROWS, COLS = len(board), len(board[0])

Calculate the number of rows and columns in the board.

Caching the dimensions avoids repeated calls to len() and simplifies boundary checks throughout the algorithm.

Test Your Understanding

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

Because any 'O' not connected to the border is surrounded by 'X's and should be captured, while all 'O's connected to the border form safe regions. DFS from the border explores all connected 'O's, marking them as safe, ensuring no safe 'O' is missed.

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)`

Problem

Example

Approach

Solution

Step-by-Step Solution

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

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

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

Line Analysis

Test Your Understanding

Related Problems

Don't just read it. Drill it.