Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Surrounded Regions solution and explanation

MediumArrayBreadth-First SearchDepth-First SearchMatrix9 min read46.1% acceptanceUpdated 9 Apr 2026
Asked atMolocoAmazonMetaAdobeNutanixAnduril
+6 moreGoogleMicrosoftBloombergOracleUberTiktok
Practise Surrounded Regions
14:50
Surrounded Regions - Graph - Leetcode 130 - PythonNeetCode · 14:50 · 142K viewsWatch on YouTube
9 more videos on this problem
  1. Surrounded Regions - Graph - Leetcode 130 - PythonNeetCode · 14:50 · 142K views
  2. Surrounded Regions | Leetcode #130Techdose · 13:30 · 30K views
  3. LeetCode 130. Surrounded Regions (Algorithm Explained)Nick White · 6:35 · 23K views
  4. [Java] Leetcode 130. Surrounded Regions [Search #3]Eric Programming · 13:37 · 2K views
  5. LeetCode 130. Surrounded Regions Explained with Examples and Solutionhappygirlzt · 8:36 · 2K views
  6. Surrounded Regions | Leetcode 130 | Live coding session 🔥🔥🔥| DFS with a trickCoding Decoded · 9:46 · 1K views
  7. Surrounded Regions | LeetCode 130 DFS ExplainedDestination FAANG · 12:26 · 593 views
  8. Surrounded Regions | Day 17 | [June LeetCoding Challenge] [Leetcode #130] [2020]Algorithms Made Easy · 3:17 · 526 views
  9. LeetCode 130 | Surrounded Regions | Union Find | JavaSleepy Cracker · 10:57 · 383 views
  10. LeetCode 130. Surrounded Regions | Medium | Algorithm Explained | C++Cherry Coding [IIT-G] · 7:49 · 328 views

The problem

You are given an m x n matrix board containing letters 'X' and 'O', capture regions that are surrounded:

  • Connect: A cell is connected to adjacent cells horizontally or vertically.
  • Region: To form a region connect every 'O' cell.
  • Surround: The region is surrounded with 'X' cells if you can connect the region with 'X' cells and none of the region cells are on the edge of the board.

To capture a surrounded region, replace all 'O's with 'X's in-place within the original board. You do not need to return anything.

Example 1:

Input: board = [["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"]]

Explanation:

In the above diagram, the bottom region is not captured because it is on the edge of the board and cannot be surrounded.

Example 2:

Input: board = [["X"]]

Output: [["X"]]

Constraints:

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

Approach overview

Problem Overview: You are given an m x n board filled with 'X' and 'O'. Any region of 'O' completely surrounded by 'X' must be captured by flipping all its cells to 'X'. The catch: if an 'O' is connected to the border, that entire region cannot be captured.

Approach 1: Depth-First Search (DFS) from Borders (O(m*n) time, O(m*n) space)

The key insight is that only regions fully enclosed by 'X' should be flipped. Instead of checking every region individually, mark the safe cells first. Iterate over the grid borders and start a depth-first search whenever you find an 'O'. During DFS, mark all connected 'O' cells as temporary (for example '#') to indicate they are connected to the border and must remain unchanged.

After the DFS traversal finishes, iterate through the entire board. Any remaining 'O' must be surrounded, so flip it to 'X'. Convert the temporary marks back to 'O'. Each cell is visited at most once, giving O(m*n) time complexity with recursion stack space up to O(m*n) in the worst case. This approach fits naturally with problems involving matrix traversal and connected components.

Approach 2: Breadth-First Search (BFS) Flood Fill (O(m*n) time, O(m*n) space)

This approach uses a queue instead of recursion. Scan the borders and push all border 'O' cells into a queue. Perform a breadth-first search, expanding in four directions (up, down, left, right). Every reachable 'O' gets marked as safe using the same temporary marker.

Once BFS finishes, run a final pass across the grid. Flip all remaining 'O' cells to 'X' and restore the marked cells. BFS avoids recursion depth issues and can be easier to control in languages where stack overflow is a concern. The algorithm still processes each cell once, resulting in O(m*n) time and queue space up to O(m*n).

Approach 3: Union-Find (Disjoint Set) (O(m*n * α(n)) time, O(m*n) space)

Another option models the board as a graph. Each 'O' cell belongs to a disjoint set. A virtual node represents the border. Union all border 'O' cells with this node, then union adjacent 'O' cells together. After building the structure, any cell not connected to the border node must be surrounded and can be flipped.

This method works well for connectivity problems but adds extra overhead and implementation complexity compared to DFS or BFS.

Recommended for interviews: DFS from border cells is the expected solution. It demonstrates that you recognized the key insight: protected regions are those connected to the boundary. BFS is equally valid and often preferred when recursion limits are a concern. Explaining why checking borders first simplifies the problem signals strong graph and grid traversal intuition.

Approach 1: Depth-First Search (DFS)

This approach uses Depth-First Search (DFS) to mark all 'O's connected to the boundary as safe. These 'O's cannot be converted to 'X' because they are on the boundary or connected to the boundary. The rest of the 'O's can be safely converted to 'X'.

class Solution:
    def solve(self, board: List[List[str]]) -> None:
        def dfs(row, col):
            if row < 0 or col < 0 or row >= len(board) or col >= len(board[0]) or board[row][col] != 'O':
                return
            board[row][col] = 'A'
            dfs(row - 1, col)
            dfs(row + 1, col)
            dfs(row, col - 1)
            dfs(row, col + 1)

        m, n = len(board), len(board[0])
        if m == 0:
            return

        for i in range(m):
            if board[i][0] == 'O':
                dfs(i, 0)
            if board[i][n - 1] == 'O':
                dfs(i, n - 1)

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

        for i in range(m):
            for j in range(n):
                if board[i][j] == 'O':
                    board[i][j] = 'X'
                elif board[i][j] == 'A':
                    board[i][j] = 'O'
class Solution {
    private void dfs(char[][] board, int row, int col, int m, int n) {
        if (row < 0 || col < 0 || row >= m || col >= n || board[row][col] != 'O') return;
        board[row][col] = 'A';
        dfs(board, row - 1, col, m, n);
        dfs(board, row + 1, col, m, n);
        dfs(board, row, col - 1, m, n);
        dfs(board, row, col + 1, m, n);
    }
    
    public void solve(char[][] board) {
        int m = board.length;
        if (m == 0) return;
        int n = board[0].length;

        for (int i = 0; i < m; i++) {
            if (board[i][0] == 'O') dfs(board, i, 0, m, n);
            if (board[i][n - 1] == 'O') dfs(board, i, n - 1, m, n);
        }
        
        for (int j = 0; j < n; j++) {
            if (board[0][j] == 'O') dfs(board, 0, j, m, n);
            if (board[m - 1][j] == 'O') dfs(board, m - 1, j, m, n);
        }
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'O') board[i][j] = 'X';
                if (board[i][j] == 'A') board[i][j] = 'O';
            }
        }
    }
}
#include <vector>
using namespace std;

