Flood Fill, Surrounded Regions, and Enclaves

Grid-based graph problems are among the most common in coding interviews. The grid itself is an implicit graph where each cell connects to its 4-directional (or sometimes 8-directional) neighbors. Flood fill is the foundational technique: start at a cell and spread to all connected cells that meet a condition.

This article covers four classic problems that all build on the flood fill idea.

The 4-directional pattern

Almost every grid traversal uses this directional array:

DIRS = [(0, 1), (0, -1), (1, 0), (-1, 0)]

A helper to check bounds:

def in_bounds(r: int, c: int, rows: int, cols: int) -> bool:
    return 0 <= r < rows and 0 <= c < cols

These two pieces appear in virtually every grid problem. Memorize them.

Problem 1: Flood Fill (LeetCode 733)

Problem: Given an image (2D grid of integers), a starting pixel (sr, sc), and a new color, flood fill the connected region of the same original color.

DFS approach

def flood_fill(image: list[list[int]], sr: int, sc: int, color: int) -> list[list[int]]:
    """
    LeetCode 733: Flood Fill.
    Replace the connected region starting at (sr, sc) with the new color.
    """
    rows, cols = len(image), len(image[0])
    original = image[sr][sc]

    if original == color:
        return image         # no-op: avoids infinite recursion

    def dfs(r: int, c: int):
        image[r][c] = color
        for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and image[nr][nc] == original:
                dfs(nr, nc)

    dfs(sr, sc)
    return image

BFS approach

from collections import deque

def flood_fill_bfs(image: list[list[int]], sr: int, sc: int, color: int) -> list[list[int]]:
    """
    BFS-based flood fill.
    """
    rows, cols = len(image), len(image[0])
    original = image[sr][sc]

    if original == color:
        return image

    queue = deque([(sr, sc)])
    image[sr][sc] = color

    while queue:
        r, c = queue.popleft()
        for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and image[nr][nc] == original:
                image[nr][nc] = color
                queue.append((nr, nc))

    return image

Time: O(m * n) where m and n are grid dimensions.

Space: O(m * n) worst case for the recursion stack or queue.

DFS vs BFS for grids

Aspect	DFS	BFS
Implementation	Simpler (recursion)	Slightly more code (queue)
Stack risk	Stack overflow on large grids	No stack overflow
Order	Deep-first exploration	Layer-by-layer
When to prefer	Small grids, simpler code	Large grids, shortest path

Problem 2: Surrounded Regions (LeetCode 130)

Problem: Given an m x n board of 'X' and 'O', capture all regions of 'O' that are completely surrounded by 'X'. A region is not captured if any of its cells is on the board boundary.

Key insight: invert the problem

Instead of finding surrounded regions (hard), find unsurrounded regions (easy) and mark everything else.

1. Start DFS/BFS from every 'O' on the boundary.
2. Mark all connected 'O' cells as safe (e.g., 'S').
3. Sweep the board: remaining 'O' cells become 'X', and 'S' cells revert to 'O'.

def solve(board: list[list[str]]) -> None:
    """
    LeetCode 130: Surrounded Regions.
    Modifies board in-place.
    """
    if not board or not board[0]:
        return

    rows, cols = len(board), len(board[0])

    def dfs(r: int, c: int):
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return
        if board[r][c] != 'O':
            return
        board[r][c] = 'S'    # mark as safe
        dfs(r + 1, c)
        dfs(r - 1, c)
        dfs(r, c + 1)
        dfs(r, c - 1)

    # Step 1: Mark boundary-connected O cells
    for r in range(rows):
        if board[r][0] == 'O':
            dfs(r, 0)
        if board[r][cols - 1] == 'O':
            dfs(r, cols - 1)

    for c in range(cols):
        if board[0][c] == 'O':
            dfs(0, c)
        if board[rows - 1][c] == 'O':
            dfs(rows - 1, c)

    # Step 2: Capture and restore
    for r in range(rows):
        for c in range(cols):
            if board[r][c] == 'O':
                board[r][c] = 'X'      # captured
            elif board[r][c] == 'S':
                board[r][c] = 'O'      # restored

Time: O(m * n)

Space: O(m * n) for recursion in worst case.

Why boundary-first works

Any 'O' region touching the boundary cannot be fully surrounded. By marking these first, all remaining 'O' cells are guaranteed to be interior and fully enclosed by 'X'.

BFS alternative to avoid stack overflow

For large boards, replace the recursive DFS with BFS:

def solve_bfs(board: list[list[str]]) -> None:
    """Surrounded Regions using BFS to avoid recursion depth issues."""
    if not board or not board[0]:
        return

    rows, cols = len(board), len(board[0])
    queue = deque()

    # Collect boundary O cells
    for r in range(rows):
        for c in range(cols):
            if (r == 0 or r == rows - 1 or c == 0 or c == cols - 1) and board[r][c] == 'O':
                queue.append((r, c))
                board[r][c] = 'S'

    # BFS from boundary
    while queue:
        r, c = queue.popleft()
        for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] == 'O':
                board[nr][nc] = 'S'
                queue.append((nr, nc))

    # Capture and restore
    for r in range(rows):
        for c in range(cols):
            if board[r][c] == 'O':
                board[r][c] = 'X'
            elif board[r][c] == 'S':
                board[r][c] = 'O'

Problem 3: Number of Enclaves (LeetCode 1020)

Problem: Given a binary matrix where 1 is land and 0 is water, count the number of land cells from which you cannot walk off the boundary.

This is almost identical to surrounded regions. The twist: we count cells instead of flipping them.

from collections import deque

def num_enclaves(grid: list[list[int]]) -> int:
    """
    LeetCode 1020: Number of Enclaves.
    """
    rows, cols = len(grid), len(grid[0])
    queue = deque()

    # Enqueue all boundary land cells
    for r in range(rows):
        for c in range(cols):
            if (r == 0 or r == rows - 1 or c == 0 or c == cols - 1) and grid[r][c] == 1:
                queue.append((r, c))
                grid[r][c] = 0    # mark as reachable from boundary

    # BFS to mark all land reachable from boundary
    while queue:
        r, c = queue.popleft()
        for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                grid[nr][nc] = 0
                queue.append((nr, nc))

    # Count remaining land cells (enclaves)
    return sum(grid[r][c] for r in range(rows) for c in range(cols))

Time: O(m * n)

Space: O(m * n) for the queue.

Pattern recognition

Notice the similarity between Surrounded Regions and Number of Enclaves:

1. Start from boundary cells.
2. Mark/remove all boundary-connected cells.
3. Process what remains.

This boundary-first elimination pattern appears in many grid problems.

Problem 4: Pacific Atlantic Water Flow (LeetCode 417)

Problem: Given an m x n matrix of heights, water can flow from a cell to a neighbor with height <= the current cell. The Pacific ocean touches the top and left edges; the Atlantic touches the bottom and right edges. Find all cells from which water can reach both oceans.

Key insight: reverse the flow

Instead of checking from each cell whether water reaches both oceans (expensive), start from the ocean borders and flow uphill.

from collections import deque

def pacific_atlantic(heights: list[list[int]]) -> list[list[int]]:
    """
    LeetCode 417: Pacific Atlantic Water Flow.
    """
    if not heights:
        return []

    rows, cols = len(heights), len(heights[0])

    def bfs(starts: list[tuple[int, int]]) -> set[tuple[int, int]]:
        reachable = set(starts)
        queue = deque(starts)

        while queue:
            r, c = queue.popleft()
            for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                nr, nc = r + dr, c + dc
                if (0 <= nr < rows and 0 <= nc < cols
                        and (nr, nc) not in reachable
                        and heights[nr][nc] >= heights[r][c]):
                    reachable.add((nr, nc))
                    queue.append((nr, nc))

        return reachable

    # Pacific: top row + left column
    pacific_starts = (
        [(0, c) for c in range(cols)] +
        [(r, 0) for r in range(1, rows)]
    )

    # Atlantic: bottom row + right column
    atlantic_starts = (
        [(rows - 1, c) for c in range(cols)] +
        [(r, cols - 1) for r in range(rows - 1)]
    )

    pacific_reach = bfs(pacific_starts)
    atlantic_reach = bfs(atlantic_starts)

    # Intersection: cells that can reach both oceans
    return [[r, c] for r, c in pacific_reach & atlantic_reach]

Time: O(m * n) — each cell is visited at most twice (once per ocean).

Space: O(m * n) for the reachable sets.

Why reverse flow works

Flowing uphill from the ocean is equivalent to asking “can water at this cell flow downhill to the ocean?” Reversing avoids redundant work: each cell is visited at most once per ocean instead of potentially starting a full DFS/BFS from every cell.

DFS alternative

