Surrounded Regions

Problem Statement

Given an m x n board containing 'X' and 'O', capture all regions of 'O' that are surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region.

What to notice first

• Only 'O' regions that are NOT connected to the border can be captured.
• Use DFS/BFS from border to mark all border-connected 'O's as safe.
• Flip remaining unmarked 'O's to 'X'.

Examples

Input	Output	Explanation
[["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]	[["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]	Only the bottom-left O is surrounded

Constraints

• m == board.length
• n == board[i].length
• 1 <= m, n <= 200
• board[i][j] is 'X' or 'O'

Real-World Applications

Where this pattern appears

• Game development — flood fill with obstacles (Minesweeper).
• Image processing — connected component analysis with boundaries.
• Geographic analysis — identifying enclosed regions.

Complexity Comparison

Approach	Time	Space	Notes
DFS	O(m * n)	O(m * n)	Recursive exploration, intuitive
Union-Find	O(m * n * α(n))	O(m * n)	Disjoint sets, path compression

Which approach should you learn first?

• Pick DFS for most intuitive and straightforward solution.
• Pick Union-Find to understand disjoint set data structure.

Most Intuitive

DFS

O(m * n) time · O(m * n) space

Elegant

Union-Find

O(m * n * α(n)) time · O(m * n) space

Approach 1: DFS — Recommended

★ Recommended

Mark all border-connected ‘O’ regions from all four borders using DFS, then flip remaining ‘O’s to ‘X’s.

⏱ Time O(m * n) Visit each cell once 💾 Space O(m * n) Recursion stack

Pseudocode

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

    // Mark border-connected O's from all borders
    for each cell on border:
        if cell is 'O':
            dfs(board, r, c, rows, cols)

    // Flip unmarked O's to X's
    for each cell in board:
        if cell is 'O':
            cell = 'X'
        else if cell is '#':  // Marked O's
            cell = 'O'

Solution Code

Python

surrounded_regions_dfs.py

def solve_dfs(board: list[list[str]]) -> None:
    """
    DFS approach - mark border-connected O's, then flip remaining O's to X's.
    Time: O(m * n)
    Space: O(m * n)
    """
    if not board or not board[0]:
        return

    rows, cols = len(board), 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] = '#'  # Mark as border-connected
        dfs(r + 1, c)
        dfs(r - 1, c)
        dfs(r, c + 1)
        dfs(r, c - 1)

    # Mark border-connected O's
    for i in range(rows):
        if board[i][0] == 'O':
            dfs(i, 0)
        if board[i][cols - 1] == 'O':
            dfs(i, cols - 1)

    for j in range(cols):
        if board[0][j] == 'O':
            dfs(0, j)
        if board[rows - 1][j] == 'O':
            dfs(rows - 1, j)

    # Flip remaining O's to X's and restore marked cells
    for i in range(rows):
        for j in range(cols):
            if board[i][j] == 'O':
                board[i][j] = 'X'
            elif board[i][j] == '#':
                board[i][j] = 'O'

C++

surrounded_regions_dfs.cpp

class SurroundedRegionsDFS {
public:
    void solve(vector<vector<char>>& board) {
        /**
         * DFS approach - mark border-connected O's, then flip remaining O's.
         * Time: O(m * n)
         * Space: O(m * n)
         */
        if (board.empty() || board[0].empty()) return;

        int rows = board.size();
        int cols = board[0].size();

        // Mark border-connected O's
        for (int i = 0; i < rows; i++) {
            if (board[i][0] == 'O') dfs(board, i, 0);
            if (board[i][cols - 1] == 'O') dfs(board, i, cols - 1);
        }

        for (int j = 0; j < cols; j++) {
            if (board[0][j] == 'O') dfs(board, 0, j);
            if (board[rows - 1][j] == 'O') dfs(board, rows - 1, j);
        }

        // Flip and restore
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (board[i][j] == 'O') board[i][j] = 'X';
                else if (board[i][j] == '#') board[i][j] = 'O';
            }
        }
    }

private:
    void dfs(vector<vector<char>>& board, int r, int c) {
        if (r < 0 || r >= board.size() || c < 0 || c >= board[0].size() || board[r][c] != 'O')
            return;
        board[r][c] = '#';
        dfs(board, r + 1, c);
        dfs(board, r - 1, c);
        dfs(board, r, c + 1);
        dfs(board, r, c - 1);
    }
};

Java

SurroundedRegionsDFS.java