void dfs(vector<vector<char>>& board, int row, int col, int m, int n) {
    if (row < 0 || col < 0 || row >= m || col >= n || board[row][col] != 'O') return;
    board[row][col] = 'A';
    dfs(board, row - 1, col, m, n);
    dfs(board, row + 1, col, m, n);
    dfs(board, row, col - 1, m, n);
    dfs(board, row, col + 1, m, n);
}

void solve(vector<vector<char>>& board) {
    int m = board.size();
    if (m == 0) return;
    int n = board[0].size();

    for (int i = 0; i < m; ++i) {
        if (board[i][0] == 'O') dfs(board, i, 0, m, n);
        if (board[i][n - 1] == 'O') dfs(board, i, n - 1, m, n);
    }

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

    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (board[i][j] == 'O') board[i][j] = 'X';
            if (board[i][j] == 'A') board[i][j] = 'O';
        }
    }
}
var solve = function(board) {
    function dfs(row, col) {
        if (row < 0 || col < 0 || row >= m || col >= n || board[row][col] !== 'O') return;
        board[row][col] = 'A';
        dfs(row - 1, col);
        dfs(row + 1, col);
        dfs(row, col - 1);
        dfs(row, col + 1);
    }

    let m = board.length;
    if (m === 0) return;
    let n = board[0].length;

    for (let i = 0; i < m; i++) {
        if (board[i][0] === 'O') dfs(i, 0);
        if (board[i][n - 1] === 'O') dfs(i, n - 1);
    }

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

    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (board[i][j] === 'O') board[i][j] = 'X';
            if (board[i][j] === 'A') board[i][j] = 'O';
        }
    }
};
#include <stdio.h>

