Number of Enclaves: Count Land Cells Trapped in a Grid

65.1k
0

Given an R × C binary grid where 1 represents land and 0 represents water, return the number of land cells unable to reach the boundary of the grid.

A land cell can move only to another land cell in four directions: up, down, left, and right. A land cell is an enclave when no path from the cell reaches any boundary cell.

number of enclaves

number of enclaves

Example 1

Input: grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]

Output: 3

Explanation: The boundary land cell at (1, 0) can escape. The three middle land cells cannot reach any boundary.

Example 2

Input: grid = [[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]

Output: 0

Explanation: All land cells connect to boundary land, so no enclave land cell remains.

Approach 1

Depth First Search removes every land cell connected to the grid boundary. Boundary-connected land can reach the boundary and therefore cannot form an enclave.

After all boundary-connected regions are removed, every remaining land cell is enclosed by water. A final grid traversal counts such enclosed cells.

Algorithm

  • Traverse the first and last columns across all rows, followed by the first and last rows across all columns. Such traversal identifies every boundary cell without scanning the entire grid for starting points.

  • Start DFS whenever a boundary cell contains land, since the complete connected region containing such a cell cannot contribute to the enclave count.

  • End the current DFS call when the row or column falls outside the grid or when the current cell contains water, as further traversal along such a path cannot reach unprocessed land.

  • Change the current land cell to water before exploring adjacent cells. Early modification marks the cell as processed and prevents repeated recursive visits.

  • Continue DFS in the upward, downward, left, and right directions to remove every land cell connected to the boundary.

  • Traverse the complete grid after all DFS calls finish and count cells still containing land, as only enclosed land remains.

  • Return the final count of enclosed land cells.

Dry Run

number of enclaves 1

number of enclaves 1

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Removes all land cells connected to the current boundary land cell.
void dfs(int row, int col, vector<vector<int>>& grid) {
int rows = grid.size();
int cols = grid[0].size();
// Base case: stop if the cell is outside the grid or is water.
if (row < 0 || col < 0 || row >= rows || col >= cols || grid[row][col] == 0) {
return;
}
// Mark the current land cell as visited by changing it to water.
grid[row][col] = 0;
// Move to the upper cell.
dfs(row - 1, col, grid);
// Move to the lower cell.
dfs(row + 1, col, grid);
// Move to the left cell.
dfs(row, col - 1, grid);
// Move to the right cell.
dfs(row, col + 1, grid);
}
public:
// Counts land cells that cannot reach the boundary.
int numEnclaves(vector<vector<int>>& grid) {
int rows = grid.size();
int cols = grid[0].size();
// Remove boundary-connected land from the left and right edges.
for (int row = 0; row < rows; row++) {
dfs(row, 0, grid);
dfs(row, cols - 1, grid);
}
// Remove boundary-connected land from the top and bottom edges.
for (int col = 0; col < cols; col++) {
dfs(0, col, grid);
dfs(rows - 1, col, grid);
}
int enclaves = 0;
// Count the remaining land cells.
for (int row = 0; row < rows; row++) {
for (int col = 0; col < cols; col++) {
enclaves += grid[row][col];
}
}
// Return the number of enclave cells.
return enclaves;
}
};
// Driver code.
int main() {
vector<vector<int>> grid = {
{0, 0, 0, 0},
{1, 0, 1, 0},
{0, 1, 1, 0},
{0, 0, 0, 0}
};
Solution sol;
cout << sol.numEnclaves(grid);
return 0;
}

Complexity Analysis

Time Complexity: O(R×C), where R and C are the numbers of rows and columns; every grid cell is processed a constant number of times.

Space Complexity: O(R×C), where the recursive DFS stack can contain up to R×C land cells in the worst case.

Approach 2

Multi-source Breadth First Search begins from all boundary land cells simultaneously. Every land cell reachable from a boundary source is removed because boundary reachability prevents enclave membership.

Recoloring boundary land before queue insertion marks each cell as processed. After queue processing finishes, a final traversal counts the land cells that remain enclosed.

