150NeetCode 150

84.Surrounded Regions

MediumGraphs · 5/19
LeetCode #130Video

Problem

You are given an m x n board of characters 'X' and 'O'. A region is a group of 'O' cells connected horizontally or vertically. A region is surrounded if none of its cells lies on the border of the board — it is completely enclosed by 'X' cells.

Capture every surrounded region by flipping all of its 'O' cells to 'X', in place. Regions that touch the border stay unchanged. The method returns nothing.

Examples

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: The region {(1,1),(1,2),(2,2)} never reaches the border, so it is captured. (3,1) sits on the bottom border, so it survives.
Input:  board = [["X"]]
Output: [["X"]]
Explanation: There is no 'O' to capture.
Input:  board = [
  ["O","O"],
  ["O","O"]
]
Output: [
  ["O","O"],
  ["O","O"]
]
Explanation: Every cell is on the border, so nothing is surrounded.

Constraints

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

💡 Key Insight

Deciding "is this region enclosed?" region by region is awkward. The complement is easy: an 'O' survives exactly when it is connected to a border 'O'. So flood-fill from every 'O' on the border and temporarily mark everything reached as safe ('T'). Afterwards, any 'O' left unmarked must be enclosed — flip it to 'X' — and turn every 'T' back into 'O'. Two linear passes, O(m·n) total.

Brute Force

TimeO((m·n)²)SpaceO(m·n)

Intuition

For each 'O', explore its whole region with a fresh BFS and check whether any cell of that region lies on the border. If none does, this cell must be captured. Record the decision in a separate matrix and apply all flips at the end, so the checks are not affected by flips made along the way.

Algorithm

  1. Create capture[m][n].
  2. For every cell with board[r][c] == 'O':
    • BFS over 'O' neighbours with a fresh visited array.
    • If any reached cell has r == 0, r == m - 1, c == 0 or c == n - 1, the cell is safe; otherwise set capture[r][c] = true.
  3. Flip every cell with capture[r][c] == true to 'X'.

Visualization

X X X X
X O O X     cell (1,1): BFS reaches (1,1),(1,2),(2,2) → no border cell → capture
X X O X     cell (1,2): same BFS again                 → capture
X O X X     cell (2,2): same BFS again                 → capture
            cell (3,1): it IS on the border            → safe

Code

java
import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    private static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    public void solve(char[][] board) {
        int rows = board.length, cols = board[0].length;
        boolean[][] capture = new boolean[rows][cols];
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (board[r][c] == 'O' && !touchesBorder(board, r, c)) {
                    capture[r][c] = true;
                }
            }
        }
        // Apply flips only after every decision is made
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (capture[r][c]) board[r][c] = 'X';
            }
        }
    }

    // Fresh BFS over the 'O' region containing (r, c)
    private boolean touchesBorder(char[][] board, int r, int c) {
        int rows = board.length, cols = board[0].length;
        boolean[][] visited = new boolean[rows][cols];
        Deque<int[]> queue = new ArrayDeque<>();
        queue.offer(new int[]{r, c});
        visited[r][c] = true;
        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            int cr = cell[0], cc = cell[1];
            if (cr == 0 || cr == rows - 1 || cc == 0 || cc == cols - 1) {
                return true;
            }
            for (int[] d : DIRS) {
                int nr = cr + d[0], nc = cc + d[1];
                if (nr >= 0 && nr < rows && nc >= 0 && nc < cols
                        && !visited[nr][nc] && board[nr][nc] == 'O') {
                    visited[nr][nc] = true;
                    queue.offer(new int[]{nr, nc});
                }
            }
        }
        return false;
    }
}

Complexity

  • Time: O((m·n)²) — each 'O' can trigger a BFS over the whole board.
  • Space: O(m·n) — capture, visited and the queue.

Complexity Comparison

Approach Time Space
Brute Force O((m·n)²) O(m·n)
DFS from Border O(m·n) O(m·n)
BFS from Border O(m·n) O(m·n)

Common Pitfalls

  • Marking safe cells with 'O' or 'X' instead of a third character — the final sweep then cannot tell "connected to the border" apart from "enclosed".
  • Doing the final sweep in the wrong order ('T' → 'O' first, then 'O' → 'X') — that captures the safe cells too. Use one if / else if per cell.
  • Only seeding from the top and left edges; all four edges matter.
  • Forgetting single-row or single-column boards, where every cell is on the border and nothing can be captured.
  • Treating diagonal 'O's as connected — a region only spreads up, down, left and right.