void dfs(char** board, int row, int col, int m, int n) {
    if (row < 0 || col < 0 || row >= m || col >= n || board[row][col] != 'O') {
        return;
    }
    board[row][col] = 'A';
    dfs(board, row - 1, col, m, n);
    dfs(board, row + 1, col, m, n);
    dfs(board, row, col - 1, m, n);
    dfs(board, row, col + 1, m, n);
}

void solve(char** board, int boardSize, int* boardColSize) {
    int m = boardSize;
    int n = boardColSize[0];
    if (m == 0) return;

    for (int i = 0; i < m; i++) {
        if (board[i][0] == 'O') dfs(board, i, 0, m, n);
        if (board[i][n - 1] == 'O') dfs(board, i, n - 1, m, n);
    }
    for (int j = 0; j < n; j++) {
        if (board[0][j] == 'O') dfs(board, 0, j, m, n);
        if (board[m - 1][j] == 'O') dfs(board, m - 1, j, m, n);
    }
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (board[i][j] == 'O') board[i][j] = 'X';
            if (board[i][j] == 'A') board[i][j] = 'O';
        }
    }
}
public class Solution {
    private void Dfs(char[][] board, int row, int col, int m, int n) {
        if (row < 0 || col < 0 || row >= m || col >= n || board[row][col] != 'O') return;
        board[row][col] = 'A';
        Dfs(board, row - 1, col, m, n);
        Dfs(board, row + 1, col, m, n);
        Dfs(board, row, col - 1, m, n);
        Dfs(board, row, col + 1, m, n);
    }

    public void Solve(char[][] board) {
        int m = board.Length;
        if (m == 0) return;
        int n = board[0].Length;

        for (int i = 0; i < m; i++) {
            if (board[i][0] == 'O') Dfs(board, i, 0, m, n);
            if (board[i][n - 1] == 'O') Dfs(board, i, n - 1, m, n);
        }

        for (int j = 0; j < n; j++) {
            if (board[0][j] == 'O') Dfs(board, 0, j, m, n);
            if (board[m - 1][j] == 'O') Dfs(board, m - 1, j, m, n);
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'O') board[i][j] = 'X';
                if (board[i][j] == 'A') board[i][j] = 'O';
            }
        }
    }
}

In the Python solution, dfs marks border-connected 'O's with 'A'. After processing the board, it swaps 'O's with 'X's and 'A's with 'O's to achieve the desired output.

Complexity

Time Complexity: O(m * n), Space Complexity: O(m * n) for the DFS recursion stack.

Try this approach in the editor

Approach 2: Breadth-First Search (BFS)

This approach uses Breadth-First Search (BFS) utilizing a queue to explore 'O's connected to the boundary. This approach is iterative and avoids deep recursion, keeping the method stack usage low.

class Solution:
    def solve(self, board: List[List[str]]) -> None:
        from collections import deque
        
        def bfs(row, col):
            q = deque([(row, col)])
            board[row][col] = 'A'
            while q:
                cur_row, cur_col = q.popleft()
                for new_row, new_col in [(cur_row-1, cur_col), (cur_row+1, cur_col), (cur_row, cur_col-1), (cur_row, cur_col+1)]:
                    if 0 <= new_row < len(board) and 0 <= new_col < len(board[0]) and board[new_row][new_col] == 'O':
                        board[new_row][new_col] = 'A'
                        q.append((new_row, new_col))

        m, n = len(board), len(board[0])
        if not board:
            return

        for i in range(m):
            if board[i][0] == 'O':
                bfs(i, 0)
            if board[i][n - 1] == 'O':
                bfs(i, n - 1)

        for j in range(n):
            if board[0][j] == 'O':
                bfs(0, j)
            if board[m - 1][j] == 'O':
                bfs(m - 1, j)

        for i in range(m):
            for j in range(n):
                if board[i][j] == 'O':
                    board[i][j] = 'X'
                elif board[i][j] == 'A':
                    board[i][j] = 'O'