Algorithm

  • Initialize an empty queue to store boundary-connected land cells awaiting exploration.

  • Traverse all boundary cells and add every land cell to the queue, since every boundary land cell acts as a starting source for BFS.

  • Change each boundary land cell to water before queue insertion. Early modification prevents duplicate queue entries, especially at corner cells.

  • Continue processing while the queue contains cells, ensuring that every land cell connected to any boundary source is explored.

  • Remove the front cell and examine neighboring cells in the upward, downward, left, and right directions.

  • For every in-bounds neighbor containing land, change the value to water before adding the coordinates to the queue. Early modification prevents repeated processing through another neighboring cell.

  • Traverse the complete grid after BFS finishes and count cells still containing land, as every remaining land cell is enclosed.

  • Return the final count of enclosed land cells.

Dry Run

number-of-enclaves-bfs-initial-grid-corrected

number-of-enclaves-bfs-initial-grid-corrected

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Counts land cells that cannot reach the boundary.
int numEnclaves(vector<vector<int>>& grid) {
int rows = grid.size();
int cols = grid[0].size();
queue<pair<int, int>> q;
vector<int> deltaRow = {-1, 1, 0, 0};
vector<int> deltaCol = {0, 0, -1, 1};
// Add land cells from the left and right boundaries.
for (int row = 0; row < rows; row++) {
for (int col : {0, cols - 1}) {
// If boundary cell is land, mark and push it.
if (grid[row][col] == 1) {
grid[row][col] = 0;
q.push({row, col});
}
}
}
// Add land cells from the top and bottom boundaries.
for (int col = 0; col < cols; col++) {
for (int row : {0, rows - 1}) {
// If boundary cell is land, mark and push it.
if (grid[row][col] == 1) {
grid[row][col] = 0;
q.push({row, col});
}
}
}
// Remove all land connected to boundary land cells.
while (!q.empty()) {
pair<int, int> cell = q.front();
q.pop();
// Explore all four adjacent directions.
for (int dir = 0; dir < 4; dir++) {
int nextRow = cell.first + deltaRow[dir];
int nextCol = cell.second + deltaCol[dir];
// Check if the next cell is inside the grid.
if (nextRow >= 0 && nextCol >= 0 && nextRow < rows && nextCol < cols) {
// If connected cell is land, mark and push it.
if (grid[nextRow][nextCol] == 1) {
grid[nextRow][nextCol] = 0;
q.push({nextRow, nextCol});
}
}
}
}
int enclaves = 0;
// Count the remaining land cells.
for (int row = 0; row < rows; row++) {
for (int col = 0; col < cols; col++) {
enclaves += grid[row][col];
}
}
// Return the number of enclave cells.
return enclaves;
}
};
// Driver code.
int main() {
vector<vector<int>> grid = {
{0, 1, 1, 0},
{0, 0, 1, 0},
{0, 0, 1, 0},
{0, 0, 0, 0}
};
Solution sol;
cout << sol.numEnclaves(grid);
return 0;
}

Complexity Analysis

Time Complexity: O(R×C), where R and C are the numbers of rows and columns; every cell enters the queue at most once and the final scan examines all cells.

Space Complexity: O(R×C), where the queue can store up to R×C land-cell coordinates in the worst case.

Approach 3

Disjoint Set Union represents every grid cell with a unique node and introduces one additional virtual boundary node. Merging boundary land cells with the virtual node places all boundary-connected land cells in the same set as the virtual boundary node.

Adjacent land cells are merged into common sets. After all unions finish, any land cell outside the set containing the virtual boundary node belongs to an enclave. Union by size may select another node as the set root, so connectivity must be checked using DSU representatives rather than assuming that the virtual node remains the root.

Algorithm

  • Initialize a DSU structure with R×C+1 nodes, where the first R×C nodes represent grid cells and the final node represents the virtual boundary.

  • Map the cell at row r and column c to node identifier r×C+c, allowing two-dimensional coordinates to work with one-dimensional DSU arrays.

  • Traverse every grid cell and process only land cells, since water cells do not participate in land connectivity.

  • Merge every boundary land cell with the virtual boundary node, placing all boundary-connected land components in the same DSU set as the virtual node.

  • Merge each land cell with the right and downward land neighbors, avoiding duplicate processing of undirected connections.

  • After all unions finish, compare find(cellNode) with find(virtualBoundary) for every land cell, ensuring that connectivity is checked through the current set representatives.

  • Increment the enclave count when both representatives differ, then return the final count.

