LeetCode #1020 Medium

Number of Enclaves

In a binary grid where 1 is land, you may walk between adjacent land cells and step off the grid from a border cell. Return the number of land cells from which you can never walk off.

graphsdfsbfsmatrix

Open on LeetCode ↗

02

Intuition

💡

This is Surrounded Regions with the answer counted rather than flipped. Walking off the grid is only possible from the border, so a land cell can escape exactly when it is connected to border land. Flood inward from every border land cell, mark what you reach, and count the land cells that were never marked — those are the enclaves. Recognising the shared structure is the point: the same border-flood idea solves a whole family of grid problems.

03

Approach

1

Restate 'can walk off the grid' as reachability

You can leave the grid only by stepping off an edge, which requires standing on a border cell. Since movement is between adjacent land cells, a cell can escape precisely when a path of land connects it to a border land cell. So 'cannot walk off' means 'not connected to the border'.

2

Flood from the border

Seed a traversal with every land cell in the first row, last row, first column, and last column. DFS or BFS from those seeds, sinking each reached cell to 0 (or marking it in a separate visited grid). Everything reachable from the border is now removed from consideration.

3

Count what remains

Sum the grid. Every 1 still standing is land that could not reach the border, which is exactly an enclave cell. Note the problem asks for the number of cells, not the number of enclosed regions — a single enclosed blob of five cells contributes 5, not 1. Sinking in place avoids allocating a visited array; if the input must not be mutated, use a separate boolean grid instead.

04

Solution & live demo

python

▶1class Solution:
▶2    def numEnclaves(self, grid):
▶3        R, C = len(grid), len(grid[0])
▶4        stack = []
▶5        for r in range(R):
▶6            for c in range(C):
▶7                if (r in (0, R - 1) or c in (0, C - 1)) and grid[r][c] == 1:
▶8                    stack.append((r, c))
▶9                    grid[r][c] = 0
▶10        while stack:
▶11            r, c = stack.pop()
▶12            for dr, dc in ((1,0), (-1,0), (0,1), (0,-1)):
▶13                nr, nc = r + dr, c + dc
▶14                if 0 <= nr < R and 0 <= nc < C and grid[nr][nc] == 1:
▶15                    grid[nr][nc] = 0
▶16                    stack.append((nr, nc))
▶17        return sum(map(sum, grid))

05

Edge cases

All land touches the border

The flood sinks everything and the count is 0.

No land at all

No seeds, nothing to count, answer 0.

Single row or column

Every cell is a border cell, so no enclave can exist and the answer is 0.

Multiple separate enclaves

All of their cells are counted together, since the problem asks for a cell count rather than a region count.

06

Complexity

Time

O(m x n)

Space

O(m x n)

Each cell is pushed at most once. Sinking cells in place removes the need for a separate visited grid.