import java.util.LinkedList;
import java.util.Queue;

public class Solution {
    private void bfs(char[][] board, int row, int col, int m, int n) {
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{row, col});
        board[row][col] = 'A';

        while (!q.isEmpty()) {
            int[] current = q.poll();
            int r = current[0], c = current[1];

            int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
            for (int[] dir : directions) {
                int newRow = r + dir[0], newCol = c + dir[1];
                if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && board[newRow][newCol] == 'O') {
                    board[newRow][newCol] = 'A';
                    q.offer(new int[]{newRow, newCol});
                }
            }
        }
    }

    public void solve(char[][] board) {
        int m = board.length;
        if (m == 0) return;
        int n = board[0].length;

        for (int i = 0; i < m; i++) {
            if (board[i][0] == 'O') bfs(board, i, 0, m, n);
            if (board[i][n - 1] == 'O') bfs(board, i, n - 1, m, n);
        }

        for (int j = 0; j < n; j++) {
            if (board[0][j] == 'O') bfs(board, 0, j, m, n);
            if (board[m - 1][j] == 'O') bfs(board, m - 1, j, m, n);
        }

        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'O') board[i][j] = 'X';
                if (board[i][j] == 'A') board[i][j] = 'O';
            }
    }
}
#include <vector>
#include <queue>
using namespace std;

void bfs(vector<vector<char>>& board, int row, int col, int m, int n) {
    queue<pair<int, int>> q;
    q.push({row, col});
    board[row][col] = 'A';

    while (!q.empty()) {
        auto [curRow, curCol] = q.front();
        q.pop();

        int directions[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        for (const auto& dir : directions) {
            int newRow = curRow + dir[0];
            int newCol = curCol + dir[1];
            if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && board[newRow][newCol] == 'O') {
                board[newRow][newCol] = 'A';
                q.push({newRow, newCol});
            }
        }
    }
}

void solve(vector<vector<char>>& board) {
    int m = board.size();
    if (m == 0) return;
    int n = board[0].size();

    for (int i = 0; i < m; ++i) {
        if (board[i][0] == 'O') bfs(board, i, 0, m, n);
        if (board[i][n - 1] == 'O') bfs(board, i, n - 1, m, n);
    }

    for (int j = 0; j < n; ++j) {
        if (board[0][j] == 'O') bfs(board, 0, j, m, n);
        if (board[m - 1][j] == 'O') bfs(board, m - 1, j, m, n);
    }
    
    for (int i = 0; i < m; ++i)
        for (int j = 0; j < n; ++j) {
            if (board[i][j] == 'O') board[i][j] = 'X';
            if (board[i][j] == 'A') board[i][j] = 'O';
        }
}
var solve = function(board) {
    function bfs(row, col) {
        let q = [];
        q.push([row, col]);
        board[row][col] = 'A';

        while (q.length) {
            let [curRow, curCol] = q.shift();
            for (let [rDiff, cDiff] of [[1,0], [-1,0], [0,1], [0,-1]]) {
                let newRow = curRow + rDiff, newCol = curCol + cDiff;
                if (newRow >= 0 && newRow < board.length && newCol >= 0 && newCol < board[0].length && board[newRow][newCol] === 'O') {
                    board[newRow][newCol] = 'A';
                    q.push([newRow, newCol]);
                }
            }
        }
    }

    let m = board.length;
    if (m === 0) return;
    let n = board[0].length;

    for (let i = 0; i < m; i++) {
        if (board[i][0] === 'O') bfs(i, 0);
        if (board[i][n - 1] === 'O') bfs(i, n - 1);
    }

    for (let j = 0; j < n; j++) {
        if (board[0][j] === 'O') bfs(0, j);
        if (board[m - 1][j] === 'O') bfs(m - 1, j);
    }

    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (board[i][j] === 'O') board[i][j] = 'X';
            if (board[i][j] === 'A') board[i][j] = 'O';
        }
    }
};
#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int row, col;
} Node;

