LeetCode 130 - Surrounded Regions

The problem gives us a two dimensional grid called board, where each cell contains either 'X' or 'O'. The goal is to modify the board in place by capturing every region of 'O' cells that is completely surrounded by 'X'.

leetcodemediumarraydepth-first-searchbreadth-first-searchunion-findmatrix

LeetCode Problem 130

Difficulty: 🟡 Medium
Topics: Array, Depth-First Search, Breadth-First Search, Union-Find, Matrix

Solution

Problem Understanding

The problem gives us a two dimensional grid called board, where each cell contains either 'X' or 'O'. The goal is to modify the board in place by capturing every region of 'O' cells that is completely surrounded by 'X'.

A region is formed by connecting adjacent 'O' cells horizontally or vertically. Diagonal connections do not count. A region is considered surrounded if none of its cells touches the border of the board. If even one cell in the region lies on the edge, or is connected to an edge 'O', then the entire region must remain unchanged.

The important observation is that surrounded regions are exactly the 'O' regions that cannot reach the border. Any 'O' connected to a border 'O' is safe and should not be flipped.

The input is an m x n matrix where both dimensions are at most 200. That means the board can contain up to 40,000 cells. Because of this constraint, an algorithm that repeatedly scans the board or launches expensive searches from every cell may become too slow. A linear traversal solution, O(m * n), is the ideal target.

Several edge cases are important:

  • A single row or single column board cannot contain surrounded regions because every cell touches the border.
  • A board with only 'X' cells should remain unchanged.
  • A board with only 'O' cells should also remain unchanged because all cells are connected to the border.
  • Large connected regions require careful traversal to avoid revisiting cells repeatedly.

Approaches

Brute Force Approach

A straightforward idea is to examine every 'O' cell independently. For each unvisited 'O', we can perform a DFS or BFS to determine the full connected region. During traversal, we track whether the region touches the border.

If the region does not touch the border, we flip every cell in that region to 'X'. Otherwise, we leave the region unchanged.

This approach is correct because every region is explored completely before deciding whether it should be captured. However, the naive implementation can become inefficient if searches repeatedly revisit the same cells or if we launch a fresh traversal from many positions unnecessarily.

A poorly optimized brute force solution may approach O((m * n)^2) in the worst case.

Optimal Approach

The key insight is that we do not actually need to identify surrounded regions directly. Instead, we only need to identify the regions that are not surrounded.

Any 'O' connected to the border can never be captured. Therefore:

  1. Start from all border 'O' cells.
  2. Traverse all connected 'O' cells using DFS or BFS.
  3. Temporarily mark these safe cells.
  4. After traversal:
  • Any remaining 'O' must be surrounded, so flip it to 'X'.
  • Restore the temporarily marked safe cells back to 'O'.

This transforms the problem into a graph reachability problem. Rather than testing every region individually, we only protect the regions that are guaranteed to survive.

Approach Time Complexity Space Complexity Notes
Brute Force O((m * n)^2) O(m * n) Repeatedly explores regions from many cells
Optimal O(m * n) O(m * n) Marks border connected regions once

Algorithm Walkthrough

  1. First, check whether the board is empty. If the board has no rows or columns, there is nothing to process.
  2. Traverse all border cells. These include:
  • The first row
  • The last row
  • The first column
  • The last column
  1. Whenever a border cell contains 'O', launch a DFS or BFS from that cell. During traversal:

  • Mark every reachable 'O' as a temporary value such as 'T'

  • Continue exploring neighboring cells in four directions:

  • Up

  • Down

  • Left

  • Right

  1. After all border connected regions are marked, scan the entire board again.
  2. For each cell:
  • If the cell is still 'O', it means it was never connected to the border, so it is surrounded. Convert it to 'X'.
  • If the cell is 'T', restore it back to 'O' because it belongs to a safe region.
  1. The board is now fully updated in place.

Why it works

The algorithm relies on one important invariant:

Any 'O' connected to the border cannot be surrounded.

By starting traversal only from border 'O' cells, we mark exactly the cells that must survive. Every unmarked 'O' therefore belongs to a fully enclosed region and can safely be flipped to 'X'.

