Surrounded Regions

35 min · solve()

Picture white tiles inside a dark frame. A white patch sealed away from the frame gets painted dark; a white path that reaches the frame survives.

You're given a rectangular board made of "X" and "O" cells. An "O" region is captured when none of its cells connects to a border "O" through up, down, left, or right moves. Flip every captured region to "X", keep every border-connected region, and return the resulting board.

A few ground rules:

Diagonal cells don't connect.
One border connection protects the entire connected "O" region.
The returned board must keep the same rows and columns as the input.

Constraints

1 <= board.length <= 200
1 <= board[r].length <= 200
Every row has the same length.
board[r][c] is either "X" or "O".

Hints

Invert the question

Testing every interior region is expensive. Which "O" cells are guaranteed not to be captured, and where must every such region begin?

Start from the frame

Run a traversal from every border "O". Mark all "O" cells reachable from those starts as safe.

Resolve three states

After marking, unmarked "O" cells become "X". Marked safe cells become "O" again. Original "X" cells never move.

Follow-up

Can you prove that searching only from the border finds every region that must survive?

Visible cases

Examples

Example 1

ready

Input: board = [ [ "X", "X", "X", "X" ], [ "X", "O", "O", "X" ], [ "X", "X", "O", "X" ], [ "X", "O", "X", "X" ] ]
Expected: [ [ "X", "X", "X", "X" ], [ "X", "X", "X", "X" ], [ "X", "X", "X", "X" ], [ "X", "O", "X", "X" ] ]
Why: the enclosed three-cell region flips; the border O survives

Example 2

ready

Input: board = [ [ "O", "O", "O" ], [ "O", "X", "O" ], [ "O", "O", "O" ] ]
Expected: [ [ "O", "O", "O" ], [ "O", "X", "O" ], [ "O", "O", "O" ] ]
Why: every O belongs to a region touching the border

Example 3

ready

Input: board = [ [ "X", "O", "X", "X", "X" ], [ "X", "O", "O", "X", "X" ], [ "X", "X", "O", "X", "X" ], [ "X", "O", "X", "O", "X" ], [ "X", "X", "X", "X", "X" ] ]
Expected: [ [ "X", "O", "X", "X", "X" ], [ "X", "O", "O", "X", "X" ], [ "X", "X", "O", "X", "X" ], [ "X", "X", "X", "X", "X" ], [ "X", "X", "X", "X", "X" ] ]
Why: the top-connected path stays O while two isolated interior cells flip

Interview signal

Asked at

AmazonGoogle

Per-cell BFS — ask every O whether it can escape

The direct approach starts a breadth-first search from each "O". If that search reaches any border, the starting cell survives. Otherwise, it becomes "X" in the result. The searches read from an untouched copy, so flipping one cell can't cut off a later cell's escape route.

from collections import deque
 
 
def solve(board: list[list[str]]) -> list[list[str]]:
    rows, cols = len(board), len(board[0])
    original = [row[:] for row in board]
    result = [row[:] for row in board]
 
    def reaches_border(start_row: int, start_col: int) -> bool:
        queue = deque([(start_row, start_col)])
        seen = {(start_row, start_col)}
        while queue:
            row, col = queue.popleft()
            if row in (0, rows - 1) or col in (0, cols - 1):
                return True
            for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                nr, nc = row + dr, col + dc
                if (0 <= nr < rows and 0 <= nc < cols and
                        (nr, nc) not in seen and original[nr][nc] == "O"):
                    seen.add((nr, nc))
                    queue.append((nr, nc))
        return False
 
    for row in range(rows):
        for col in range(cols):
            if original[row][col] == "O" and not reaches_border(row, col):
                result[row][col] = "X"
    return result

One large region may be explored again from every cell it contains. Time O((mn)²) in the worst case. Space O(mn) for one BFS plus the board copies.

Boundary DFS — mark the regions that survive

The useful pattern is boundary DFS, a depth-first search seeded from qualifying cells along the grid's outer edge. Reverse the decision: instead of proving which regions are trapped, start from every border "O" and mark everything it can reach as safe.

Use a temporary marker "S". Once all boundary searches finish, every remaining "O" is enclosed and flips to "X"; every "S" returns to "O".

def solve(board: list[list[str]]) -> list[list[str]]:
    rows, cols = len(board), len(board[0])
 
    def mark_safe(start_row: int, start_col: int) -> None:
        if board[start_row][start_col] != "O":
            return
        board[start_row][start_col] = "S"
        stack = [(start_row, start_col)]
        while stack:
            row, col = stack.pop()
            for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                nr, nc = row + dr, col + dc
                if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] == "O":
                    board[nr][nc] = "S"
                    stack.append((nr, nc))
 
    for row in range(rows):
        mark_safe(row, 0)
        mark_safe(row, cols - 1)
    for col in range(cols):
        mark_safe(0, col)
        mark_safe(rows - 1, col)
 
    for row in range(rows):
        for col in range(cols):
            if board[row][col] == "O":
                board[row][col] = "X"
            elif board[row][col] == "S":
                board[row][col] = "O"
    return board

Every cell is marked and resolved at most once. Time O(mn). Space O(mn) in the worst case for the DFS stack.

LeetCode's version mutates the board in place and returns void; ours returns the board so the judge can compare it.

Loading editor

Console

ready to run

Ready to run.

3 cases are queued.

Visible testcase

Case 1

Arguments · JSON arrayboard: char[][]

Expected

[
  [
    "X",
    "X",
    "X",
    "X"
  ],
  [
    "X",
    "X",
    "X",
    "X"
  ],
  [
    "X",
    "X",
    "X",
    "X"
  ],
  [
    "X",
    "O",
    "X",
    "X"
  ]
]

Run: visible + custom · Submit: full suite