LeetCode 1020 - Number of Enclaves

The problem gives us a binary matrix called grid, where: - 0 represents water - 1 represents land We can move only in four directions, up, down, left, and right.

leetcodemediumarraydepth-first-searchbreadth-first-searchunion-findmatrix

LeetCode Problem 1020

Difficulty: 🟡 Medium
Topics: Array, Depth-First Search, Breadth-First Search, Union-Find, Matrix

Solution

Problem Understanding

The problem gives us a binary matrix called grid, where:

  • 0 represents water
  • 1 represents land

We can move only in four directions, up, down, left, and right. A land cell is considered an enclave if there is no possible path from that land cell to any boundary cell of the grid.

Another way to think about the problem is this:

  • If a land region touches the border directly, or can reach the border through connected land cells, then every cell in that region is not enclosed.
  • Only land cells that are completely surrounded by water and disconnected from all borders should be counted.

The task is to return the total number of such enclosed land cells.

The constraints are important:

  • m and n can each be as large as 500
  • The grid may therefore contain up to 250,000 cells

Because of this, we need an algorithm close to linear time, ideally O(m * n). Any solution that repeatedly performs searches from many cells independently can become too slow.

Several edge cases are important:

  • A grid containing only water should return 0
  • A grid where every land cell touches the border should also return 0
  • A single isolated land cell in the middle should return 1
  • Large connected regions that partially touch the border should not count at all
  • Thin paths connecting inner land to the boundary can easily be missed by incorrect implementations

The problem guarantees that the input is always a valid rectangular matrix and every value is either 0 or 1.

Approaches

Brute Force Approach

A straightforward solution is to examine every land cell individually.

For each land cell:

  1. Run a DFS or BFS starting from that cell
  2. Determine whether the connected component can reach the boundary
  3. If it cannot, count all cells in that component as enclaves

This approach is correct because it explicitly checks whether each connected land region can escape the grid.

However, it is inefficient if implemented naively. Imagine a large island in the center of the grid. Starting a DFS from every land cell may repeatedly traverse the same component many times. In the worst case, this can lead to time complexity approaching O((m * n)^2).

With up to 250,000 cells, that is too slow.

Optimal Approach

The key insight is to reverse the perspective.

Instead of asking:

Which land cells are enclosed?

We ask:

Which land cells are definitely not enclosed?

Any land cell connected to the boundary cannot be an enclave.

So we can:

  1. Start DFS or BFS from every boundary land cell
  2. Mark all reachable land cells as safe
  3. Count the remaining unvisited land cells

This works because every non-enclave cell must belong to a component connected to the boundary.

Rather than checking every component repeatedly, we process each cell at most once.

Approach Time Complexity Space Complexity Notes
Brute Force O((m * n)^2) O(m * n) Repeatedly explores the same components
Optimal O(m * n) O(m * n) Flood-fill from the boundary once

Algorithm Walkthrough

  1. Determine the dimensions of the grid.

We store the number of rows and columns because they are used repeatedly throughout the traversal logic. 2. Create a DFS or BFS helper function.

This helper will mark all land cells connected to a starting cell. We use it to remove all land reachable from the boundary. 3. Traverse all boundary cells.

The boundary consists of:

  • First row
  • Last row
  • First column
  • Last column

Any land cell on these edges is automatically not enclosed. 4. Start DFS/BFS from every boundary land cell.

During traversal:

  • Mark visited land cells as water, or store them in a visited structure
  • Continue exploring in four directions

This effectively removes every land region capable of escaping the grid. 5. After all boundary-connected land is removed, scan the entire grid again.

Any remaining 1 cell is guaranteed to be enclosed because:

  • It was never reachable from the boundary
  • Therefore its component is completely surrounded
  1. Count all remaining land cells and return the result.

Why it works

The algorithm relies on a simple invariant:

Any land cell connected to the boundary cannot be an enclave.

