Number of Enclaves

Medium · Graphs · Explanation and code example

Disjoint Set Union

How it works

Union-Find provides another perspective on this problem. We create a virtual boundary node and union all boundary land cells with it. We also union adjacent land cells together. After processing, the size of the boundary node's component tells us how many land cells can reach the boundary. The answer is total land minus this count (plus 1 to account for the virtual node itself being counted in the size).

Steps

Create a DSU with size ROWS * COLS + 1, where index N represents the boundary.
For each land cell:
- Count it toward total land.
- Union with adjacent land cells.
- If on the boundary (neighbor out of bounds), union with the virtual boundary node N.
Get the size of the boundary component using find(N).
Return land - borderLand + 1 (the +1 adjusts for the virtual boundary node).

Complexity

Time complexity: O(m * n)
Space complexity: O(m * n)

Where m is the number of rows and n is the number of columns in the given grid.

Things to watch for

Counting All Land Cells Instead of Enclaves Only

A common mistake is to count all land cells that are not on the boundary. However, an enclave is defined as land that cannot reach any boundary cell through adjacent land connections. Interior land cells connected to boundary land are not enclaves and must be excluded from the count.

Starting DFS/BFS From Interior Cells Instead of Boundary

The efficient approach starts traversal from boundary land cells and marks all reachable land. Starting from each interior cell and checking if it can reach the boundary is much slower and prone to errors. Always initiate searches from boundary cells to find non-enclave land.

Off-by-One Errors in Boundary Detection

When checking if a cell is on the boundary, ensure you correctly identify cells where row equals 0 or ROWS - 1, and column equals 0 or COLS - 1. Using incorrect boundary conditions (like row == ROWS instead of row == ROWS - 1) will cause cells to be misclassified as boundary or interior cells.

Python code example

class DSU:
    def __init__(self, n):
        self.Parent = list(range(n + 1))
        self.Size = [1] * (n + 1)

    def find(self, node):
        if self.Parent[node] != node:
            self.Parent[node] = self.find(self.Parent[node])
        return self.Parent[node]

    def union(self, u, v):
        pu, pv = self.find(u), self.find(v)
        if pu == pv:
            return False
        if self.Size[pu] >= self.Size[pv]:
            self.Size[pu] += self.Size[pv]
            self.Parent[pv] = pu
        else:
            self.Size[pv] += self.Size[pu]
            self.Parent[pu] = pv
        return True

class Solution:
    def numEnclaves(self, grid: list[list[int]]) -> int:
        ROWS, COLS = len(grid), len(grid[0])
        N = ROWS * COLS
        def index(r, c):
            return r * COLS + c

        dsu = DSU(N)
        directions = [0, 1, 0, -1, 0]
        land = 0
        for r in range(ROWS):
            for c in range(COLS):
                if grid[r][c] == 0:
                    continue
                land += 1
                for d in range(4):
                    nr, nc = r + directions[d], c + directions[d + 1]
                    if 0 <= nr < ROWS and 0 <= nc < COLS:
                        if grid[nr][nc] == 1:
                            dsu.union(index(r, c), index(nr, nc))
                    else:
                        dsu.union(N, index(r, c))

        borderLand = dsu.Size[dsu.find(N)]
        return land - borderLand + 1

C++ code example

class DSU {
public:
    vector<int> Parent, Size;

    DSU(int n) {
        Parent.resize(n + 1);
        Size.resize(n + 1, 1);
        for (int i = 0; i <= n; i++) {
            Parent[i] = i;
        }
    }

    int find(int node) {
        if (Parent[node] != node) {
            Parent[node] = find(Parent[node]);
        }
        return Parent[node];
    }

    bool unionSets(int u, int v) {
        int pu = find(u), pv = find(v);
        if (pu == pv) return false;
        if (Size[pu] >= Size[pv]) {
            Size[pu] += Size[pv];
            Parent[pv] = pu;
        } else {
            Size[pv] += Size[pu];
            Parent[pu] = pv;
        }
        return true;
    }
};

class Solution {
public:
    int numEnclaves(vector<vector<int>>& grid) {
        int ROWS = grid.size(), COLS = grid[0].size();
        int N = ROWS * COLS;
        DSU dsu(N);
        vector<int> directions = {0, 1, 0, -1, 0};
        int land = 0;

        for (int r = 0; r < ROWS; r++) {
            for (int c = 0; c < COLS; c++) {
                if (grid[r][c] == 0) continue;
                land++;
                for (int d = 0; d < 4; d++) {
                    int nr = r + directions[d], nc = c + directions[d + 1];
                    if (nr >= 0 && nc >= 0 && nr < ROWS && nc < COLS) {
                        if (grid[nr][nc] == 1) {
                            dsu.unionSets(r * COLS + c, nr * COLS + nc);
                        }
                    } else {
                        dsu.unionSets(N, r * COLS + c);
                    }
                }
            }
        }

        int borderLand = dsu.Size[dsu.find(N)];
        return land - borderLand + 1;
    }
};

Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode Watch NeetCode on YouTube

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations