130. Surrounded Regions (Medium)

Problem

Given an m × n board of 'X' and 'O', capture all regions of 'O' that are 4-directionally surrounded by 'X' (flip them to 'X'). A region is surrounded if no cell in it lies on the border.

Modify the board in place.

Example

• Input:

  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

LeetCode 130 · Link · Medium

Try it yourself

Python

▶ Run Python ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Brute force, DFS from each O to check if surrounded

Swift

final class Solution {
    func solve(_ board: inout [[Character]]) {
        let rows = board.count, cols = board[0].count
        var visited = Array(repeating: Array(repeating: false, count: cols), count: rows)
        let directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        for startRow in 0..<rows {
            for startCol in 0..<cols where board[startRow][startCol] == "O" && !visited[startRow][startCol] {
                var stack = [(startRow, startCol)], region: [(Int, Int)] = []
                visited[startRow][startCol] = true
                var touchesBorder = false
                while let (row, col) = stack.popLast() {
                    region.append((row, col))
                    if row == 0 || row == rows - 1 || col == 0 || col == cols - 1 { touchesBorder = true }
                    for (dr, dc) in directions {
                        let nr = row + dr, nc = col + dc
                        if nr >= 0 && nr < rows && nc >= 0 && nc < cols && board[nr][nc] == "O" && !visited[nr][nc] {
                            visited[nr][nc] = true; stack.append((nr, nc))
                        }
                    }
                }
                if !touchesBorder { for (row, col) in region { board[row][col] = "X" } }
            }
        }
    }
}

For each O, DFS to see if the component touches the border. If not, flip them all to X.

Complexity

• Time: $O(m*n)$, driven by total component work across all cells.
• Space: $O(m*n)$ for the visited set and the done set.

Works but it’s awkward to implement the “touches border” flag cleanly.

Approach 2: Reverse DFS from borders (optimal)

Flip the problem: any O that’s reachable from a border O is not surrounded. Temporarily mark those border-connected Os with a sentinel (e.g., 'T'). After the scan, flip every remaining O to X, then flip T back to O.

Python

def solve(board):
    if not board:                              # L1: O(1) guard
        return
    rows, cols = len(board), len(board[0])    # L2: O(1)

    def dfs(r, c):
        if not (0 <= r < rows and 0 <= c < cols) or board[r][c] != 'O':
            return                             # L3: O(1) base case
        board[r][c] = 'T'                     # L4: O(1) mark sentinel
        dfs(r + 1, c); dfs(r - 1, c); dfs(r, c + 1); dfs(r, c - 1)  # L5: recurse 4 neighbors

    for c in range(cols):
        dfs(0, c); dfs(rows - 1, c)           # L6: seed top and bottom rows
    for r in range(rows):
        dfs(r, 0); dfs(r, cols - 1)           # L7: seed left and right cols

    for r in range(rows):
        for c in range(cols):                  # L8: O(m*n) final sweep
            if board[r][c] == 'O':
                board[r][c] = 'X'             # L9: O(1) flip interior O
            elif board[r][c] == 'T':
                board[r][c] = 'O'             # L10: O(1) restore border O

TypeScript

function solve(board: string[][]): void {
    if (!board.length) return;                 // L1: O(1) guard
    const rows = board.length, cols = board[0].length;  // L2: O(1)

    function dfs(r: number, c: number): void {
        if (r < 0 || r >= rows || c < 0 || c >= cols || board[r][c] !== 'O') return;  // L3
        board[r][c] = 'T';                     // L4: O(1) mark sentinel
        dfs(r + 1, c); dfs(r - 1, c); dfs(r, c + 1); dfs(r, c - 1);  // L5: recurse
    }

    for (let c = 0; c < cols; c++) {
        dfs(0, c); dfs(rows - 1, c);           // L6: seed top and bottom rows
    }
    for (let r = 0; r < rows; r++) {
        dfs(r, 0); dfs(r, cols - 1);           // L7: seed left and right cols
    }

    for (let r = 0; r < rows; r++) {
        for (let c = 0; c < cols; c++) {       // L8: O(m*n) final sweep
            if (board[r][c] === 'O') board[r][c] = 'X';       // L9: flip interior O
            else if (board[r][c] === 'T') board[r][c] = 'O';  // L10: restore border O
        }
    }
}