def pacific_atlantic_dfs(heights: list[list[int]]) -> list[list[int]]:
    """Pacific Atlantic Water Flow using DFS."""
    if not heights:
        return []

    rows, cols = len(heights), len(heights[0])

    def dfs(r: int, c: int, reachable: set):
        reachable.add((r, c))
        for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            nr, nc = r + dr, c + dc
            if (0 <= nr < rows and 0 <= nc < cols
                    and (nr, nc) not in reachable
                    and heights[nr][nc] >= heights[r][c]):
                dfs(nr, nc, reachable)

    pacific = set()
    atlantic = set()

    for c in range(cols):
        dfs(0, c, pacific)
        dfs(rows - 1, c, atlantic)

    for r in range(rows):
        dfs(r, 0, pacific)
        dfs(r, cols - 1, atlantic)

    return [[r, c] for r, c in pacific & atlantic]

Iterative DFS to avoid stack overflow

For very large grids (1000 x 1000), recursive DFS may hit Python’s recursion limit. Use an explicit stack:

def flood_fill_iterative(image: list[list[int]], sr: int, sc: int, color: int) -> list[list[int]]:
    """
    Iterative DFS flood fill using an explicit stack.
    """
    rows, cols = len(image), len(image[0])
    original = image[sr][sc]

    if original == color:
        return image

    stack = [(sr, sc)]
    image[sr][sc] = color

    while stack:
        r, c = stack.pop()
        for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and image[nr][nc] == original:
                image[nr][nc] = color
                stack.append((nr, nc))

    return image

This uses O(m * n) space in the worst case but avoids recursion depth issues.

Multi-source BFS pattern

Problems 2, 3, and 4 all use multi-source BFS: start BFS from multiple cells simultaneously. The pattern:

1. Identify all starting cells (boundary cells, ocean edges, etc.).
2. Add all starting cells to the queue at once.
3. Run standard BFS.

This is equivalent to adding a virtual super-source connected to all starting cells with zero-weight edges.

def multi_source_bfs_template(grid, start_condition):
    """
    Generic multi-source BFS template.
    start_condition: function(r, c) -> bool to identify start cells.
    """
    rows, cols = len(grid), len(grid[0])
    queue = deque()
    visited = [[False] * cols for _ in range(rows)]

    # Collect all starting cells
    for r in range(rows):
        for c in range(cols):
            if start_condition(r, c):
                queue.append((r, c))
                visited[r][c] = True

    # BFS from all sources simultaneously
    while queue:
        r, c = queue.popleft()
        for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and not visited[nr][nc]:
                # Add problem-specific condition here
                visited[nr][nc] = True
                queue.append((nr, nc))

    return visited

Big-O summary

Problem	Time	Space
Flood Fill	O(m * n)	O(m * n)
Surrounded Regions	O(m * n)	O(m * n)
Number of Enclaves	O(m * n)	O(m * n)
Pacific Atlantic Water Flow	O(m * n)	O(m * n)

All four problems run in linear time relative to the grid size. The space is dominated by the visited set or recursion stack.

Common mistakes

1. Forgetting the base case in flood fill: If the original color equals the new color, DFS recurses infinitely. Always check this before starting.

2. Modifying the grid during iteration incorrectly: Mark cells before adding to queue/stack, not after popping, to avoid duplicate processing and wasted work.

3. Off-by-one on boundaries: When iterating boundary cells, ensure corners are not processed twice.

4. Using a visited set when in-place marking suffices: For problems that allow grid modification, skip the extra set to save space.

5. Forgetting to handle empty grids: Always check if not grid or not grid[0] before accessing dimensions.

Practice problems

Problem	Difficulty	Key Concept
Flood Fill - LeetCode 733	Easy	The classic starting point
Surrounded Regions - LeetCode 130	Medium	Boundary-first DFS/BFS
Number of Enclaves - LeetCode 1020	Medium	Count unreachable land cells
Pacific Atlantic Water Flow - LeetCode 417	Medium	Dual-origin reverse BFS
Number of Islands - LeetCode 200	Medium	Count connected components
Max Area of Island - LeetCode 695	Medium	Flood fill with size tracking
Rotting Oranges - LeetCode 994	Medium	Multi-source BFS with distance

Key takeaways

• Flood fill is DFS or BFS on a grid treating each cell as a graph node with 4-directional edges.
• For “surrounded” problems, invert the question: mark what is NOT surrounded (boundary-connected), then capture the rest.
• Multi-source BFS handles problems where spreading starts from multiple points simultaneously.
• Reverse the flow direction when checking reachability to/from boundaries or oceans.
• Always handle the edge case where original color equals new color in flood fill to prevent infinite loops.
• Use iterative DFS with an explicit stack for large grids to avoid Python’s recursion limit.