By starting from the boundary and marking all reachable land, we eliminate every non-enclave cell. The only cells left are those with no path to the boundary, which exactly matches the definition of enclaves.

Because each cell is processed at most once, the algorithm is both correct and efficient.

Python Solution

from typing import List

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

        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

        def dfs(row: int, col: int) -> None:
            if (
                row < 0 or row >= rows or
                col < 0 or col >= cols or
                grid[row][col] == 0
            ):
                return

            grid[row][col] = 0

            for dr, dc in directions:
                dfs(row + dr, col + dc)

        for row in range(rows):
            if grid[row][0] == 1:
                dfs(row, 0)

            if grid[row][cols - 1] == 1:
                dfs(row, cols - 1)

        for col in range(cols):
            if grid[0][col] == 1:
                dfs(0, col)

            if grid[rows - 1][col] == 1:
                dfs(rows - 1, col)

        enclave_count = 0

        for row in range(rows):
            for col in range(cols):
                if grid[row][col] == 1:
                    enclave_count += 1

        return enclave_count

The implementation begins by storing the grid dimensions and defining the four possible movement directions.

The dfs helper performs the flood-fill operation. If the current cell is out of bounds or already water, recursion stops immediately. Otherwise, the cell is marked as 0, effectively removing it from future consideration.

The next section processes every boundary cell. Whenever a boundary land cell is found, DFS removes the entire connected component.

After this boundary cleanup step, every remaining 1 cell must be enclosed. The final nested loop simply counts them.

An important implementation detail is that the algorithm modifies the input grid in place. This avoids needing an additional visited matrix and reduces memory usage.

Go Solution

func numEnclaves(grid [][]int) int {
    rows := len(grid)
    cols := len(grid[0])

    directions := [][]int{
        {1, 0},
        {-1, 0},
        {0, 1},
        {0, -1},
    }

    var dfs func(int, int)

    dfs = func(row int, col int) {
        if row < 0 || row >= rows ||
            col < 0 || col >= cols ||
            grid[row][col] == 0 {
            return
        }

        grid[row][col] = 0

        for _, dir := range directions {
            newRow := row + dir[0]
            newCol := col + dir[1]

            dfs(newRow, newCol)
        }
    }

    for row := 0; row < rows; row++ {
        if grid[row][0] == 1 {
            dfs(row, 0)
        }

        if grid[row][cols-1] == 1 {
            dfs(row, cols-1)
        }
    }

    for col := 0; col < cols; col++ {
        if grid[0][col] == 1 {
            dfs(0, col)
        }

        if grid[rows-1][col] == 1 {
            dfs(rows-1, col)
        }
    }

    enclaveCount := 0

    for row := 0; row < rows; row++ {
        for col := 0; col < cols; col++ {
            if grid[row][col] == 1 {
                enclaveCount++
            }
        }
    }

    return enclaveCount
}

The Go implementation follows the same logic as the Python version.

One difference is the recursive function declaration. In Go, recursive anonymous functions require a prior variable declaration using:

var dfs func(int, int)

The solution also modifies the grid in place rather than maintaining a separate visited matrix.

Because the maximum grid size is moderate, integer overflow is not a concern. Slice indexing naturally handles the 2D matrix structure cleanly.

Worked Examples

Example 1

Input:

[
  [0,0,0,0],
  [1,0,1,0],
  [0,1,1,0],
  [0,0,0,0]
]

Initial grid:

Row Values
0 [0,0,0,0]
1 [1,0,1,0]
2 [0,1,1,0]
3 [0,0,0,0]

Boundary scan finds:

  • (1,0) is land

Start DFS from (1,0):

Step Cell Visited Grid Change
1 (1,0) Set to 0

Updated grid:

[
  [0,0,0,0],
  [0,0,1,0],
  [0,1,1,0],
  [0,0,0,0]
]

No other boundary land exists.

Now count remaining land cells:

  • (1,2)
  • (2,1)
  • (2,2)

