Number of Enclaves — Boundary Flood Fill That Trips Up Candidates

Problem Statement

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

Constraints:

m == grid.length
n == grid[0].length
1 <= m, n <= 500
grid[i][j] is 0 or 1

Example 1:

Input:
0 0 0 0
1 0 1 0
0 1 1 0
0 0 0 0
 
Output: 3
Explanation: The three land cells at (1,2), (2,1), (2,2) form an island
             that has no connection to the grid boundary.

Example 2:

Input:
0 1 1 0
0 0 1 0
0 0 1 0
0 0 0 0
 
Output: 0
Explanation: All land cells are connected to the right edge of the grid.

Example 3:

Input:
0 0 0
0 1 0
0 0 0
 
Output: 1
Explanation: The single land cell at (1,1) is completely enclosed by sea.

Why This Problem Matters

Number of Enclaves is a rite of passage for the "eliminate from boundary" pattern — one of the most versatile tricks in grid interview problems. It appears at Amazon and Google as a medium-difficulty question that separates candidates who only know standard flood fill from those who understand how to invert the problem framing.

The naive approach — for each land cell, do a DFS to check if it can reach the border — is O((m*n)^2) because each DFS can visit the entire grid. The efficient approach is to run DFS just once, from every boundary land cell, marking everything reachable. Then count the surviving land cells in a single scan. Total work is O(m*n).

This pattern directly transfers to LC 130 (Surrounded Regions), where you also start from the boundary and mark, then flip/count the interior. Understanding Number of Enclaves means you understand Surrounded Regions for free, because the core logic is identical.

The Core Insight

Land cells that can walk off the boundary are exactly the land cells reachable from some boundary land cell via 4-directional movement through land. Instead of checking each interior cell individually, flood-fill outward from every border land cell. Any cell you visit during this flood-fill is "not an enclave." Everything not visited is an enclave.

The two-step algorithm:

Flood-fill (DFS or BFS) from every land cell on the four borders, marking visited cells (e.g., setting them to 0 or using a visited set).
Count all remaining land cells (1s) — these are the enclaves.

The insight is that you run the traversal exactly once, from the outside in, rather than from each inside cell trying to find the outside. The boundary cells are the seeds; the unreachable interior is what you want to count.

Visual Dry Run

Input:

Step 1 — Scan all four border rows/columns for land cells:

Top row: no land
Bottom row: no land
Left column: (1,0) = 1 → DFS from here
Right column: no land

Step 2 — DFS from (1,0): Visit (1,0), mark as 0. Neighbors: (0,0)=0, (2,0)=0, (1,1)=0. Dead end.

Grid after boundary flood-fill:

Step 3 — Count remaining land cells: (1,2), (2,1), (2,2) → answer = 3.

Common Mistakes

1. Running DFS from interior cells instead of boundary cells. The classic mistake is to DFS from every land cell and check if any DFS reaches the boundary. This is O((m*n)^2) — for a 500x500 grid that is potentially 250 000 full-grid DFS runs. Always seed from the boundary and flood inward.

2. Not scanning all four borders. The boundary consists of four edges: top row, bottom row, left column, right column. Missing even one edge leaves boundary-connected land cells uncleaned, inflating the count. Iterate all four edges explicitly.

3. Counting cells before flood-filling. Some candidates count all land cells first, then subtract the boundary-reachable count. This is correct in concept but error-prone because you must count only the cells eliminated by the flood-fill, not the total boundary-reachable cells (which might overlap with already-counted cells). Counting survivors after flood-fill is cleaner.

4. Modifying the input grid causes issues in multi-test environments. The flood-fill mutates the grid. In LeetCode this is fine, but mention in interviews that you could use a separate visited boolean grid if mutation is not allowed. The algorithm structure is identical either way.

5. Using wrong adjacency (8-directional instead of 4-directional). The problem specifies 4-directional movement. Using 8-directional adjacency would merge islands that are only diagonally touching, incorrectly reducing the enclave count.

6. Off-by-one when iterating borders. When iterating the left and right columns, make sure r ranges from 0 to ROWS - 1 inclusive (not ROWS). Similarly for top and bottom rows. A common error is to iterate range(1, ROWS - 1) thinking you only need the middle of the column edges.

Solutions

Python

def numEnclaves(grid: list[list[int]]) -> int:
    ROWS, COLS = len(grid), len(grid[0])
 
    def dfs(r: int, c: int) -> None:
        # Out of bounds, sea cell, or already visited — stop recursion
        if r < 0 or r >= ROWS or c < 0 or c >= COLS or grid[r][c] != 1:
            return
        grid[r][c] = 0              # mark this cell as "reachable from boundary"
        # Explore all four neighbors
        dfs(r + 1, c)
        dfs(r - 1, c)
        dfs(r, c + 1)
        dfs(r, c - 1)
 
    # Step 1: flood-fill from every land cell on the left and right borders
    for r in range(ROWS):
        if grid[r][0] == 1:         # left column border cell
            dfs(r, 0)
        if grid[r][COLS - 1] == 1:  # right column border cell
            dfs(r, COLS - 1)
 
    # Step 1 (continued): flood-fill from top and bottom border rows
    for c in range(COLS):
        if grid[0][c] == 1:         # top row border cell
            dfs(0, c)
        if grid[ROWS - 1][c] == 1:  # bottom row border cell
            dfs(ROWS - 1, c)
 
    # Step 2: count surviving land cells — these are the enclaves
    count = 0
    for r in range(ROWS):
        for c in range(COLS):
            if grid[r][c] == 1:     # not reachable from any border
                count += 1
    return count

