Surrounded Regions

MediumGraph BFS/DFSNeetCode 150MidOpen on LeetCodeUpdated Nov 11, 2026

You're given an m x n board of 'X' and 'O' cells. A region is a group of 'O' cells connected up, down, left, or right. A region is captured when none of its cells lies on the border of the board, and capturing flips every cell in it to 'X'. Capture every such region, modifying the board in place.

Examples

board = ["XXXXX","XOOXX","XXOXO","XXXXO"] returns ["XXXXX","XXXXX","XXXXO","XXXXO"]

before

Each string is one row. The three Os in the middle touch no border and are captured. The two Os in the last column touch the right edge, so they stay.

board = ["O"] returns ["O"]

The only cell is on the border, so it can't be captured.

board = ["XXX","XOX","XXX"] returns ["XXX","XXX","XXX"]

The center O is fully enclosed and flips to X.

Constraints

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

Hints

Hint 1

It's hard to prove a region is enclosed, but easy to see which cells touch the edge. Which Os can never be captured?

Hint 2

A pointer toward the approach

Hint 3

The full approach, step by step

Drill This: Your Approach First

Answer, Then Reveal

In two or three sentences, how would you solve it and what's the complexity?

Skip to Reading

Approach

Work backward from the cells that are safe. Any O connected to a border O survives, and every other O is captured. Flood fill from each O on the border with DFS or BFS and mark every O it reaches with a temporary symbol such as '#'. Then sweep the board once: remaining Os flip to X and #s go back to O. O(m * n) time, and O(m * n) space for the stack in the worst case.

Time

O(m * n)

Space

O(m * n)

Pitfall

Flood filling from every interior O to test whether it reaches a border. It works, but repeats the same search for every cell of a large region. Starting from the border visits each cell once.

Solutions

class Solution {
    public void solve(char[][] board) {
        int m = board.length, n = board[0].length;
        Deque<int[]> stack = new ArrayDeque<>();
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                boolean border = r == 0 || c == 0 || r == m - 1 || c == n - 1;
                if (border && board[r][c] == 'O') {
                    board[r][c] = '#';
                    stack.push(new int[] {r, c});
                }
            }
        }
        int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        while (!stack.isEmpty()) {
            int[] cell = stack.pop();
            for (int[] d : dirs) {
                int nr = cell[0] + d[0], nc = cell[1] + d[1];
                if (nr >= 0 && nr < m && nc >= 0 && nc < n && board[nr][nc] == 'O') {
                    board[nr][nc] = '#';
                    stack.push(new int[] {nr, nc});
                }
            }
        }
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (board[r][c] == 'O') board[r][c] = 'X';
                else if (board[r][c] == '#') board[r][c] = 'O';
            }
        }
    }
}

class Solution:
    def solve(self, board) -> None:
        m, n = len(board), len(board[0])
        stack = []
        for r in range(m):
            for c in range(n):
                on_border = r in (0, m - 1) or c in (0, n - 1)
                if on_border and board[r][c] == "O":
                    board[r][c] = "#"
                    stack.append((r, c))
        while stack:
            r, c = stack.pop()
            for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
                if 0 <= nr < m and 0 <= nc < n and board[nr][nc] == "O":
                    board[nr][nc] = "#"
                    stack.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"