1020. Number of Enclaves

Problem¶

Given a binary grid, return the number of land cells that are not connected 4-directionally to any boundary land cell.

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

boundary-connected land = {(1,0)}
output = 3

Key trick¶

Reverse the question: flood-fill all land reachable from the boundary, then count the remaining land.

Trap¶

Checking only whether a cell is on the boundary instead of whether its component reaches the boundary.
Using recursive DFS on a grid with up to \(250{,}000\) cells, which can exceed Python's recursion limit.
Forgetting that a one-row or one-column grid has no enclaves.
Overlooking that an in-place flood-fill modifies the input.

Why is it interesting?¶

It turns a global escape-path question into a simple multi-source boundary traversal.

Python solution¶

class Solution:
    def numEnclaves(self, grid: list[list[int]]) -> int:
        m, n = len(grid), len(grid[0])

        def flood(r,c):
            if grid[r][c] == 0:
                return

            stack = [(r, c)]
            grid[r][c] = 0

            while stack:
                r, c = stack.pop()
                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 grid[nr][nc] == 1:
                        grid[nr][nc] = 0
                        stack.append((nr, nc))

        # Remove every land component connected to the boundary.
        for r in range(m):
            flood(r, 0)
            flood(r, n - 1)

        for c in range(n):
            flood(0, c)
            flood(m - 1, c)

        return sum(map(sum, grid))

Time complexity: \(O(mn)\).

Auxiliary space: \(O(mn)\) in the worst case for the DFS stack.

Comment on my solution¶

Your algorithm is correct and has optimal \(O(mn)\) time complexity. The main issue is recursive DFS: a large connected component can exceed Python's recursion limit, so an iterative stack is safer. Mutating the grid is acceptable for this problem, but it should be intentional because callers cannot reuse the original grid afterward.

# Ideas:
# - It is similar of the surrender problem.
#   - start dfs from 1 on the grid edges and flood fill the land
#   - then count the 1 left on the grid

# WORKS
class Solution:
    def numEnclaves(self, grid: list[list[int]]) -> int:
        m, n = len(grid), len(grid[0])

        def dfs(r,c):
            if grid[r][c] != 1:
                return
            grid[r][c] = 0
            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 grid[nr][nc] == 1:
                    dfs(nr, nc)

        for r in range(m):
            dfs(r, 0)
            dfs(r, n - 1)
        for c in range(n):
            dfs(0, c)
            dfs(m - 1, c)
        ans = 0
        for r in range(m):
            for c in range(n):
               if grid[r][c] == 1:
                   ans += 1
        return ans