class SurroundedRegionsDFS {
    public void solve(char[][] board) {
        if (board == null || board.length == 0) return;

        int rows = board.length;
        int cols = board[0].length;

        // Mark border-connected O's
        for (int i = 0; i < rows; i++) {
            if (board[i][0] == 'O') dfs(board, i, 0);
            if (board[i][cols - 1] == 'O') dfs(board, i, cols - 1);
        }

        for (int j = 0; j < cols; j++) {
            if (board[0][j] == 'O') dfs(board, 0, j);
            if (board[rows - 1][j] == 'O') dfs(board, rows - 1, j);
        }

        // Flip and restore
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (board[i][j] == 'O') board[i][j] = 'X';
                else if (board[i][j] == '#') board[i][j] = 'O';
            }
        }
    }

    private void dfs(char[][] board, int r, int c) {
        if (r < 0 || r >= board.length || c < 0 || c >= board[0].length || board[r][c] != 'O')
            return;
        board[r][c] = '#';
        dfs(board, r + 1, c);
        dfs(board, r - 1, c);
        dfs(board, r, c + 1);
        dfs(board, r, c - 1);
    }
}

JavaScript

surrounded_regions_dfs.js

function solveDFS(board) {
    if (!board || board.length === 0) return;

    const rows = board.length;
    const cols = board[0].length;

    const dfs = (r, c) => {
        if (r < 0 || r >= rows || c < 0 || c >= cols || 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 (let i = 0; i < rows; i++) {
        if (board[i][0] === 'O') dfs(i, 0);
        if (board[i][cols - 1] === 'O') dfs(i, cols - 1);
    }

    for (let j = 0; j < cols; j++) {
        if (board[0][j] === 'O') dfs(0, j);
        if (board[rows - 1][j] === 'O') dfs(rows - 1, j);
    }

    for (let i = 0; i < rows; i++) {
        for (let j = 0; j < cols; j++) {
            if (board[i][j] === 'O') board[i][j] = 'X';
            else if (board[i][j] === '#') board[i][j] = 'O';
        }
    }
}

Rust

surrounded_regions_dfs.rs

impl Solution {
    pub fn solve(board: &mut Vec<Vec<char>>) {
        if board.is_empty() || board[0].is_empty() {
            return;
        }

        let rows = board.len();
        let cols = board[0].len();

        // Mark border-connected O's
        for i in 0..rows {
            if board[i][0] == 'O' {
                Self::dfs(board, i, 0, rows, cols);
            }
            if board[i][cols - 1] == 'O' {
                Self::dfs(board, i, cols - 1, rows, cols);
            }
        }

        for j in 0..cols {
            if board[0][j] == 'O' {
                Self::dfs(board, 0, j, rows, cols);
            }
            if board[rows - 1][j] == 'O' {
                Self::dfs(board, rows - 1, j, rows, cols);
            }
        }

        // Flip and restore
        for i in 0..rows {
            for j in 0..cols {
                if board[i][j] == 'O' {
                    board[i][j] = 'X';
                } else if board[i][j] == '#' {
                    board[i][j] = 'O';
                }
            }
        }
    }

    fn dfs(board: &mut Vec<Vec<char>>, r: usize, c: usize, rows: usize, cols: usize) {
        if r >= rows || c >= cols || board[r][c] != 'O' {
            return;
        }
        board[r][c] = '#';
        if r > 0 {
            Self::dfs(board, r - 1, c, rows, cols);
        }
        Self::dfs(board, r + 1, c, rows, cols);
        if c > 0 {
            Self::dfs(board, r, c - 1, rows, cols);
        }
        Self::dfs(board, r, c + 1, rows, cols);
    }
}

pub struct Solution;

Go

surrounded_regions_dfs.go

package main

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

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

    var dfs func(int, int)
    dfs = func(r, c int) {
        if r < 0 || r >= rows || c < 0 || c >= cols || 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 i := 0; i < rows; i++ {
        if board[i][0] == 'O' {
            dfs(i, 0)
        }
        if board[i][cols-1] == 'O' {
            dfs(i, cols-1)
        }
    }

    for j := 0; j < cols; j++ {
        if board[0][j] == 'O' {
            dfs(0, j)
        }
        if board[rows-1][j] == 'O' {
            dfs(rows-1, j)
        }
    }

    for i := 0; i < rows; i++ {
        for j := 0; j < cols; j++ {
            if board[i][j] == 'O' {
                board[i][j] = 'X'
            } else if board[i][j] == '#' {
                board[i][j] = 'O'
            }
        }
    }
}

Approach 2: Union-Find

✓ Simple

Create a virtual boundary node and union it with all border-connected ‘O’s. Flip ‘O’s that are not connected to boundary.

⏱ Time O(m * n * α(n)) Union operations with path compression 💾 Space O(m * n) Parent array + rank

Solution Code

Python

surrounded_regions_union_find.py

class UnionFind:
    def __init__(self, n: int):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x: int) -> int:
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x: int, y: int) -> None:
        px, py = self.find(x), self.find(y)
        if px == py:
            return
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1

