Surrounded Regions LeetCode 130 Guide

LeetCode 130 Surrounded Regions gives you an m x n board of characters containing only 'X' and 'O'. A region of 'O' cells is considered surrounded when it is completely enclosed by 'X' cells with no path to any border cell. Your task is to capture all such surrounded regions by flipping every 'O' in them to 'X'.

The tricky part is what does NOT get captured: any 'O' cell that is on the border, or any 'O' cell that is 4-directionally connected to a border 'O', is considered safe and must not be flipped. Only interior 'O' clusters that have no route to the edge of the board are captured.

Key constraints to understand: the board is guaranteed to have at least one row and one column. Cells on the four borders are never captured. The capture definition is purely 4-directional — diagonal connections do not count. This means even a single 'O' touching the edge protects its entire connected component.

The naive approach tries to identify all surrounded regions — groups of 'O' cells with no path to the border. This is surprisingly hard to implement cleanly because you need to track whether each connected component reaches the border, which requires complete component exploration before deciding whether to flip.

The reverse thinking trick flips the question entirely: instead of finding what IS surrounded, find what is NOT surrounded. An 'O' cell is safe if and only if it can reach the border. These are easy to identify — just start from every 'O' on the four borders and do a DFS or BFS to mark all reachable 'O' cells as safe.

After marking the safe cells, the remaining unmarked 'O' cells are by definition surrounded. A single pass through the board flips them to 'X' and restores the safe markers back to 'O'. Two phases, linear time, minimal code. This is the standard approach accepted in interviews.

The first phase scans only the four borders of the board — the first row, the last row, the first column, and the last column. For every cell on these borders that contains 'O', launch a DFS (or BFS) that traverses all 4-directionally connected 'O' cells and marks each one with a temporary sentinel character such as 'S' for safe.

The DFS is straightforward: if the current cell is out of bounds or is not 'O', return immediately. Otherwise mark it 'S' and recursively call DFS on all four neighbors. Because you only ever call DFS on 'O' cells and immediately change them to 'S', there is no risk of infinite loops or revisiting cells.

After Phase 1, every 'O' remaining on the board is an interior 'O' with no connection to the border. Every 'S' is a safe cell that was originally 'O' but is border-connected. The 'X' cells are unchanged throughout.

The second phase is a single pass through the entire board with exactly two rules. If a cell contains 'O', it is a captured interior cell — flip it to 'X'. If a cell contains 'S', it is a safe border-connected cell — restore it to 'O'. If a cell contains 'X', leave it unchanged.

This single sweep is the elegant payoff of the reverse thinking approach. You never needed to track connected components explicitly, never needed a union-find structure, and never needed to decide during DFS whether to commit a flip. The decision was already made by the marking phase.

After Phase 2, the board is in its final state: all surrounded 'O' regions have been captured (flipped to 'X'), and all border-connected 'O' regions have been preserved. The sentinel 'S' characters have been cleaned up and are gone from the board.

DFS is the more common implementation for this problem because it leads to shorter, more recursive code. The DFS helper is typically 5-6 lines in Python. However, Python's default recursion limit is 1000 frames, and a large board (e.g., 200x200) with a fully connected 'O' region could produce a call stack thousands of frames deep, causing a RecursionError.

BFS with an explicit queue avoids the recursion limit entirely. Instead of recursive calls, you maintain a deque and process cells iteratively. The logic is the same — pop a cell, check its four neighbors, enqueue any 'O' neighbors after marking them 'S' — but it runs on the heap rather than the call stack.

Both DFS and BFS have O(m * n) time complexity and O(m * n) space complexity in the worst case. For interview problems on small boards, DFS is fine. For production code or competitive programming with large inputs, prefer BFS or increase the recursion limit explicitly with sys.setrecursionlimit in Python.

In Python, define a dfs(r, c) helper that returns immediately if out-of-bounds or board[r][c] != 'O', otherwise sets board[r][c] = 'S' and calls dfs on all four neighbors. Then iterate border cells, calling dfs on each 'O'. Finally loop all cells: 'O' → 'X', 'S' → 'O'. Total: ~15 lines.

In Java, the structure is identical but uses char[][] board instead of a list of lists. The DFS helper is a private void method. Alternatively, a BFS version uses ArrayDeque<int[]> as the queue and an int[][] directions = {{0,1},{0,-1},{1,0},{-1,0}} array for neighbor offsets. Both approaches are O(m*n) time and O(m*n) space.

The space complexity accounts for the DFS call stack (worst case O(m*n) for a board of all 'O') or the BFS queue (same worst case). The time complexity is O(m*n) since each cell is touched at most twice: once during the border DFS and once during the final sweep.

Surrounded Regions belongs to the border DFS family — problems where you start traversal from the edges of the grid to identify cells with certain reachability properties. Recognizing this family unlocks a powerful template: scan borders, DFS/BFS inward to mark reachable cells, then process the board based on which cells were and were not reached.

Pacific Atlantic Water Flow (LeetCode 417) uses the same border DFS pattern: two separate multi-source DFS passes from the Pacific border cells and the Atlantic border cells, then find cells reachable from both. Number of Islands (LeetCode 200) uses interior DFS to count connected components. Walls and Gates (LeetCode 286) uses multi-source BFS from all gates simultaneously.

The unifying insight across this family: when you need to find cells that can or cannot reach the boundary, it is almost always easier to start from the boundary and work inward rather than starting from interior cells and asking whether they escape. Reverse the direction of your traversal to simplify the logic.