☕ DSA Java Articles

Topics › Graphs › Problems on BFS/DFS

Surrounded Regions

Medium TUF ID 537 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given an n × m board of characters, each 'X' or 'O'. A region is a maximal group of 'O' cells connected up, down, left or right (not diagonally). A region is surrounded if none of its cells lies on the border of the board, because then it is completely fenced in by 'X's. Capture every surrounded region by flipping all its cells to 'X'. Modify the board in place.

Constraints: 1 ≤ n, m ≤ 200.

Example 1

X X X X        X X X X
X O O X   ->   X X X X
X X O X        X X X X
X O X X        X O X X

The three connected 'O's in the middle never touch the border, so they are captured. The 'O' in the bottom row is on the border and survives.

Example 2

X O X X X      X O X X X
X O O X X  ->  X O O X X
X X X O X      X X X X X
X O X X O      X O X X O

(1,1) and (1,2) are connected to (0,1), which is on the border, so all three survive. (2,3) is alone in the interior and gets captured.

The whole problem hinges on one reformulation: a region survives if and only if it touches the border. So the question “which 'O's are trapped?” is the same as “which 'O's are not connected to a border 'O'?”.

Approach 1: Brute force, one search per cell

Intuition. Take each 'O' on its own and ask whether it can reach the border by walking through 'O's. A BFS from that cell answers it. Record the answers first and flip afterwards, because flipping during the scan would change what later searches see.

Algorithm.

  1. For every 'O' at (i, j), run a BFS through 'O' cells; if it ever stands on a border cell, the cell is safe.
  2. Remember the cells whose BFS never reached the border.
  3. Flip those cells to 'X'.
static final int[] DR = {-1, 0, 1, 0}, DC = {0, 1, 0, -1};

static void bruteForce(char[][] board) {
    int n = board.length, m = board[0].length;
    boolean[][] capture = new boolean[n][m];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (board[i][j] == 'O' && !reachesBorder(board, i, j)) capture[i][j] = true;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (capture[i][j]) board[i][j] = 'X';
}

static boolean reachesBorder(char[][] board, int sr, int sc) {
    int n = board.length, m = board[0].length;
    boolean[][] seen = new boolean[n][m];
    Deque<int[]> q = new ArrayDeque<>();
    q.offer(new int[]{sr, sc});
    seen[sr][sc] = true;
    while (!q.isEmpty()) {
        int[] cell = q.poll();
        int r = cell[0], c = cell[1];
        if (r == 0 || c == 0 || r == n - 1 || c == m - 1) return true;
        for (int k = 0; k < 4; k++) {                // interior cell, so all 4 neighbours are inside the grid
            int nr = r + DR[k], nc = c + DC[k];
            if (board[nr][nc] == 'O' && !seen[nr][nc]) { seen[nr][nc] = true; q.offer(new int[]{nr, nc}); }
        }
    }
    return false;
}

A small detail in reachesBorder: the border test runs before any neighbour is generated, so every cell that expands its neighbours is an interior cell, and all four of its neighbours are guaranteed to be inside the board. That is why no bounds check is needed there.

Complexity. Time O((n·m)^2): a region of size k is searched k times, and one big region can hold almost every cell. Space O(n·m) for the seen array of one search.

Approach 2: Optimal, DFS from the border

Intuition. The brute force asks the question from the inside, once per cell. Ask it from the outside instead, once for the whole board. Every surviving cell is connected to some border 'O'. So start a DFS from each 'O' on the border and mark everything it reaches as safe. When all those searches are done, the safe cells are exactly the survivors, and every remaining 'O' belongs to a surrounded region.

Why is this exact? If a cell is marked safe, the DFS reached it along a chain of 'O's from the border, so its region touches the border. Conversely, if a region touches the border, one of its cells is a border 'O', the DFS starts there, and a DFS floods its entire connected region. So “safe” and “survives” are the same set.

Each cell is marked at most once, and a marked cell is never expanded again, so all the border searches together cost one sweep of the board.

Algorithm.

  1. For each cell on the four borders, call markSafe, which returns immediately on 'X', outside the board, or an already safe cell, and otherwise marks the cell and recurses to its four neighbours.
  2. Scan the board and flip every 'O' that is not safe.
static void optimalDfs(char[][] board) {
    int n = board.length, m = board[0].length;
    boolean[][] safe = new boolean[n][m];
    for (int i = 0; i < n; i++) {
        markSafe(board, i, 0, safe);
        markSafe(board, i, m - 1, safe);
    }
    for (int j = 0; j < m; j++) {
        markSafe(board, 0, j, safe);
        markSafe(board, n - 1, j, safe);
    }
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (board[i][j] == 'O' && !safe[i][j]) board[i][j] = 'X';
}

static void markSafe(char[][] board, int r, int c, boolean[][] safe) {
    if (r < 0 || c < 0 || r >= board.length || c >= board[0].length) return;
    if (board[r][c] != 'O' || safe[r][c]) return;
    safe[r][c] = true;
    for (int k = 0; k < 4; k++) markSafe(board, r + DR[k], c + DC[k], safe);
}

Dry run on Example 2. The border 'O's are (0,1), (3,1) and (3,4).

start cells marked safe
(0,1) (0,1), (1,1), (1,2)
(3,1) (3,1)
(3,4) (3,4)

The only 'O' not in the table is (2,3), so it is the only cell flipped.

Complexity. Time O(n·m): every cell is marked once and inspected a constant number of times. Space O(n·m) for safe and for the recursion stack in the worst case.

A common in-place variant skips the safe array: temporarily overwrite safe cells with a third character such as '#', then in the final scan turn 'O' into 'X' and '#' back into 'O'.

Approach 3: The same idea with multi-source BFS

Intuition. On a 200 × 200 board a snake-shaped region can be 40000 cells long, and the recursive DFS would then go 40000 frames deep, which can overflow Java’s default call stack. A BFS that starts with all border 'O's in the queue marks the same set of cells using heap memory only. The correctness argument is identical: BFS also floods each connected region it touches.

static void optimalBfs(char[][] board) {
    int n = board.length, m = board[0].length;
    boolean[][] safe = new boolean[n][m];
    Deque<int[]> q = new ArrayDeque<>();
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            boolean border = i == 0 || j == 0 || i == n - 1 || j == m - 1;
            if (border && board[i][j] == 'O') { safe[i][j] = true; q.offer(new int[]{i, j}); }
        }
    }
    while (!q.isEmpty()) {
        int[] cell = q.poll();
        for (int k = 0; k < 4; k++) {
            int r = cell[0] + DR[k], c = cell[1] + DC[k];
            if (r >= 0 && c >= 0 && r < n && c < m && board[r][c] == 'O' && !safe[r][c]) {
                safe[r][c] = true;
                q.offer(new int[]{r, c});
            }
        }
    }
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (board[i][j] == 'O' && !safe[i][j]) board[i][j] = 'X';
}

Complexity. Time O(n·m), space O(n·m) for safe and the queue.

Edge cases and pitfalls