AlgoViz
HomeGraphs

Number of enclaves

Medium

Remove border-reachable land, count what remains

Problem

Count land cells (1s) from which you cannot walk off the grid boundary.

In simple words

Sink every land cell reachable from the border, then count the land that's left stranded inside.

The idea

Walk inward from every land cell on the boundary and sink everything reachable, then count the land still standing. Those cells cannot reach an edge, which is the definition of an enclave.

The trick

  • Same border-first idea as surrounded regions.
  • The answer is a simple count after the sinking pass.
1
1
0
0
1
0
0
1
0
0
1
1
0
0
0
1

Step 1 of 9. Scan for land. Each unvisited '1' starts a new island; flood-fill its whole blob so it isn't counted twice.

1/9
Optimal
timeO(rows·cols)spaceO(rows·cols)

Sink each island you find.

1for (r, c) if (grid[r][c] === '1') {2  islands++;3  sink(r, c); // DFS marks the blob as water4}5function sink(r, c) {6  if (out of bounds || grid[r][c] !== '1') return;7  grid[r][c] = '0';8  for (const [dr, dc] of DIRS) sink(r+dr, c+dc);9}

Input

grid
4 × 4

Memory

at
—
cells marked
0

Output

islands
—
answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]
Output:
3
Explanation:
3 land cells can't reach the border.

Example 2

Input:
grid = [[0,1,1,0],[0,0,1,0],[0,0,0,0]]
Output:
0
Explanation:
3 interior land cells are trapped.

Example 3

Input:
grid = [[1,1],[1,0]]
Output:
0
Explanation:
All land touches the edge → 0.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.