Problem 22.5 · Depth-First SearchMedium

Surrounded Regions

PatternGraph DFS and Flood Fill Matrix Traversal

What it teaches: Mark the survivors from the border, then flip everything else.

Practise it on judges as “Surrounded Regions”.

The problem

Capture every region of 'O' that is completely surrounded by 'X' (not connected to the border) by flipping it to 'X'. Modify the board in place.

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]]

Constraints

1 ≤ rows, cols ≤ 200

Pattern clues in the wording

→ Regions that do or don't touch the border

These clues point to Graph DFS and Flood Fill: Go as deep as possible from a node, marking visited cells or nodes, to find connected regions.

Stuck? Take one hint at a time

Solution.java · starter

class Solution {
    public void solve(char[][] board) {
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]	[["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]
2	board = [["X"]]	[["X"]]

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Border DFS, then sweep · O(rows × cols)

Border DFS, then sweep

Time O(rows × cols) Space O(rows × cols)

DFS from each border 'O', turning it into '#'. Then flip remaining 'O' to 'X' and '#' back to 'O'.

Approach 1

class Solution {
    public void solve(char[][] board) {
        int m = board.length, n = board[0].length;
        for (int r = 0; r < m; r++) { mark(board, r, 0); mark(board, r, n - 1); }
        for (int c = 0; c < n; c++) { mark(board, 0, c); mark(board, m - 1, c); }
        for (int r = 0; r < m; r++)
            for (int c = 0; c < n; c++)
                board[r][c] = board[r][c] == '#' ? 'O' : 'X';
    }

    private void mark(char[][] b, int r, int c) {
        if (r < 0 || c < 0 || r >= b.length || c >= b[0].length || b[r][c] != 'O') return;
        b[r][c] = '#';
        mark(b, r + 1, c); mark(b, r - 1, c); mark(b, r, c + 1); mark(b, r, c - 1);
    }
}

Verdict: Two passes over the board.

Before you submit

Edge cases and common mistakes

Test these inputs

All 'O'
Board with one row

Mistakes people make

DFS from every interior 'O' to test for the border (repeated work).

Interview

Follow-up questions

How does Number of Enclaves relate?

Command Palette

The problem

Approaches

Border DFS, then sweep

Edge cases and common mistakes

Follow-up questions