LeetCode 130: Surrounded Regions

Capture surrounded O regions by marking border-connected O cells first, then flipping the remaining O cells.

leetcodemediumarraymatrixdfsbfsunion-find

Problem Restatement

We are given an m x n board containing only two characters:

Character Meaning
"X" Wall or blocking cell
"O" Open cell

We need to capture every region of "O" cells that is completely surrounded by "X" cells.

A region is connected 4-directionally, meaning cells connect through up, down, left, and right. Diagonal connection does not count.

To capture a surrounded region, we flip every "O" in that region into "X".

The modification must happen in-place. The function does not return a new board. LeetCode states that surrounded regions are captured by replacing all surrounded "O" cells with "X" in the original board.

Examples

Example 1:

board = [
    ["X", "X", "X", "X"],
    ["X", "O", "O", "X"],
    ["X", "X", "O", "X"],
    ["X", "O", "X", "X"],
]

The middle "O" cells are surrounded:

(1, 1), (1, 2), (2, 2)

They do not touch the border, and they have no path to a border "O".

The bottom "O" at (3, 1) is on the border, so it cannot be captured.

After solving:

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

Example 2:

board = [["X"]]

There is no "O" region to capture.

Output:

[["X"]]

Input and Output

Item Meaning
Input board: list[list[str]]
Output Nothing, modify board in-place
Cell values "X" or "O"
Connection 4-directional only
Captured region An "O" component with no connection to the border

Function shape:

class Solution:
    def solve(self, board: list[list[str]]) -> None:
        ...

First Thought: Check Each O Region

One direct idea is:

  1. Find an unvisited "O".
  2. Explore its whole connected region.
  3. Decide whether the region touches the border.
  4. If it does not touch the border, flip the region to "X".

This works, but the bookkeeping is heavier because each region must store its cells until we know whether it is captured.

There is a simpler reverse view.

Key Insight

Instead of finding surrounded regions directly, find the regions that cannot be captured.

An "O" cannot be captured if it is connected to the border.

That includes:

  1. Every "O" on the border.
  2. Every "O" connected to a border "O" through other "O" cells.

So we mark all border-connected "O" cells as safe.

Then every remaining "O" must be surrounded.

Use a temporary marker, for example "#":

Cell after marking Meaning
"#" This was an "O" connected to the border, so keep it
"O" This "O" was not connected to the border, so flip it
"X" Already blocked

Why Border Search Works

A captured region is completely surrounded by "X".

That means it has no path to any border cell.

So the only "O" cells that survive are exactly the cells reachable from the border.

This reverses the problem:

Instead of asking:

Which O regions are surrounded?

ask:

Which O cells can escape to the border?

The second question is easier because the starting cells are only on the border.

Algorithm

Let m be the number of rows and n be the number of columns.

  1. Scan the border cells.
  2. Whenever a border cell is "O", run DFS from it.
  3. The DFS changes every reachable "O" into "#".
  4. After marking, scan the whole board:
    • Change remaining "O" to "X".
    • Change "#" back to "O".

The board is modified in-place.

Correctness

A cell marked "#" was reached by DFS starting from a border "O". Therefore, it is connected to the border through "O" cells. Such a cell cannot be part of a surrounded region, so changing it back to "O" is correct.

Any "O" left unmarked after the border DFS has no path to the border. If it had such a path, the DFS from that border-connected component would have reached it and marked it. Therefore, this remaining "O" belongs to a region fully enclosed away from the border, so flipping it to "X" is correct.

Every cell is either border-connected and preserved, or not border-connected and captured. Therefore, the algorithm produces exactly the required board.

Complexity

Let:

Symbol Meaning
m Number of rows
n Number of columns
Metric Value Why
Time O(m * n) Each cell is processed a constant number of times
Space O(m * n) DFS recursion stack can hold many cells in the worst case

The board itself is modified in-place.

Implementation