Swift

final class Solution {
    func solve(_ board: inout [[Character]]) {
        let rows = board.count, cols = board[0].count
        func mark(_ row: Int, _ col: Int) {
            if row < 0 || row >= rows || col < 0 || col >= cols || board[row][col] != "O" { return }
            board[row][col] = "E"
            mark(row + 1, col); mark(row - 1, col); mark(row, col + 1); mark(row, col - 1)
        }
        for row in 0..<rows { mark(row, 0); mark(row, cols - 1) }
        for col in 0..<cols { mark(0, col); mark(rows - 1, col) }
        for row in 0..<rows {
            for col in 0..<cols { board[row][col] = board[row][col] == "E" ? "O" : "X" }
        }
    }
}

Where the time goes, line by line

Variables: m = grid rows, n = grid cols.

Line	Per-call cost	Times executed	Contribution
L6 (seed top/bottom)	$O(1)$	2*n	$O(n)$
L7 (seed left/right)	$O(1)$	2*m	$O(m)$
L5 (DFS recursion)	$O(1)$ per cell	at most m*n total	$O(m*n)$ ← dominates
L8-L10 (final sweep)	$O(1)$	m*n	$O(m*n)$

Complexity

• Time: $O(m*n)$, driven by L5/L8 (DFS traversal + final sweep).
• Space: $O(m*n)$ recursion stack in the worst case (a board full of O’s causes a chain of depth m*n).

Approach 3: BFS variant of Approach 2

Same idea with a queue, prefer when recursion depth is a concern.

Python

from collections import deque

def solve(board):
    if not board:                              # L1: O(1) guard
        return
    rows, cols = len(board), len(board[0])    # L2: O(1)

    def bfs(start_r, start_c):
        if board[start_r][start_c] != 'O':
            return                             # L3: O(1) early exit
        q = deque([(start_r, start_c)])        # L4: O(1) init queue
        board[start_r][start_c] = 'T'         # L5: O(1) mark start
        while q:                               # L6: loop until queue empty
            r, c = q.popleft()                 # L7: O(1) dequeue
            for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] == 'O':
                    board[nr][nc] = 'T'
                    q.append((nr, nc))         # L8: O(1) enqueue neighbor

    for c in range(cols):
        bfs(0, c); bfs(rows - 1, c)           # L9: seed top and bottom rows
    for r in range(rows):
        bfs(r, 0); bfs(r, cols - 1)           # L10: seed left and right cols

    for r in range(rows):
        for c in range(cols):                  # L11: O(m*n) final sweep
            if board[r][c] == 'O':
                board[r][c] = 'X'             # L12: O(1)
            elif board[r][c] == 'T':
                board[r][c] = 'O'             # L13: O(1)

TypeScript

function solve(board: string[][]): void {
    if (!board.length) return;
    const rows = board.length, cols = board[0].length;

    function bfs(startR: number, startC: number): void {
        if (board[startR][startC] !== 'O') return;
        const q: [number, number][] = [[startR, startC]];
        board[startR][startC] = 'T';
        let head = 0;
        while (head < q.length) {
            const [r, c] = q[head++];
            for (const [dr, dc] of [[1,0],[-1,0],[0,1],[0,-1]]) {
                const nr = r + dr, nc = c + dc;
                if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && board[nr][nc] === 'O') {
                    board[nr][nc] = 'T';
                    q.push([nr, nc]);
                }
            }
        }
    }

    for (let c = 0; c < cols; c++) { bfs(0, c); bfs(rows - 1, c); }
    for (let r = 0; r < rows; r++) { bfs(r, 0); bfs(r, cols - 1); }

    for (let r = 0; r < rows; r++)
        for (let c = 0; c < cols; c++) {
            if (board[r][c] === 'O') board[r][c] = 'X';
            else if (board[r][c] === 'T') board[r][c] = 'O';
        }
}

Swift