def solve_union_find(board: list[list[str]]) -> None:
    """
    Union-Find approach - unite boundary with border-connected O's.
    Time: O(m * n * α(n))
    Space: O(m * n)
    """
    if not board or not board[0]:
        return

    rows, cols = len(board), len(board[0])
    uf = UnionFind(rows * cols + 1)
    boundary = rows * cols

    for i in range(rows):
        for j in range(cols):
            if board[i][j] == 'O':
                if i == 0 or i == rows - 1 or j == 0 or j == cols - 1:
                    uf.union(i * cols + j, boundary)
                else:
                    if i > 0 and board[i - 1][j] == 'O':
                        uf.union(i * cols + j, (i - 1) * cols + j)
                    if j > 0 and board[i][j - 1] == 'O':
                        uf.union(i * cols + j, i * cols + (j - 1))

    for i in range(rows):
        for j in range(cols):
            if uf.find(i * cols + j) != uf.find(boundary) and board[i][j] == 'O':
                board[i][j] = 'X'

C++

surrounded_regions_union_find.cpp

class UnionFind {
public:
    vector<int> parent, rank;

    UnionFind(int n) {
        parent.resize(n);
        rank.resize(n, 0);
        for (int i = 0; i < n; i++) parent[i] = i;
    }

    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }

    void unite(int x, int y) {
        int px = find(x), py = find(y);
        if (px == py) return;
        if (rank[px] < rank[py]) swap(px, py);
        parent[py] = px;
        if (rank[px] == rank[py]) rank[px]++;
    }
};

class SurroundedRegionsUnionFind {
public:
    void solve(vector<vector<char>>& board) {
        if (board.empty() || board[0].empty()) return;

        int rows = board.size();
        int cols = board[0].size();
        UnionFind uf(rows * cols + 1);
        int boundary = rows * cols;

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (board[i][j] == 'O') {
                    if (i == 0 || i == rows - 1 || j == 0 || j == cols - 1) {
                        uf.unite(i * cols + j, boundary);
                    } else {
                        if (i > 0 && board[i-1][j] == 'O') uf.unite(i*cols+j, (i-1)*cols+j);
                        if (j > 0 && board[i][j-1] == 'O') uf.unite(i*cols+j, i*cols+(j-1));
                    }
                }
            }
        }

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (uf.find(i * cols + j) != uf.find(boundary) && board[i][j] == 'O') {
                    board[i][j] = 'X';
                }
            }
        }
    }
};

Java

SurroundedRegionsUnionFind.java

class UnionFind {
    int[] parent, rank;

    UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
    }

    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }

    void unite(int x, int y) {
        int px = find(x), py = find(y);
        if (px == py) return;
        if (rank[px] < rank[py]) { int t = px; px = py; py = t; }
        parent[py] = px;
        if (rank[px] == rank[py]) rank[px]++;
    }
}

class SurroundedRegionsUnionFind {
    public void solve(char[][] board) {
        if (board == null || board.length == 0) return;

        int rows = board.length, cols = board[0].length;
        UnionFind uf = new UnionFind(rows * cols + 1);
        int boundary = rows * cols;

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (board[i][j] == 'O') {
                    if (i == 0 || i == rows - 1 || j == 0 || j == cols - 1) {
                        uf.unite(i * cols + j, boundary);
                    } else {
                        if (i > 0 && board[i-1][j] == 'O') uf.unite(i*cols+j, (i-1)*cols+j);
                        if (j > 0 && board[i][j-1] == 'O') uf.unite(i*cols+j, i*cols+(j-1));
                    }
                }
            }
        }

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (uf.find(i * cols + j) != uf.find(boundary) && board[i][j] == 'O') {
                    board[i][j] = 'X';
                }
            }
        }
    }
}

JavaScript

surrounded_regions_union_find.js

class UnionFind {
    constructor(n) {
        this.parent = Array.from({length: n}, (_, i) => i);
        this.rank = Array(n).fill(0);
    }

    find(x) {
        if (this.parent[x] !== x) {
            this.parent[x] = this.find(this.parent[x]);
        }
        return this.parent[x];
    }

    unite(x, y) {
        let px = this.find(x), py = this.find(y);
        if (px === py) return;
        if (this.rank[px] < this.rank[py]) [px, py] = [py, px];
        this.parent[py] = px;
        if (this.rank[px] === this.rank[py]) this.rank[px]++;
    }
}

function solveUnionFind(board) {
    if (!board || board.length === 0) return;

    const rows = board.length, cols = board[0].length;
    const uf = new UnionFind(rows * cols + 1);
    const boundary = rows * cols;

    for (let i = 0; i < rows; i++) {
        for (let j = 0; j < cols; j++) {
            if (board[i][j] === 'O') {
                if (i === 0 || i === rows - 1 || j === 0 || j === cols - 1) {
                    uf.unite(i * cols + j, boundary);
                } else {
                    if (i > 0 && board[i-1][j] === 'O') uf.unite(i*cols+j, (i-1)*cols+j);
                    if (j > 0 && board[i][j-1] === 'O') uf.unite(i*cols+j, i*cols+(j-1));
                }
            }
        }
    }

    for (let i = 0; i < rows; i++) {
        for (let j = 0; j < cols; j++) {
            if (uf.find(i * cols + j) !== uf.find(boundary) && board[i][j] === 'O') {
                board[i][j] = 'X';
            }
        }
    }
}

