Problem statement

You are given an m × n board where 1 marks an open cell and 0 marks a wall.

Capture every region of 1s that is completely surrounded by 0s by flipping those cells to 0. A region is surrounded only if none of its cells touches the border of the board.

Return the board after the capture.

Example 1

Input: board = [[0,0,0,0],[0,1,1,0],[0,0,1,0],[0,1,0,0]]
Output: [[0,0,0,0],[0,0,0,0],[0,0,0,0],[0,1,0,0]]
Explanation: The bottom-left 1 touches the border and survives.

Example 2

Input: board = [[1]]
Output: [[1]]
Explanation: It is on the border.

Example 3

Input: board = [[0,0,0],[0,1,0],[0,0,0]]
Output: [[0,0,0],[0,0,0],[0,0,0]]

Constraints

• 1 <= board.length, board[i].length <= 8
• board[i][j] is 0 or 1.

Hints for Surrounded Regions

1. Hint 1

   Work backwards: instead of hunting for surrounded regions, find the ones that escape.

2. Hint 2

   Flood-fill inward from every 1 on the border and mark everything reachable as safe.

3. Hint 3

   Any 1 left unmarked afterwards is surrounded — flip it.

How to solve Surrounded Regions

Invert the question: flood-fill inward from every border 1 to mark the regions that escape; everything unmarked is surrounded.

Approach

1. Push every 1 on the four edges onto a stack and mark it safe.
2. Pop and spread to four-directional neighbours that are 1 and not yet safe.
3. Emit the board with unsafe 1s flipped to 0.

Why it works

A region is surrounded iff none of its cells touches the border, which is the same as saying it is unreachable from any border cell through 1s. The flood fill computes reachability exactly.

Complexity

• Time — O(m · n)
• Space — O(m · n)

Pitfalls

• Searching for surrounded regions directly requires knowing whether a fill touched the border before deciding — the inversion avoids that bookkeeping.
• Use an explicit stack; recursion overflows on large boards.

Reference solution

Python

def solve(board):
    m, n = len(board), len(board[0])
    safe = [[False] * n for _ in range(m)]
    stack = []

    def push(r, c):
        if 0 <= r < m and 0 <= c < n and board[r][c] == 1 and not safe[r][c]:
            safe[r][c] = True
            stack.append((r, c))

    for r in range(m):
        push(r, 0)
        push(r, n - 1)
    for c in range(n):
        push(0, c)
        push(m - 1, c)
    while stack:
        r, c = stack.pop()
        push(r - 1, c)
        push(r + 1, c)
        push(r, c - 1)
        push(r, c + 1)
    return [[board[r][c] if safe[r][c] else 0 for c in range(n)] for r in range(m)]

Java

public static int[][] solve(int[][] board) {
    int m = board.length, n = board[0].length;
    boolean[][] safe = new boolean[m][n];
    Deque<int[]> stack = new ArrayDeque<>();
    for (int r = 0; r < m; r++) {
        if (board[r][0] == 1 && !safe[r][0]) { safe[r][0] = true; stack.push(new int[]{r, 0}); }
        if (board[r][n - 1] == 1 && !safe[r][n - 1]) { safe[r][n - 1] = true; stack.push(new int[]{r, n - 1}); }
    }
    for (int c = 0; c < n; c++) {
        if (board[0][c] == 1 && !safe[0][c]) { safe[0][c] = true; stack.push(new int[]{0, c}); }
        if (board[m - 1][c] == 1 && !safe[m - 1][c]) { safe[m - 1][c] = true; stack.push(new int[]{m - 1, c}); }
    }
    int[][] steps = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    while (!stack.isEmpty()) {
        int[] cell = stack.pop();
        for (int[] d : steps) {
            int nr = cell[0] + d[0], nc = cell[1] + d[1];
            if (nr >= 0 && nr < m && nc >= 0 && nc < n && board[nr][nc] == 1 && !safe[nr][nc]) {
                safe[nr][nc] = true;
                stack.push(new int[]{nr, nc});
            }
        }
    }
    int[][] out = new int[m][n];
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) out[r][c] = safe[r][c] ? board[r][c] : 0;
    }
    return out;
}

C++

vector<vector<int>> solve(vector<vector<int>>& board) {
    int m = (int) board.size(), n = (int) board[0].size();
    vector<vector<bool>> safe(m, vector<bool>(n, false));
    vector<pair<int, int>> stack;
    for (int r = 0; r < m; r++) {
        if (board[r][0] == 1 && !safe[r][0]) { safe[r][0] = true; stack.push_back(make_pair(r, 0)); }
        if (board[r][n - 1] == 1 && !safe[r][n - 1]) { safe[r][n - 1] = true; stack.push_back(make_pair(r, n - 1)); }
    }
    for (int c = 0; c < n; c++) {
        if (board[0][c] == 1 && !safe[0][c]) { safe[0][c] = true; stack.push_back(make_pair(0, c)); }
        if (board[m - 1][c] == 1 && !safe[m - 1][c]) { safe[m - 1][c] = true; stack.push_back(make_pair(m - 1, c)); }
    }
    int dr[4] = {-1, 1, 0, 0};
    int dc[4] = {0, 0, -1, 1};
    while (!stack.empty()) {
        pair<int, int> cell = stack.back();
        stack.pop_back();
        for (int k = 0; k < 4; k++) {
            int nr = cell.first + dr[k], nc = cell.second + dc[k];
            if (nr >= 0 && nr < m && nc >= 0 && nc < n && board[nr][nc] == 1 && !safe[nr][nc]) {
                safe[nr][nc] = true;
                stack.push_back(make_pair(nr, nc));
            }
        }
    }
    vector<vector<int>> out(m, vector<int>(n, 0));
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) out[r][c] = safe[r][c] ? board[r][c] : 0;
    }
    return out;
}

JavaScript

var solve = function(board) {
    const m = board.length, n = board[0].length;
    const safe = [];
    for (let r = 0; r < m; r++) safe.push(new Array(n).fill(false));
    const stack = [];
    const push = function(r, c) {
        if (r >= 0 && r < m && c >= 0 && c < n && board[r][c] === 1 && !safe[r][c]) {
            safe[r][c] = true;
            stack.push([r, c]);
        }
    };
    for (let r = 0; r < m; r++) { push(r, 0); push(r, n - 1); }
    for (let c = 0; c < n; c++) { push(0, c); push(m - 1, c); }
    while (stack.length > 0) {
        const cell = stack.pop();
        push(cell[0] - 1, cell[1]);
        push(cell[0] + 1, cell[1]);
        push(cell[0], cell[1] - 1);
        push(cell[0], cell[1] + 1);
    }
    const out = [];
    for (let r = 0; r < m; r++) {
        const row = [];
        for (let c = 0; c < n; c++) row.push(safe[r][c] ? board[r][c] : 0);
        out.push(row);
    }
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Implement Router Medium
• Design Memory Allocator Medium
• Design a Food Rating System Medium
• Design an ATM Machine Medium
• Design Bitset Medium
• Range Frequency Queries Medium