void bfs(char** board, int row, int col, int m, int n) {
    Node* queue = (Node*)malloc(sizeof(Node) * m * n);
    int front = 0, rear = 0;
    queue[rear++] = (Node){row, col};
    board[row][col] = 'A';

    while (front != rear) {
        Node cur = queue[front++];
        int directions[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        for (int i = 0; i < 4; i++) {
            int newRow = cur.row + directions[i][0];
            int newCol = cur.col + directions[i][1];
            if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && board[newRow][newCol] == 'O') {
                board[newRow][newCol] = 'A';
                queue[rear++] = (Node){newRow, newCol};
            }
        }
    }
    free(queue);
}

void solve(char** board, int boardSize, int* boardColSize) {
    int m = boardSize;
    if (m == 0) return;
    int n = boardColSize[0];

    for (int i = 0; i < m; ++i) {
        if (board[i][0] == 'O') bfs(board, i, 0, m, n);
        if (board[i][n - 1] == 'O') bfs(board, i, n - 1, m, n);
    }

    for (int j = 0; j < n; ++j) {
        if (board[0][j] == 'O') bfs(board, 0, j, m, n);
        if (board[m - 1][j] == 'O') bfs(board, m - 1, j, m, n);
    }

    for (int i = 0; i < m; ++i)
        for (int j = 0; j < n; ++j) {
            if (board[i][j] == 'O') board[i][j] = 'X';
            if (board[i][j] == 'A') board[i][j] = 'O';
        }
}
using System;
using System.Collections.Generic;

public class Solution {
    private void Bfs(char[][] board, int row, int col, int m, int n) {
        Queue<(int, int)> q = new Queue<(int, int)>();
        q.Enqueue((row, col));
        board[row][col] = 'A';

        while (q.Count > 0) {
            var (curRow, curCol) = q.Dequeue();

            int[][] directions = new int[][] {
                new int[] {1, 0},
                new int[] {-1, 0},
                new int[] {0, 1},
                new int[] {0, -1}
            };

            foreach (var dir in directions) {
                int newRow = curRow + dir[0];
                int newCol = curCol + dir[1];
                if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && board[newRow][newCol] == 'O') {
                    board[newRow][newCol] = 'A';
                    q.Enqueue((newRow, newCol));
                }
            }
        }
    }

    public void Solve(char[][] board) {
        int m = board.Length;
        if (m == 0) return;
        int n = board[0].Length;

        for (int i = 0; i < m; i++) {
            if (board[i][0] == 'O') Bfs(board, i, 0, m, n);
            if (board[i][n - 1] == 'O') Bfs(board, i, n - 1, m, n);
        }

        for (int j = 0; j < n; j++) {
            if (board[0][j] == 'O') Bfs(board, 0, j, m, n);
            if (board[m - 1][j] == 'O') Bfs(board, m - 1, j, m, n);
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'O') board[i][j] = 'X';
                if (board[i][j] == 'A') board[i][j] = 'O';
            }
        }
    }
}

BFS approach in Python uses deque for optimal queue operations. It safely flips surrounded 'O's to 'X' by expanding node exploration based on boundary-check constraints.

Complexity

Time Complexity: O(m * n), Space Complexity: O(m * n) due to deque holding potentially all cells when necessary.

Try this approach in the editor

Approach 3: Depth-First Search (DFS)

We can start from the boundary of the matrix, taking each 'O' on the matrix boundary as a starting point, and perform depth-first search. All 'O's found in the search are replaced with '.'.

Then we traverse the matrix again, for each position:

  • If it is '.', replace it with 'O';
  • Otherwise, if it is 'O', replace it with 'X'.

The time complexity is O(m times n), and the space complexity is O(m times n). Here, m and n are the number of rows and columns in the matrix, respectively.

