Number of Enclaves

Number of Enclaves

What is this problem about?

The Number of Enclaves problem gives you a binary matrix where 1 represents land and 0 represents water. Find the number of land cells that cannot reach the boundary by moving only through adjacent land cells. These are "enclosed" land cells. This Number of Enclaves coding problem uses boundary flood-fill followed by counting.

Why is this asked in interviews?

Microsoft, Amazon, Google, and Bloomberg ask this as a direct variant of the flood-fill pattern. It reinforces the "eliminate boundary-connected cells, count the rest" technique. The array, matrix, union find, BFS, and DFS interview pattern is the core, and the problem tests systematic grid traversal with flood-fill.

Algorithmic pattern used

Boundary flood-fill + count remaining. DFS/BFS from all boundary land cells (value=1), marking them visited (setting to 0 or a separate mark). After all boundary-connected land is eliminated, count the remaining 1-cells. Each remaining cell cannot reach the boundary.

Example explanation

Matrix:

0 0 0 0
1 0 1 0
0 1 1 0
0 0 0 0

Boundary land cells: none (all boundary cells are 0). Interior land cells: (1,2),(2,1),(2,2). From (1,2): can it reach boundary? Only connects to (2,2) which connects to (2,1). None touch boundary → all 3 are enclaves. Count = 3.

Common mistakes candidates make

• Forgetting to flood-fill from ALL four boundary edges (top row, bottom row, left column, right column).
• Counting all land cells, not just non-boundary-connected ones.
• Using BFS but missing land cells on the corners.
• Not restoring the grid after modification (if in-place modification affects the count).

Interview preparation tip

Number of Enclaves and Number of Closed Islands are variations of the same pattern: flood-fill from boundaries to eliminate non-enclosed regions, then count what remains. The difference: Closed Islands counts connected groups; Enclaves counts individual cells. Mastering the boundary flood-fill template (iterate all 4 edges, DFS from every boundary land/water cell) solves both problems. Practice this template until boundary edge iteration is automatic.