Number of Enclaves

Given an R × C grid of 0s (sea) and 1s (land), a move steps 4-directionally between land cells, and you may walk off the grid only from a boundary cell. Return the number of land cells from which it is impossible to walk off the boundary — the enclaves.

Hints

· Stuck? Reveal one nudge at a time.

A land cell escapes only if it connects (through land) to a boundary cell.

Instead of testing each cell, flood inward from every boundary land cell.

The land that survives the flood is enclosed — count it.

Common doubts

Testing each cell reruns a flood per cell — O((R·C)²). One flood from all boundary sources removes every escapable cell in O(R·C).

Every boundary land cell is an equally valid escape point, so they all seed the same flood simultaneously.

Same border-flood idea: mark what the boundary reaches, then act on the rest.

Interview follow-ups

· What an interviewer asks next.

After the flood, collect the coordinates of surviving land.

Add the four diagonals; more land becomes border-connected, so fewer enclaves.

Fun facts

LeetCode 1020 — the 'walk off the boundary' framing of the border-flood pattern.
The same inward flood underlies surrounded regions and the pacific-atlantic water flow.

Asked at

AmazonGoogle

Frequently Sometimes Occasionally

Example 1

Input: grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,1]]
Output: 3
The inner block of land can't reach the border; the border-touching land can.

Example 2

Input: grid = [[0,0,0],[0,1,0],[0,0,0]]
Output: 1
The single central land cell is fully enclosed.

Constraints

- 1 <= R, C <= 500 - grid[i][j] is 0 or 1

A land cell can escape the grid iff it's connected (through land) to a boundary land cell. So the enclaves are all land minus the land reachable from the border. Instead of testing each cell, flood inward from the boundary: seed every boundary land cell and sink everything reachable. Whatever land survives is enclosed.

This "start from the edge" inversion is a recurring grid trick (it also solves surrounded regions and pacific-atlantic). Multi-source BFS seeds all boundary cells into one queue at once. O(R·C).

Prerequisites

Before you start

· Concepts used directly in the solution.

Boundary seeding. everything escaping must touch the border.

Multi-source BFS. enqueue all sources before spreading.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

Setup

“When can a cell escape?”

Only if connected via land to a boundary land cell.

“4- or 8-directional?”

4-directional.

The ideal opening — say it like this

Land escapes only if it reaches the border, so I flood inward from every boundary land cell and sink it.

The land left standing can't reach the border — that's the enclave count. O(R·C).

Understand the problem

Worked example — grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]

no boundary land is set here -> flood removes nothing on the border
the inner block {(1,2),(2,1),(2,2)} and (1,0)... (1,0) is on the border column? col 0 is boundary -> escapes
enclosed land = {(1,2),(2,1),(2,2)} = 3

Key observations

1Aha

Escape ⟺ reach the boundary

A cell is an enclave exactly when it can't reach a border land cell.

2Aha

Flood from the border, not each cell

One inward flood removes all escapable land.

3Aha

Surviving land = enclaves

Count the 1s left after the flood.

Brute force vs optimal

	Boundary DFS	Multi-source BFS
Seeds	recurse from each boundary land cell	all boundary land in one queue
Time	O(R·C)	O(R·C)
Risk	deep recursion	none

Both remove border-connected land and count the rest. Full code is in the Approaches selector below.

Summary

Key takeaway

Flood inward from every boundary land cell and sink it; the land that survives can't escape — that's the enclave count. O(R·C).

seed all boundary land into the flood; sink reachable land
answer = remaining 1s