function solve(board: string[][]): void {
    const m = board.length;
    const n = board[0].length;
    const dirs: number[] = [-1, 0, 1, 0, -1];
    const dfs = (i: number, j: number): void => {
        if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] !== 'O') {
            return;
        }
        board[i][j] = '.';
        for (let k = 0; k < 4; ++k) {
            dfs(i + dirs[k], j + dirs[k + 1]);
        }
    };
    for (let i = 0; i < m; ++i) {
        dfs(i, 0);
        dfs(i, n - 1);
    }
    for (let j = 0; j < n; ++j) {
        dfs(0, j);
        dfs(m - 1, j);
    }
    for (let i = 0; i < m; ++i) {
        for (let j = 0; j < n; ++j) {
            if (board[i][j] === '.') {
                board[i][j] = 'O';
            } else if (board[i][j] === 'O') {
                board[i][j] = 'X';
            }
        }
    }
}
func solve(board [][]byte) {
	m, n := len(board), len(board[0])
	dirs := [5]int{-1, 0, 1, 0, -1}
	var dfs func(i, j int)
	dfs = func(i, j int) {
		if i < 0 || i >= m || j < 0 || j >= n || board[i][j] != 'O' {
			return
		}
		board[i][j] = '.'
		for k := 0; k < 4; k++ {
			dfs(i+dirs[k], j+dirs[k+1])
		}
	}
	for i := 0; i < m; i++ {
		dfs(i, 0)
		dfs(i, n-1)
	}
	for j := 0; j < n; j++ {
		dfs(0, j)
		dfs(m-1, j)
	}
	for i, row := range board {
		for j, c := range row {
			if c == '.' {
				board[i][j] = 'O'
			} else if c == 'O' {
				board[i][j] = 'X'
			}
		}
	}
}
impl Solution {
    pub fn solve(board: &mut Vec<Vec<char>>) {
        let m = board.len();
        let n = board[0].len();
        let dirs = vec![-1, 0, 1, 0, -1];

        fn dfs(
            board: &mut Vec<Vec<char>>,
            i: usize,
            j: usize,
            dirs: &Vec<i32>,
            m: usize,
            n: usize,
        ) {
            if i >= 0 && i < m && j >= 0 && j < n && board[i][j] == 'O' {
                board[i][j] = '.';
                for k in 0..4 {
                    dfs(
                        board,
                        ((i as i32) + dirs[k]) as usize,
                        ((j as i32) + dirs[k + 1]) as usize,
                        dirs,
                        m,
                        n,
                    );
                }
            }
        }

        for i in 0..m {
            dfs(board, i, 0, &dirs, m, n);
            dfs(board, i, n - 1, &dirs, m, n);
        }
        for j in 0..n {
            dfs(board, 0, j, &dirs, m, n);
            dfs(board, m - 1, j, &dirs, m, n);
        }

        for i in 0..m {
            for j in 0..n {
                if board[i][j] == '.' {
                    board[i][j] = 'O';
                } else if board[i][j] == 'O' {
                    board[i][j] = 'X';
                }
            }
        }
    }
}
Try this approach in the editor

Approach 4: Union-Find Set

We can also use a union-find set, connecting each 'O' on the matrix boundary with a super node m times n, and connecting each 'O' in the matrix with the 'O's above, below, left, and right of it.

Then we traverse this matrix, for each position, if it is 'O' and it is not connected to the super node, then we replace it with 'X'.

The time complexity is O(m times n times \alpha(m times n)), and the space complexity is O(m times n). Here, m and n are the number of rows and columns in the matrix, respectively, and \alpha is the inverse Ackermann function.