JavaScript

var numEnclaves = function(grid) {
    const ROWS = grid.length;
    const COLS = grid[0].length;
 
    // DFS to mark all land reachable from (r, c) as visited (set to 0)
    function dfs(r, c) {
        // Base case: out of bounds or not a land cell
        if (r < 0 || r >= ROWS || c < 0 || c >= COLS || grid[r][c] !== 1) return;
 
        grid[r][c] = 0;   // mark as boundary-reachable (eliminate from enclave count)
 
        // Recurse into 4-directional neighbors
        dfs(r + 1, c);
        dfs(r - 1, c);
        dfs(r, c + 1);
        dfs(r, c - 1);
    }
 
    // Step 1: flood-fill from left and right column borders
    for (let r = 0; r < ROWS; r++) {
        if (grid[r][0] === 1) dfs(r, 0);           // left border
        if (grid[r][COLS - 1] === 1) dfs(r, COLS - 1); // right border
    }
 
    // Step 1 (continued): flood-fill from top and bottom row borders
    for (let c = 0; c < COLS; c++) {
        if (grid[0][c] === 1) dfs(0, c);           // top border
        if (grid[ROWS - 1][c] === 1) dfs(ROWS - 1, c); // bottom border
    }
 
    // Step 2: count remaining land cells — these are enclave cells
    let count = 0;
    for (let r = 0; r < ROWS; r++) {
        for (let c = 0; c < COLS; c++) {
            if (grid[r][c] === 1) count++; // still land means unreachable from border
        }
    }
    return count;
};

Complexity Analysis

Approach	Time	Space	Notes
Boundary flood-fill + count (optimal)	O(m*n)	O(m*n)	Each cell visited at most once; recursion stack O(m*n) worst case
DFS from each interior cell	O((m*n)^2)	O(m*n)	Full DFS for every land cell — too slow for large grids
Union-Find with virtual border node	O(mn alpha(m*n))	O(m*n)	Correct and elegant but more complex to implement

The boundary flood-fill approach is optimal. Each cell is visited at most once (once set to 0, it is never re-entered). The final counting scan is a single O(m*n) pass. Recursion depth can reach O(m*n) in the worst case (a single long snake of land cells); for very large grids, replace recursion with an explicit stack to avoid stack overflow.

Follow-up Questions

Q: What if you cannot mutate the grid? Use a visited = [[False]*COLS for _ in range(ROWS)] boolean grid. DFS marks visited[r][c] = True instead of modifying grid[r][c]. The boundary seeds and counting logic remain identical.

Q: How does this differ from LC 130 Surrounded Regions? Surrounded Regions asks you to flip all interior 'O' cells (enclaves) to 'X'. The algorithm is identical: flood-fill from boundary 'O' cells to mark them safe, then iterate the grid flipping all un-marked 'O' to 'X'. Number of Enclaves counts; Surrounded Regions mutates.

Q: What if we also want to return which cells are enclaves, not just the count? After the boundary flood-fill, collect all (r, c) pairs where grid[r][c] == 1. That is the full enclave cell list.

Q: Can you solve this with BFS instead of DFS? Yes. Replace the recursive DFS with a queue-based BFS. Seed the queue with all boundary land cells, then process in BFS order, setting each visited cell to 0. The final count is identical. BFS avoids recursion depth issues for very large grids.

This Pattern Solves

LC 130 — Surrounded Regions (flip interior O cells to X)
LC 200 — Number of Islands (standard flood-fill baseline)
LC 695 — Max Area of Island
LC 1254 — Number of Closed Islands (count 0-islands not touching border)
LC 417 — Pacific Atlantic Water Flow (reverse BFS from two borders)

Key Takeaways

Invert the problem: instead of checking if each interior cell can reach the boundary, flood-fill from all boundary cells inward
Seed DFS/BFS from all four border edges (top, bottom, left, right columns) — missing even one edge produces wrong answers
After flood-filling boundary-connected land to 0, count surviving 1s — those are the enclaves
Time O(mn), space O(mn) — each cell visited at most once; far better than O((m*n)^2) naive approach
This boundary-elimination pattern directly transfers to LC 130 (Surrounded Regions) — same algorithm, different final action
Mutation of the grid is acceptable in interviews — mention you could use a separate visited array if mutation is forbidden
4-directional connectivity only — diagonal neighbors do not count as connected in this problem

Problem Statement#

Why This Problem Matters#

The Core Insight#

Visual Dry Run#

Common Mistakes#

Solutions#

Python#

JavaScript#

Complexity Analysis#

Follow-up Questions#

This Pattern Solves#

Key Takeaways#

Related reading