final class Solution {
    func solve(_ board: inout [[Character]]) {
        let rows = board.count, cols = board[0].count
        var queue: [(Int, Int)] = [], head = 0
        func enqueue(_ row: Int, _ col: Int) {
            if board[row][col] == "O" { board[row][col] = "E"; queue.append((row, col)) }
        }
        for row in 0..<rows { enqueue(row, 0); enqueue(row, cols - 1) }
        for col in 0..<cols { enqueue(0, col); enqueue(rows - 1, col) }
        for (dr, dc) in [(1, 0), (-1, 0), (0, 1), (0, -1)] {
            _ = dr; _ = dc
        }
        let directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        while head < queue.count {
            let (row, col) = queue[head]; head += 1
            for (dr, dc) in directions {
                let nr = row + dr, nc = col + dc
                if nr >= 0 && nr < rows && nc >= 0 && nc < cols && board[nr][nc] == "O" {
                    board[nr][nc] = "E"; queue.append((nr, nc))
                }
            }
        }
        for row in 0..<rows {
            for col in 0..<cols { board[row][col] = board[row][col] == "E" ? "O" : "X" }
        }
    }
}

Complexity

• Time: $O(m*n)$, driven by BFS traversal + final sweep.
• Space: $O(m*n)$ for the queue in the worst case.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Summary

Approach	Time	Space
DFS + border-touch flag	$O(m*n)$	$O(m*n)$
Reverse DFS from borders	$O(m*n)$	$O(m*n)$
Reverse BFS from borders	$O(m*n)$	$O(m*n)$

Same “reverse direction from boundary” trick as Pacific Atlantic, the cleanest version of the problem.

Test cases

Python

# Quick smoke tests, paste into a REPL or save as test_130.py and run.
# Uses the canonical implementation (Approach 2: reverse DFS from borders).

def solve(board):
    if not board:
        return
    rows, cols = len(board), len(board[0])

    def dfs(r, c):
        if not (0 <= r < rows and 0 <= 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 c in range(cols):
        dfs(0, c); dfs(rows - 1, c)
    for r in range(rows):
        dfs(r, 0); dfs(r, cols - 1)

    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'

def _run_tests():
    # Example from the problem statement
    b = [['X','X','X','X'],
         ['X','O','O','X'],
         ['X','X','O','X'],
         ['X','O','X','X']]
    solve(b)
    assert b == [['X','X','X','X'],
                 ['X','X','X','X'],
                 ['X','X','X','X'],
                 ['X','O','X','X']]

    # All X's: nothing changes
    b2 = [['X','X'],['X','X']]
    solve(b2)
    assert b2 == [['X','X'],['X','X']]

    # Single cell O on border: stays O
    b3 = [['O']]
    solve(b3)
    assert b3 == [['O']]

    # O's entirely on the border: all stay
    b4 = [['O','O','O'],
          ['O','X','O'],
          ['O','O','O']]
    solve(b4)
    assert b4 == [['O','O','O'],
                  ['O','X','O'],
                  ['O','O','O']]

    # Interior O fully surrounded: gets captured
    b5 = [['X','X','X'],
          ['X','O','X'],
          ['X','X','X']]
    solve(b5)
    assert b5 == [['X','X','X'],
                  ['X','X','X'],
                  ['X','X','X']]

    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

TypeScript

function solve(board: string[][]): void {
    if (!board.length) return;
    const rows = board.length, cols = board[0].length;

    function dfs(r: number, c: number): void {
        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);
    }

    for (let c = 0; c < cols; c++) { dfs(0, c); dfs(rows-1, c); }
    for (let r = 0; r < rows; r++) { dfs(r, 0); dfs(r, cols-1); }
    for (let r = 0; r < rows; r++)
        for (let c = 0; c < cols; c++) {
            if (board[r][c] === 'O') board[r][c] = 'X';
            else if (board[r][c] === 'T') board[r][c] = 'O';
        }
}

const b1 = [['X','X','X','X'],['X','O','O','X'],['X','X','O','X'],['X','O','X','X']];
solve(b1);
console.assert(JSON.stringify(b1) === JSON.stringify([['X','X','X','X'],['X','X','X','X'],['X','X','X','X'],['X','O','X','X']]));
const b2 = [['O']]; solve(b2); console.assert(b2[0][0] === 'O');
const b3 = [['X','X','X'],['X','O','X'],['X','X','X']];
solve(b3);
console.assert(b3[1][1] === 'X');
console.log("all tests pass");

Related data structures

• Arrays, board with sentinel mutation

Related concepts

• Flood Fill, the grid expansion pattern for connected cells that share a condition.
• DFS, the depth first traversal habit of following one branch before returning.