class Solution:
    def solve(self, board: list[list[str]]) -> None:
        m = len(board)
        n = len(board[0])

        def dfs(r: int, c: int) -> None:
            if r < 0 or r >= m or c < 0 or c >= n:
                return

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

            board[r][c] = "#"

            dfs(r + 1, c)
            dfs(r - 1, c)
            dfs(r, c + 1)
            dfs(r, c - 1)

        for r in range(m):
            dfs(r, 0)
            dfs(r, n - 1)

        for c in range(n):
            dfs(0, c)
            dfs(m - 1, c)

        for r in range(m):
            for c in range(n):
                if board[r][c] == "O":
                    board[r][c] = "X"
                elif board[r][c] == "#":
                    board[r][c] = "O"

Code Explanation

We first get the board dimensions:

m = len(board)
n = len(board[0])

The helper function marks all "O" cells connected to a starting cell:

def dfs(r: int, c: int) -> None:

If the position is outside the board, stop:

if r < 0 or r >= m or c < 0 or c >= n:
    return

If the cell is not "O", stop:

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

Otherwise, mark it safe:

board[r][c] = "#"

Then visit its four neighbors:

dfs(r + 1, c)
dfs(r - 1, c)
dfs(r, c + 1)
dfs(r, c - 1)

Next, we start DFS from the left and right borders:

for r in range(m):
    dfs(r, 0)
    dfs(r, n - 1)

Then from the top and bottom borders:

for c in range(n):
    dfs(0, c)
    dfs(m - 1, c)

Finally, we scan every cell:

if board[r][c] == "O":
    board[r][c] = "X"
elif board[r][c] == "#":
    board[r][c] = "O"

Remaining "O" cells are captured. Safe cells are restored.

Iterative BFS Version

Recursive DFS is clear, but Python recursion can be risky for a large 200 x 200 board.

An iterative BFS avoids recursion depth issues.

from collections import deque

class Solution:
    def solve(self, board: list[list[str]]) -> None:
        m = len(board)
        n = len(board[0])
        queue = deque()

        def add_if_border_o(r: int, c: int) -> None:
            if board[r][c] == "O":
                board[r][c] = "#"
                queue.append((r, c))

        for r in range(m):
            add_if_border_o(r, 0)
            add_if_border_o(r, n - 1)

        for c in range(n):
            add_if_border_o(0, c)
            add_if_border_o(m - 1, c)

        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

        while queue:
            r, c = queue.popleft()

            for dr, dc in directions:
                nr = r + dr
                nc = c + dc

                if nr < 0 or nr >= m or nc < 0 or nc >= n:
                    continue

                if board[nr][nc] != "O":
                    continue

                board[nr][nc] = "#"
                queue.append((nr, nc))

        for r in range(m):
            for c in range(n):
                if board[r][c] == "O":
                    board[r][c] = "X"
                elif board[r][c] == "#":
                    board[r][c] = "O"

For LeetCode, I would submit the BFS version in Python because it avoids recursion depth problems.

Testing

def run_tests():
    s = Solution()

    board = [
        ["X", "X", "X", "X"],
        ["X", "O", "O", "X"],
        ["X", "X", "O", "X"],
        ["X", "O", "X", "X"],
    ]
    s.solve(board)
    assert board == [
        ["X", "X", "X", "X"],
        ["X", "X", "X", "X"],
        ["X", "X", "X", "X"],
        ["X", "O", "X", "X"],
    ]

    board = [["X"]]
    s.solve(board)
    assert board == [["X"]]

    board = [["O"]]
    s.solve(board)
    assert board == [["O"]]

    board = [
        ["O", "O"],
        ["O", "O"],
    ]
    s.solve(board)
    assert board == [
        ["O", "O"],
        ["O", "O"],
    ]

    board = [
        ["X", "X", "X"],
        ["X", "O", "X"],
        ["X", "X", "X"],
    ]
    s.solve(board)
    assert board == [
        ["X", "X", "X"],
        ["X", "X", "X"],
        ["X", "X", "X"],
    ]

    print("all tests passed")

run_tests()

Test meaning:

Test Why
Standard example Captures only the enclosed region
Single "X" No change
Single "O" Border cell cannot be captured
All "O" board Every cell is border-connected
Center "O" surrounded by "X" Smallest captured region