Because every cell is processed at most a constant number of times, the algorithm is both correct and efficient.

Python Solution

from typing import List

class Solution:
    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        
        if not board or not board[0]:
            return

        rows = len(board)
        cols = len(board[0])

        def dfs(r: int, c: int) -> None:
            if (
                r < 0 or r >= rows or
                c < 0 or c >= cols or
                board[r][c] != 'O'
            ):
                return

            board[r][c] = 'T'

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

        # Process left and right borders
        for r in range(rows):
            if board[r][0] == 'O':
                dfs(r, 0)

            if board[r][cols - 1] == 'O':
                dfs(r, cols - 1)

        # Process top and bottom borders
        for c in range(cols):
            if board[0][c] == 'O':
                dfs(0, c)

            if board[rows - 1][c] == 'O':
                dfs(rows - 1, c)

        # Final conversion
        for r in range(rows):
            for c in range(cols):
                if board[r][c] == 'O':
                    board[r][c] = 'X'
                elif board[r][c] == 'T':
                    board[r][c] = 'O'

The implementation begins by handling empty input safely. The dimensions of the board are stored in rows and cols for easier access.

The dfs helper function performs depth first traversal. It immediately stops when:

  • The position goes out of bounds
  • The cell is not 'O'

Whenever a valid 'O' is found, it is temporarily marked as 'T'. This prevents revisiting the same cell and distinguishes safe cells from surrounded ones.

The algorithm then scans all border cells. Every border 'O' launches a DFS traversal that marks all connected safe cells.

After all safe regions are identified, the board is scanned one final time:

  • Remaining 'O' cells are surrounded and flipped to 'X'
  • Temporary 'T' cells are restored back to 'O'

This satisfies the in place modification requirement because no separate board is created.

Go Solution