function solve(board: string[][]): void {
    const m = board.length;
    const n = board[0].length;
    const p: number[] = Array(m * n + 1)
        .fill(0)
        .map((_, i) => i);
    const dirs: number[] = [-1, 0, 1, 0, -1];
    const find = (x: number): number => {
        if (p[x] !== x) {
            p[x] = find(p[x]);
        }
        return p[x];
    };
    for (let i = 0; i < m; ++i) {
        for (let j = 0; j < n; ++j) {
            if (board[i][j] === 'O') {
                if (i === 0 || i === m - 1 || j === 0 || j === n - 1) {
                    p[find(i * n + j)] = find(m * n);
                } else {
                    for (let k = 0; k < 4; ++k) {
                        const [x, y] = [i + dirs[k], j + dirs[k + 1]];
                        if (board[x][y] === 'O') {
                            p[find(x * n + y)] = find(i * n + j);
                        }
                    }
                }
            }
        }
    }
    for (let i = 0; i < m; ++i) {
        for (let j = 0; j < n; ++j) {
            if (board[i][j] === 'O' && find(i * n + j) !== find(m * n)) {
                board[i][j] = 'X';
            }
        }
    }
}
func solve(board [][]byte) {
	m, n := len(board), len(board[0])
	p := make([]int, m*n+1)
	for i := range p {
		p[i] = i
	}
	var find func(x int) int
	find = func(x int) int {
		if p[x] != x {
			p[x] = find(p[x])
		}
		return p[x]
	}
	dirs := [5]int{-1, 0, 1, 0, -1}
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if board[i][j] == 'O' {
				if i == 0 || i == m-1 || j == 0 || j == n-1 {
					p[find(i*n+j)] = find(m * n)
				} else {
					for k := 0; k < 4; k++ {
						x, y := i+dirs[k], j+dirs[k+1]
						if board[x][y] == 'O' {
							p[find(x*n+y)] = find(i*n + j)
						}
					}
				}
			}
		}
	}
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if board[i][j] == 'O' && find(i*n+j) != find(m*n) {
				board[i][j] = 'X'
			}
		}
	}
}
Try this approach in the editor

Complexity comparison

ApproachComplexity
Depth-First Search (DFS)

Time Complexity: O(m * n), Space Complexity: O(m * n) for the DFS recursion stack.

Breadth-First Search (BFS)

Time Complexity: O(m * n), Space Complexity: O(m * n) due to deque holding potentially all cells when necessary.

Depth-First Search (DFS)–
Union-Find Set–

Complexity analysis

ApproachTimeSpaceWhen to Use
Depth-First Search (DFS)O(m*n)O(m*n)Standard interview solution for grid traversal and region capture problems
Breadth-First Search (BFS)O(m*n)O(m*n)Preferred when avoiding recursion stack limits or implementing iterative flood fill
Union-Find (Disjoint Set)O(m*n * α(n))O(m*n)Useful when solving multiple connectivity queries or practicing union-find patterns

Frequently asked questions

Is Surrounded Regions easy or hard?

Surrounded Regions is considered a medium difficulty problem. The challenge is recognizing that border-connected regions should not be flipped. Once that insight is clear, the problem reduces to a standard DFS or BFS grid traversal.

How to solve Surrounded Regions in O(n)?

Treat the grid as a graph and start DFS or BFS from all border 'O' cells. Mark every reachable 'O' as safe using a temporary marker. After traversal, flip all remaining 'O' cells to 'X' and restore the marked cells. Each cell is processed once, giving O(m*n) time.

What is the best approach for Surrounded Regions?

Depth-First Search (DFS) or Breadth-First Search (BFS) starting from border cells is the best approach. Instead of checking every region, mark all 'O' cells connected to the border as safe, then flip the remaining ones. This avoids redundant checks and runs in O(m*n) time.

What data structure is used in Surrounded Regions?

The solution typically uses a matrix traversal with DFS recursion or a BFS queue. Some implementations also use a Union-Find (Disjoint Set) structure to track connectivity between cells and border nodes.

What is the time complexity of Surrounded Regions?

The optimal DFS or BFS solution runs in O(m*n) time because every cell in the grid is visited at most once. Space complexity is O(m*n) in the worst case due to recursion stack or queue storage during traversal.

Surrounded Regions Python or Java solution approach?

Python and Java solutions usually implement DFS or BFS flood fill. Start from border cells containing 'O', mark connected cells, then iterate through the board to flip enclosed regions. Both languages achieve O(m*n) time complexity with similar logic.

Is Surrounded Regions asked at Google, Amazon, or Meta?

Surrounded Regions is a common medium-level grid traversal problem frequently asked in interviews at companies like Amazon, Google, and Meta. It tests understanding of graph traversal, connected components, and matrix boundary conditions.

Comments

Next problem · similarNumber of IslandsMedium
Now write it yourselfClose this page and solve Surrounded Regions in the editor, without looking.
Practise Surrounded Regions