Dry Run

number-of-enclaves-dsu-corrected

number-of-enclaves-dsu-corrected

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Finds the representative parent using path compression.
int findParent(int node, vector<int>& parent) {
// Base case: the node is its own parent.
if (parent[node] == node) {
return node;
}
// Compress the path while finding the parent.
parent[node] = findParent(parent[node], parent);
// Return the ultimate parent.
return parent[node];
}
// Merges two sets using union by size.
void unite(int first, int second, vector<int>& parent, vector<int>& size) {
// Find the parent of the first node.
int pFirst = findParent(first, parent);
// Find the parent of the second node.
int pSecond = findParent(second, parent);
// If both nodes are already in the same set, stop.
if (pFirst == pSecond) {
return;
}
// Keep the larger set as the main parent.
if (size[pFirst] < size[pSecond]) {
swap(pFirst, pSecond);
}
// Attach the smaller set to the larger set.
parent[pSecond] = pFirst;
// Update the size of the merged set.
size[pFirst] += size[pSecond];
}
public:
// Counts land cells that are not connected to the boundary.
int numEnclaves(vector<vector<int>>& grid) {
int rows = grid.size();
int cols = grid[0].size();
int total = rows * cols;
// This extra node represents all boundary-connected land.
int boundary = total;
vector<int> parent(total + 1);
vector<int> size(total + 1, 1);
// Initially, every node is its own parent.
for (int node = 0; node <= total; node++) {
parent[node] = node;
}
vector<int> deltaRow = {-1, 1, 0, 0};
vector<int> deltaCol = {0, 0, -1, 1};
// Connect land cells using DSU.
for (int row = 0; row < rows; row++) {
for (int col = 0; col < cols; col++) {
// Skip water cells.
if (grid[row][col] == 0) {
continue;
}
int current = row * cols + col;
// Connect boundary land cells to the virtual boundary node.
if (row == 0 || col == 0 || row == rows - 1 || col == cols - 1) {
unite(current, boundary, parent, size);
}
// Check all four adjacent directions.
for (int dir = 0; dir < 4; dir++) {
int nextRow = row + deltaRow[dir];
int nextCol = col + deltaCol[dir];
// Check if the next cell is inside the grid.
if (nextRow >= 0 && nextRow < rows && nextCol >= 0 && nextCol < cols) {
// Connect the current land cell to adjacent land.
if (grid[nextRow][nextCol] == 1) {
unite(current, nextRow * cols + nextCol, parent, size);
}
}
}
}
}
int enclaves = 0;
// Find the parent of the virtual boundary node.
int boundaryParent = findParent(boundary, parent);
// Count land cells that are not connected to the boundary.
for (int row = 0; row < rows; row++) {
for (int col = 0; col < cols; col++) {
// Count only land cells outside the boundary component.
if (grid[row][col] == 1 && findParent(row * cols + col, parent) != boundaryParent) {
enclaves++;
}
}
}
// Return the number of enclave cells.
return enclaves;
}
};
// Driver code.
int main() {
vector<vector<int>> grid = {
{0, 0, 0, 0},

Complexity Analysis

Time Complexity: O(R×C×α(R×C)), where R and C are the grid dimensions and α is the inverse Ackermann cost of each optimized DSU operation.

Space Complexity: O(R×C), where the DSU parent and size arrays store information for all R×C cells and one virtual boundary node.

Interview follow-up Questions

A land cell is an enclave when no four-direction land path reaches the grid boundary.

Graph

Read Similar Blogs

Graph

Disjoint Set Union: Union by Rank, Size and Path Compression

Design a disjoint set, also called a union-find data structure, for N nodes numbered from 1 to N . Initially, every node belongs to a separate set. Support the following operations: DisjointSet(int...

89.1k
Graph

Print Shortest Path

Given a weighted undirected graph with n vertices numbered from 1 to n and m edges, find a shortest path from vertex 1 to vertex n . Each edge appears as [u, v, weight] and every weight is positive...

96.1k
Graph

Network Delay Time Using Dijkstra's Algorithm

A network contains n nodes labeled from 1 to n . Each directed edge [u,v,w] means a signal needs w time units to travel from node u to node v . A signal starts from node k . Return the minimum time...

81.2k
Comments0