Total enclaves = 3

Example 2

Input:

[
  [0,1,1,0],
  [0,0,1,0],
  [0,0,1,0],
  [0,0,0,0]
]

Boundary land cells:

  • (0,1)
  • (0,2)

Start DFS from (0,1):

Step Cell Visited
1 (0,1)
2 (0,2)
3 (1,2)
4 (2,2)

All connected land is removed.

Final grid:

[
  [0,0,0,0],
  [0,0,0,0],
  [0,0,0,0],
  [0,0,0,0]
]

No land remains.

Answer = 0

Complexity Analysis

Measure Complexity Explanation
Time O(m * n) Each cell is visited at most once
Space O(m * n) Recursive DFS stack may grow to all cells

The algorithm performs a constant amount of work per cell. Even though DFS is initiated multiple times from the boundary, no land cell is processed more than once because visited cells are immediately converted to water.

The recursive call stack can grow large in the worst case, especially when the entire grid is land. Therefore the worst-case auxiliary space complexity is O(m * n).

Test Cases

sol = Solution()

# Example 1
assert sol.numEnclaves([
    [0,0,0,0],
    [1,0,1,0],
    [0,1,1,0],
    [0,0,0,0]
]) == 3  # enclosed island in center

# Example 2
assert sol.numEnclaves([
    [0,1,1,0],
    [0,0,1,0],
    [0,0,1,0],
    [0,0,0,0]
]) == 0  # all land connected to boundary

# Single enclosed cell
assert sol.numEnclaves([
    [0,0,0],
    [0,1,0],
    [0,0,0]
]) == 1  # one isolated enclave

# All water
assert sol.numEnclaves([
    [0,0],
    [0,0]
]) == 0  # no land exists

# All land
assert sol.numEnclaves([
    [1,1],
    [1,1]
]) == 0  # every cell touches boundary indirectly

# Narrow path to boundary
assert sol.numEnclaves([
    [0,1,0,0],
    [0,1,1,0],
    [0,0,1,0],
    [0,0,1,0]
]) == 0  # connected escape path exists

# Multiple enclosed regions
assert sol.numEnclaves([
    [0,0,0,0,0],
    [0,1,0,1,0],
    [0,1,0,1,0],
    [0,0,0,0,0]
]) == 4  # two separate enclave regions

# Single row
assert sol.numEnclaves([
    [1,0,1,1]
]) == 0  # every cell is boundary

# Single column
assert sol.numEnclaves([
    [1],
    [0],
    [1]
]) == 0  # every land cell on boundary
Test Why
Example 1 Validates standard enclave detection
Example 2 Validates boundary-connected removal
Single enclosed cell Smallest non-trivial enclave
All water Ensures zero handling works
All land Ensures complete flood-fill works
Narrow path to boundary Verifies indirect escape detection
Multiple enclosed regions Ensures disconnected enclaves counted correctly
Single row Boundary edge case
Single column Boundary edge case

Edge Cases

A grid containing only water is an important edge case because the DFS should never start. Incorrect implementations sometimes assume at least one land cell exists and may produce errors or incorrect counts. This implementation handles the case naturally because the final counting loop simply finds zero remaining land cells.

Single-row or single-column grids are another subtle scenario. In these grids, every cell is automatically on the boundary. That means no enclave can ever exist. Some implementations accidentally double-process cells or incorrectly treat interior positions as enclosed. The boundary traversal here correctly marks every land cell reachable immediately from the edges.

A large connected island that touches the border through a narrow corridor is another common source of bugs. A naive local check might incorrectly classify deep interior cells as enclosed. This implementation avoids that mistake because the DFS explores the entire connected component from the boundary, ensuring every reachable land cell is removed.

Another important edge case is a fully enclosed island surrounded by water. The algorithm must avoid accidentally removing it during the boundary flood-fill phase. Because DFS starts only from boundary land cells, isolated interior regions remain untouched and are counted correctly in the final pass.