Surrounded Regions — Boundary DFS Trick (LC 130)

Problem Statement#

LeetCode 130 — Surrounded Regions (Medium)

Given an m x n matrix board containing 'X' and 'O', capture all regions that are 4-directionally surrounded by 'X'. A region is captured by flipping all 'O's into 'X's in that surrounded region. You must do it in place.

Constraints:

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

Example:

Input:
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 bottom-left O is on the border, so it (and any Os connected to it) survives.
The Os at (1,1), (1,2), (2,2) are fully surrounded and get flipped.

Why This Problem Matters#

Surrounded Regions is the first problem most candidates fail to invert. The naive instinct is to walk every interior region of 'O's and check whether any cell touches the boundary — an algorithm that requires bookkeeping and is easy to get wrong. The optimal solution flips the question on its head: instead of finding regions that cannot escape, find regions that can escape by flooding from the boundary inward.

This inversion trick is one of the most-cited interview patterns by Google, Meta, and Amazon. Once you learn "flood from the boundary", you immediately solve LC 1020 (Number of Enclaves), LC 417 (Pacific Atlantic Water Flow), and LC 1254 (Number of Closed Islands) with the same template. Interviewers specifically ask this problem to test whether you can re-frame a problem instead of brute-forcing it.

The Core Insight#

Two observations break the problem open:

1. An 'O' survives if and only if it is connected to a boundary 'O'. Any region that does not touch the edges is fully enclosed by 'X' and must be flipped.
2. Searching from the interior is hard; searching from the boundary is easy. Walk the four edges, run DFS/BFS from every boundary 'O', and mark every reachable 'O' as "safe".

After the boundary flood:

• Cells still equal to 'O' are surrounded — flip to 'X'.
• Cells marked safe (we use a temporary sentinel like '#') are connected to the border — flip back to 'O'.

The third pass is a clean linear sweep. No tricky bookkeeping, no second-guessing.

Why this is faster mentally than the naive approach: The naive approach (DFS each region, check if any cell is on the border) is also O(m times n) in time, but you must remember to defer decisions until DFS finishes. The boundary trick avoids that conditional logic entirely — the marking does all the work.

Visual Dry Run#

Starting board:

X X X X
X O O X
X X O X
X O X X

Step 1 — Find boundary 'O's. Only (3, 1) qualifies.

Step 2 — DFS from (3, 1), marking visited as '#':

Board after boundary flood:

X X X X
X O O X
X X O X
X # X X

Step 3 — Sweep:

• 'O' cells (1,1), (1,2), (2,2) become 'X' (surrounded).
• '#' cell (3,1) becomes 'O' (safe).

Final board:

X X X X
X X X X
X X X X
X O X X

Solution (Optimal)#

Python#

class Solution:
    def solve(self, board: list[list[str]]) -> None:
        if not board or not board[0]:
            return
        R, C = len(board), len(board[0])
 
        def dfs(r: int, c: int) -> None:
            # stop at OOB, X, or already-marked safe cell
            if not (0 <= r < R and 0 <= c < C) or board[r][c] != 'O':
                return
            board[r][c] = '#'                # sentinel: connected to border
            dfs(r + 1, c)
            dfs(r - 1, c)
            dfs(r, c + 1)
            dfs(r, c - 1)
 
        # 1) flood from every boundary O
        for r in range(R):
            dfs(r, 0)
            dfs(r, C - 1)
        for c in range(C):
            dfs(0, c)
            dfs(R - 1, c)
 
        # 2) sweep: surrounded -> X, safe -> O
        for r in range(R):
            for c in range(C):
                if board[r][c] == 'O':
                    board[r][c] = 'X'
                elif board[r][c] == '#':
                    board[r][c] = 'O'

JavaScript#

/**
 * @param {character[][]} board
 * @return {void}
 */
var solve = function(board) {
    if (!board.length || !board[0].length) return;
    const R = board.length, C = board[0].length;
 
    // mark every O reachable from the border with a sentinel '#'
    function dfs(r, c) {
        if (r < 0 || r >= R || c < 0 || c >= C || board[r][c] !== 'O') return;
        board[r][c] = '#';
        dfs(r + 1, c);
        dfs(r - 1, c);
        dfs(r, c + 1);
        dfs(r, c - 1);
    }
 
    // 1) flood from every border cell
    for (let r = 0; r < R; r++) { dfs(r, 0); dfs(r, C - 1); }
    for (let c = 0; c < C; c++) { dfs(0, c); dfs(R - 1, c); }
 
    // 2) final sweep: O -> X (captured), # -> O (safe)
    for (let r = 0; r < R; r++) {
        for (let c = 0; c < C; c++) {
            if (board[r][c] === 'O') board[r][c] = 'X';
            else if (board[r][c] === '#') board[r][c] = 'O';
        }
    }
};

Time Complexity: O(m times n) — each cell visited at most twice. Space Complexity: O(m times n) recursion stack worst case.

Common Mistakes#

1. Skipping corner cases of empty boards. board[0] throws if board is empty; always guard.
2. Trying to track "is this region on the border" inside an interior DFS. This works but is error-prone; the boundary-flood trick is cleaner.
3. Using a separate visited matrix. Possible but wasteful — the sentinel '#' doubles as visited and "this cell stays".
4. Forgetting the second sweep. If you only flip surrounded 'O's but leave '#' cells untouched, your output has a third character.
5. Recursing on 'X' cells. The base case must reject any cell that is not exactly 'O'.

Interview Tips#

• Verbalize the inversion. Say "I will flood from the boundary because escape paths are easier to identify than enclosure" before writing code. Interviewers love hearing reasoning.
• Sentinel choice. Pick any character that is not 'O' or 'X'. '#' is a common convention; 'S' for "safe" works too.
• Mention BFS as an alternative. For very large boards (200x200) recursion depth can hit 40,000. Switching to a queue avoids stack overflow in stricter environments.

Follow-up Questions#

1. What if the board is enormous and recursion overflows? Use BFS with a queue, or sys.setrecursionlimit in Python as a quick patch.
2. Multiple connected interior regions — does the algorithm still work? Yes; each region is independent. The sweep flips each one correctly because none of them is marked safe.
3. Diagonal connectivity? Add four more direction deltas. The boundary trick still applies.
4. Can we use Union-Find? Yes — connect every boundary 'O' to a virtual "safe" node, union neighbors, then check root in the final sweep. Same time complexity but more code.

Key Takeaways#

• Surrounded Regions is solved by inverting the question: flood-fill from the border to find safe 'O's, then flip everything else.
• The sentinel-character trick ('#') avoids allocating a separate visited matrix.
• This same boundary-DFS pattern unlocks LC 417, LC 1020, and LC 1254 — make it part of your reusable toolbox.
• Always handle empty-board edge cases before indexing.
• BFS and DFS both work; choose BFS if recursion depth is a concern on large grids.
• The post-flood sweep is what actually mutates the answer — never forget the second pass.