⚡Flashcard Drill➔
NeetCode #591LC-1020MediumGraphs
← Back to All Problems

#591 · #1020 · Number of Enclaves(飞地的数量)

📌 Problem Statement & Constraints

Given an m x n binary matrix grid where 0 is sea and 1 is land, return the number of land cells from which you cannot walk off the grid boundary via 4-directional land moves. Constraints: 1 <= m, n <= 500.

💡 Core Algorithmic Approaches

  1. Any land connected to the border can be walked off, so remove all border-connected land first.
  2. Flood-fill from every border land cell, turning it into sea.
  3. Then count the remaining land -- these are the enclosed cells.
  4. The reverse-reachability trick again avoids per-component border checks.

💻 Benchmark Python3 Implementation

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

        def dfs(r: int, c: int) -> None:
            if not (0 <= r < m and 0 <= c < n) or grid[r][c] == 0:
                return
            grid[r][c] = 0                 # sink the walkable land
            dfs(r + 1, c)
            dfs(r - 1, c)
            dfs(r, c + 1)
            dfs(r, c - 1)

        for i in range(m):                 # top and bottom rows
            dfs(i, 0)
            dfs(i, n - 1)
        for j in range(n):                 # left and right columns
            dfs(0, j)
            dfs(m - 1, j)

        return sum(sum(row) for row in grid)   # whatever land remains is enclosed

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(m * n): each cell is visited a constant number of times.
💾 Space Complexity
O(m * n) for the recursion stack.

⚠️ Interview Pitfalls & Follow-ups

  • Only seeding the corners: the whole border must be seeded.
  • Counting before sinking the border land: those cells must be excluded.
  • Using a separate visited array: in-place sinking is free.
  • Recursing on a 500x500 all-land grid: the depth can reach 250 000; an iterative BFS is safer.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Graphs Problems