LeetCode 1020: Number of Enclaves

Problem Restatement

We are given a binary matrix grid where 0 represents sea and 1 represents land.

A move consists of walking from one land cell to an adjacent (4-directional) land cell.

We need to return the number of land cells from which it is impossible to walk off the boundary of the grid.

Land cells connected to the boundary are not counted.

The official constraints state that m == grid.length, n == grid[i].length, 1 <= m, n <= 500, and grid[i][j] is either 0 or 1.

Input and Output

Item	Meaning
Input	Binary matrix `grid`
Output	Number of inland land cells with no path to the boundary

Function shape:

def numEnclaves(grid: list[list[int]]) -> int:
    ...

Examples

Example 1:

grid = [
    [0, 0, 0, 0],
    [1, 0, 1, 0],
    [0, 1, 1, 0],
    [0, 0, 0, 0],
]

The land cell at (1, 0) is on the left boundary and can walk off.

The cells at (1, 2), (2, 1), (2, 2) form an interior cluster with no boundary connection.

Answer:

Example 2:

grid = [
    [0, 1, 1, 0],
    [0, 0, 1, 0],
    [0, 0, 1, 0],
    [0, 0, 0, 0],
]

All land cells are connected to the top boundary.

Answer:

Key Insight

Any land cell connected (directly or indirectly) to a boundary land cell can reach the boundary.

So we find all land cells reachable from the boundary using BFS or DFS. The remaining land cells are enclaves.

Algorithm

Add all boundary land cells to a queue.
BFS: mark all reachable land cells.
Count remaining land cells that are not marked.

Correctness

BFS from boundary land cells visits exactly the land cells that are connected to the boundary.

All remaining land cells form enclaves because they have no path to the boundary.

Edge Cases

Mark nodes or cells as visited at enqueue/discovery time to avoid duplicate work.
Return the failure value when the destination is unreachable.
Check grid or graph boundaries before reading neighbors.

Complexity

Let m and n be the grid dimensions.

Metric	Value	Why
Time	`O(m * n)`	Each cell is visited at most once
Space	`O(m * n)`	Queue and visited set

Common Pitfalls

Do not optimize away the invariant; the code should still make it clear what condition is being maintained.
Prefer problem-specific names over one-letter variables once the logic becomes stateful.

Implementation

from collections import deque

class Solution:
    def numEnclaves(self, grid: list[list[int]]) -> int:
        m, n = len(grid), len(grid[0])
        visited = [[False] * n for _ in range(m)]
        queue = deque()

        for r in range(m):
            for c in range(n):
                if (r == 0 or r == m - 1 or c == 0 or c == n - 1) and grid[r][c] == 1:
                    queue.append((r, c))
                    visited[r][c] = True

        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 < m and 0 <= nc < n and not visited[nr][nc] and grid[nr][nc] == 1:
                    visited[nr][nc] = True
                    queue.append((nr, nc))

        return sum(
            grid[r][c] == 1 and not visited[r][c]
            for r in range(m)
            for c in range(n)
        )

Code Explanation

Initialize BFS from all boundary land cells:

if (r == 0 or r == m - 1 or c == 0 or c == n - 1) and grid[r][c] == 1:
    queue.append((r, c))
    visited[r][c] = True

Expand BFS to all reachable land cells:

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 < m and 0 <= nc < n and not visited[nr][nc] and grid[nr][nc] == 1:
            visited[nr][nc] = True
            queue.append((nr, nc))

Count land cells not reached by BFS:

return sum(
    grid[r][c] == 1 and not visited[r][c]
    for r in range(m)
    for c in range(n)
)

Testing

def run_tests():
    s = Solution()

    assert s.numEnclaves([
        [0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]
    ]) == 3

    assert s.numEnclaves([
        [0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]
    ]) == 0

    assert s.numEnclaves([[1]]) == 0
    assert s.numEnclaves([[0,0],[0,1]]) == 0

    print("all tests passed")

run_tests()

Test	Expected	Why
Interior cluster	`3`	Three inland land cells
Border-connected	`0`	All land touches the boundary
Single land cell at boundary	`0`	It is on the boundary
Land cell at corner	`0`	Corner is a boundary cell