Rust

surrounded_regions_union_find.rs

struct UnionFind {
    parent: Vec<usize>,
    rank: Vec<usize>,
}

impl UnionFind {
    fn new(n: usize) -> Self {
        UnionFind {
            parent: (0..n).collect(),
            rank: vec![0; n],
        }
    }

    fn find(&mut self, x: usize) -> usize {
        if self.parent[x] != x {
            self.parent[x] = self.find(self.parent[x]);
        }
        self.parent[x]
    }

    fn unite(&mut self, x: usize, y: usize) {
        let mut px = self.find(x);
        let mut py = self.find(y);
        if px == py { return; }
        if self.rank[px] < self.rank[py] {
            std::mem::swap(&mut px, &mut py);
        }
        self.parent[py] = px;
        if self.rank[px] == self.rank[py] {
            self.rank[px] += 1;
        }
    }
}

impl Solution {
    pub fn solve(board: &mut Vec<Vec<char>>) {
        if board.is_empty() || board[0].is_empty() {
            return;
        }

        let rows = board.len();
        let cols = board[0].len();
        let mut uf = UnionFind::new(rows * cols + 1);
        let boundary = rows * cols;

        for i in 0..rows {
            for j in 0..cols {
                if board[i][j] == 'O' {
                    if i == 0 || i == rows - 1 || j == 0 || j == cols - 1 {
                        uf.unite(i * cols + j, boundary);
                    } else {
                        if i > 0 && board[i-1][j] == 'O' {
                            uf.unite(i*cols+j, (i-1)*cols+j);
                        }
                        if j > 0 && board[i][j-1] == 'O' {
                            uf.unite(i*cols+j, i*cols+(j-1));
                        }
                    }
                }
            }
        }

        for i in 0..rows {
            for j in 0..cols {
                if uf.find(i * cols + j) != uf.find(boundary) && board[i][j] == 'O' {
                    board[i][j] = 'X';
                }
            }
        }
    }
}

pub struct Solution;

Go

surrounded_regions_union_find.go

package main

type UnionFind struct {
    parent []int
    rank   []int
}

func NewUnionFind(n int) *UnionFind {
    uf := &UnionFind{
        parent: make([]int, n),
        rank:   make([]int, n),
    }
    for i := 0; i < n; i++ {
        uf.parent[i] = i
    }
    return uf
}

func (uf *UnionFind) Find(x int) int {
    if uf.parent[x] != x {
        uf.parent[x] = uf.Find(uf.parent[x])
    }
    return uf.parent[x]
}

func (uf *UnionFind) Unite(x, y int) {
    px, py := uf.Find(x), uf.Find(y)
    if px == py {
        return
    }
    if uf.rank[px] < uf.rank[py] {
        px, py = py, px
    }
    uf.parent[py] = px
    if uf.rank[px] == uf.rank[py] {
        uf.rank[px]++
    }
}

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

    rows, cols := len(board), len(board[0])
    uf := NewUnionFind(rows*cols + 1)
    boundary := rows * cols

    for i := 0; i < rows; i++ {
        for j := 0; j < cols; j++ {
            if board[i][j] == 'O' {
                if i == 0 || i == rows-1 || j == 0 || j == cols-1 {
                    uf.Unite(i*cols+j, boundary)
                } else {
                    if i > 0 && board[i-1][j] == 'O' {
                        uf.Unite(i*cols+j, (i-1)*cols+j)
                    }
                    if j > 0 && board[i][j-1] == 'O' {
                        uf.Unite(i*cols+j, i*cols+(j-1))
                    }
                }
            }
        }
    }

    for i := 0; i < rows; i++ {
        for j := 0; j < cols; j++ {
            if uf.Find(i*cols+j) != uf.Find(boundary) && board[i][j] == 'O' {
                board[i][j] = 'X'
            }
        }
    }
}

Related Problems

• Number of Islands ↗ Medium #200
• Flood Fill ↗ Easy #733
• Number of Enclaves ↗ Medium #1020

Interview Tips

Key trade-offs to discuss

• DFS vs Union-Find: DFS is simpler but uses implicit stack; Union-Find is more elegant for understanding disjoint sets.
• Border strategy: Key insight is to work from borders outward rather than interiors.
• Follow-up: Can you do this without modifying the board? Use a visited set instead.

← Previous
#200 Number of Islands Next
#133 Clone Graph →