func solve(board [][]byte) {
    if len(board) == 0 || len(board[0]) == 0 {
        return
    }

    rows := len(board)
    cols := len(board[0])

    var dfs func(int, int)

    dfs = func(r int, c int) {
        if r < 0 || r >= rows || c < 0 || c >= cols || board[r][c] != 'O' {
            return
        }

        board[r][c] = 'T'

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

    // Process left and right borders
    for r := 0; r < rows; r++ {
        if board[r][0] == 'O' {
            dfs(r, 0)
        }

        if board[r][cols-1] == 'O' {
            dfs(r, cols-1)
        }
    }

    // Process top and bottom borders
    for c := 0; c < cols; c++ {
        if board[0][c] == 'O' {
            dfs(0, c)
        }

        if board[rows-1][c] == 'O' {
            dfs(rows-1, c)
        }
    }

    // Final conversion
    for r := 0; r < rows; r++ {
        for c := 0; c < cols; c++ {
            if board[r][c] == 'O' {
                board[r][c] = 'X'
            } else if board[r][c] == 'T' {
                board[r][c] = 'O'
            }
        }
    }
}

The Go solution follows exactly the same algorithmic structure as the Python implementation. One difference is that the board uses [][]byte rather than strings for individual characters. This allows direct in place modification of cells.

Go also requires explicit declaration of the recursive function variable before assigning the closure to it. Other than syntax differences, the traversal and marking logic remain identical.

Worked Examples

Example 1

Input:

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

Initial board:

Row State
0 X X X X
1 X O O X
2 X X O X
3 X O X X

The algorithm first scans the border.

Border cells containing 'O':

  • (3, 1)

DFS starts from (3, 1).

Board after marking safe region:

Row State
0 X X X X
1 X O O X
2 X X O X
3 X T X X

Now the algorithm scans the full board.

All remaining 'O' cells are surrounded:

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

These are flipped to 'X'.

Temporary 'T' is restored to 'O'.

Final board:

Row State
0 X X X X
1 X X X X
2 X X X X
3 X O X X

Example 2

Input:

[
  ["X"]
]

The board contains only one cell.

Since the cell is already 'X', nothing changes.

Final board:

[
  ["X"]
]

Complexity Analysis

Measure Complexity Explanation
Time O(m * n) Every cell is visited at most a constant number of times
Space O(m * n) Recursive DFS stack can grow to the size of the board

The board traversal itself is linear because each cell transitions through states at most once. The DFS recursion depth may become large if the board contains one massive connected region of 'O' cells, which is why the auxiliary space complexity is also O(m * n) in the worst case.

Test Cases

from typing import List

class Solution:
    def solve(self, board: List[List[str]]) -> None:
        if not board or not board[0]:
            return

        rows = len(board)
        cols = len(board[0])

        def dfs(r: int, c: int) -> None:
            if (
                r < 0 or r >= rows or
                c < 0 or c >= cols or
                board[r][c] != 'O'
            ):
                return

            board[r][c] = 'T'

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

        for r in range(rows):
            if board[r][0] == 'O':
                dfs(r, 0)

            if board[r][cols - 1] == 'O':
                dfs(r, cols - 1)

        for c in range(cols):
            if board[0][c] == 'O':
                dfs(0, c)

            if board[rows - 1][c] == 'O':
                dfs(rows - 1, c)

        for r in range(rows):
            for c in range(cols):
                if board[r][c] == 'O':
                    board[r][c] = 'X'
                elif board[r][c] == 'T':
                    board[r][c] = 'O'

sol = Solution()

# Example 1
board = [
    ["X","X","X","X"],
    ["X","O","O","X"],
    ["X","X","O","X"],
    ["X","O","X","X"]
]
sol.solve(board)
assert board == [
    ["X","X","X","X"],
    ["X","X","X","X"],
    ["X","X","X","X"],
    ["X","O","X","X"]
]  # standard surrounded region case

# Example 2
board = [["X"]]
sol.solve(board)
assert board == [["X"]]  # single X cell

# Single O cell
board = [["O"]]
sol.solve(board)
assert board == [["O"]]  # border O should survive

# All O board
board = [
    ["O","O"],
    ["O","O"]
]
sol.solve(board)
assert board == [
    ["O","O"],
    ["O","O"]
]  # all connected to border

# Fully surrounded center
board = [
    ["X","X","X"],
    ["X","O","X"],
    ["X","X","X"]
]
sol.solve(board)
assert board == [
    ["X","X","X"],
    ["X","X","X"],
    ["X","X","X"]
]  # center region captured

# Narrow single row
board = [["O","O","X","O"]]
sol.solve(board)
assert board == [["O","O","X","O"]]  # no surrounded regions possible

# Narrow single column
board = [
    ["O"],
    ["X"],
    ["O"]
]
sol.solve(board)
assert board == [
    ["O"],
    ["X"],
    ["O"]
]  # border connected vertically

# Complex mixed case
board = [
    ["X","O","X","X"],
    ["O","O","X","O"],
    ["X","O","O","X"],
    ["X","X","X","X"]
]
sol.solve(board)
assert board == [
    ["X","O","X","X"],
    ["O","O","X","O"],
    ["X","O","O","X"],
    ["X","X","X","X"]
]  # all O cells connected to border
Test Why
Standard surrounded region Verifies basic capture behavior
Single X cell Smallest possible board
Single O cell Border connected cell must survive
All O board Ensures border propagation works correctly
Fully surrounded center Validates capture of enclosed region
Single row No interior cells exist
Single column Vertical edge connectivity
Complex mixed case Tests multi direction connectivity

Edge Cases

Single Row or Single Column

Boards with only one row or one column are important because every cell lies on the border. A naive implementation might incorrectly attempt to capture internal cells even though no true interior exists.

The algorithm handles this naturally because all 'O' cells are discovered during the border traversal phase and marked as safe.

Large Connected Border Region

A board may contain a massive region of 'O' cells connected indirectly to the border through a long path. A buggy solution might only preserve border cells themselves instead of preserving the entire connected component.

The DFS traversal correctly propagates through all connected 'O' cells, ensuring the whole region survives.

Completely Enclosed Island

A region entirely surrounded by 'X' cells is the main capture case. The danger here is accidentally preserving cells because of incomplete traversal or incorrect neighbor checks.

Since the algorithm only preserves border reachable cells, enclosed regions are never marked safe. They remain 'O' during the marking phase and are later flipped to 'X' during the final scan.