Number of Enclaves: Border-Connected Flood Fill

You are given an m x n binary matrix grid, where 0 represents a sea cell and 1 represents a land cell. A move consists of walking from one land cell to another adjacent (4-directionally) land cell or walking off the boundary of the grid. Return the number of land cells in grid for which you cannot walk off the boundary of the grid.

This is LeetCode 1020: Number of Enclaves, and it is one of the cleanest problems for learning the boundary flood fill pattern. The technique it teaches shows up any time you need to classify cells based on whether they can reach the edge of a grid.

Why this problem matters

Grid problems often ask you to explore connected regions using DFS or BFS. Number of Enclaves adds a twist: instead of counting all connected components, you only care about land cells that are completely surrounded by water, with no path to the boundary. The naive approach of checking every land cell to see if it can reach an edge is expensive and redundant. The boundary flood fill pattern solves it in a single pass.

This "eliminate from the boundary" technique is a recurring pattern in grid problems. You will see it in Surrounded Regions (LeetCode 130), where you flip all interior O's to X's. You will see it in Pacific Atlantic Water Flow (LeetCode 417), where you BFS inward from both ocean borders. And you will see it in any problem that asks "which cells are trapped inside the grid?"

Once you internalize this pattern, you recognize the cue immediately: "can this cell reach the boundary?" means "start from the boundary and flood fill inward."

The key insight

Instead of checking each land cell to see if it can reach the boundary (which could mean running a full BFS from every single land cell), flip the problem around. Start from every land cell that sits on the boundary and flood fill inward. Mark every cell you can reach as "border-connected." When you are done, any land cell that is still unmarked cannot reach the boundary. Those are your enclaves.

This is the same idea behind Surrounded Regions (LeetCode 130). There, you start from border O's and mark them safe, then flip everything else. Here, you start from border 1's and mark them reachable, then count everything else.

The algorithm:

1. Scan all four edges of the grid. For every land cell on the boundary, add it to a BFS queue and mark it as visited (set it to 0).
2. Run BFS. For each cell in the queue, check its four neighbors. If a neighbor is land (1), mark it as 0 and add it to the queue.
3. When BFS finishes, every remaining 1 in the grid is an enclave. Sum them up.

The solution

from collections import deque

def num_enclaves(grid: list[list[int]]) -> int:
    rows, cols = len(grid), len(grid[0])

    queue = deque()
    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

    while queue:
        r, c = queue.popleft()
        for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            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))

    return sum(grid[r][c] for r in range(rows) for c in range(cols))

Let's walk through what each piece does.

The first loop scans every cell in the grid, but it only cares about cells on the boundary (where r == 0, r == rows - 1, c == 0, or c == cols - 1). If a boundary cell is land, it gets added to the queue and immediately set to 0. This both marks it as visited and "removes" it from the grid so it will not be counted later.

The BFS loop processes cells from the queue. For each cell, it checks all four neighbors. If a neighbor is land, it gets the same treatment: set to 0 and added to the queue. This flood fill radiates inward from every border land cell, erasing every land cell that has a path to the boundary.

After BFS completes, the only 1s left in the grid are land cells that were never reached from any border. The final sum counts them. That count is the answer.

Visual walkthrough

Let's trace through the algorithm on the example grid step by step. Watch how the boundary scan identifies starting points, the BFS eliminates reachable land, and the remaining cells become the answer.

The key observation: cell (1,0) is the only land cell on the boundary. BFS starts there but finds no adjacent land cells to spread to. The three interior land cells at (1,2), (2,1), and (2,2) are completely surrounded by water and were never visited. They are the enclaves.

Complexity analysis

Time is O(m * n) where m is the number of rows and n is the number of columns. The boundary scan visits every cell once. The BFS visits each cell at most once because we set cells to 0 before enqueueing them, preventing duplicates. The final sum iterates through the grid one more time. All three passes are O(m * n), so total time is linear in the grid size.

Space is O(m * n) in the worst case. If the entire boundary is land and all cells are connected, the BFS queue could hold up to m * n entries. In practice, the queue holds only the current frontier, which is much smaller. If you use DFS instead of BFS, the recursion stack could also reach O(m * n) depth in a worst-case spiral grid.

The building blocks

1. Boundary cell identification

The pattern of scanning the edges of a grid to find starting points:

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

This is the "start from the edges" setup. You iterate through every cell but filter for boundary positions. This same scan appears in Surrounded Regions (scan for border O's), Pacific Atlantic Water Flow (scan for cells touching each ocean), and any problem where boundary cells have special meaning. The condition r == 0 or r == rows - 1 or c == 0 or c == cols - 1 captures all four edges in a single pass.

2. Flood fill from boundary

The pattern of BFS that erases reachable cells by modifying the grid in place:

while queue:
    r, c = queue.popleft()
    for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
        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))

This is standard grid BFS with one twist: instead of maintaining a separate visited set, you mark cells by flipping their value. Setting grid[nr][nc] = 0 before appending ensures no cell is processed twice. This in-place marking trick saves space and simplifies the code. You will reuse this pattern in Number of Islands (mark visited islands), Surrounded Regions (mark safe O's), and any grid traversal where you can afford to modify the input.

Edge cases

Before submitting, think through these scenarios:

• All water: no land cells at all. The answer is 0.
• All land: every cell is 1. Every cell on the boundary is land, so BFS reaches everything. The answer is 0.
• Single row or single column: every cell is on the boundary. No cell can be an enclave. The answer is 0.
• 1x1 grid: the single cell is on the boundary. If it is land, it is not an enclave. The answer is 0.
• No border land cells: all border cells are water, but interior cells are land. BFS queue starts empty, so nothing is erased. Every interior land cell is an enclave.
• Large connected island touching the border: one border land cell connects to a massive interior region. BFS erases the entire region. None of those cells are enclaves.

From understanding to recall

You have seen how boundary flood fill works: scan the edges, BFS inward, and count what is left. The logic is clean and the code is short. But writing it correctly under pressure requires more than understanding. You need to recall the boundary scanning condition, the in-place marking trick, and the final counting step without hesitation.

The details that trip people up are small but costly. Do you scan all four edges or just two? Do you mark cells before or after enqueueing? Do you count remaining 1's or remaining 0's? These are not conceptual gaps. They are recall gaps, and they show up when the clock is ticking. Spaced repetition closes them. You practice writing the boundary scan and the flood fill loop from memory at increasing intervals until the pattern is automatic.

Related posts

• Surrounded Regions - The same boundary flood fill pattern, where you mark border-connected O's and flip the rest
• Number of Islands - The foundational grid DFS/BFS problem that teaches flood fill on a 2D matrix
• Pacific Atlantic Water Flow - Multi-source BFS from boundaries, using the same "start from edges" strategy

CodeBricks breaks Number of Enclaves into its boundary scanning and flood fill building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a boundary flood fill problem shows up in your interview, you do not think about it. You just write it.