Number of Enclaves in a Binary Matrix

Problem Statement❯

You are given an N x M binary matrix grid, where 0 represents a sea cell and 1 represents a land cell. A move consists of walking from one land cell to another adjacent (4-directionally) land cell or walking off the boundary of the grid.

The task is to find the number of land cells in the grid from which you cannot walk off the boundary in any number of moves. These land cells are called enclaves.

Examples❯

Grid	Output	Description
[[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]	3	The 3 inner land cells cannot escape to boundary.
[[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]	0	All land cells can reach the boundary.
[[1]]	0	Single land cell is on the boundary.
[[1,1,1],[1,0,1],[1,1,1]]	0	All land cells touch or connect to boundary.
[[0,0],[0,0]]	0	No land cells present in the grid.
[[0,1,0,0],[1,1,1,0],[0,1,0,0],[0,0,0,1]]	0	All land cells can reach the boundary.

Visualization Player

Solution❯

Understanding the Problem

We are given a 2D grid where 1 represents land and 0 represents water. Our task is to count the number of land cells that are completely enclosed — meaning they cannot reach the boundary of the grid by moving up, down, left, or right. These enclosed land cells are called enclaves.

To solve this, we need to eliminate all land cells that can possibly escape to the boundary. The remaining land cells are the enclaves.

Step-by-Step Solution with Example

Step 1: Identify the Boundaries

We start by identifying all the cells on the outer border of the grid — i.e., the first and last rows, and the first and last columns. Any land cell (1) that is on the boundary or connected to the boundary is not an enclave.

Step 2: Traverse from Boundary Land

We perform a DFS (or BFS) starting from each boundary land cell to mark all reachable land cells. These cells will be marked as visited. This step helps us eliminate all land that can reach the boundary directly or indirectly.

Step 3: Count Unvisited Land Cells

After marking all boundary-connected land, we loop through the grid. Any land cell that is still unvisited is an enclave. We count these and return the total.

Step 4: Example Walkthrough

Consider the grid:

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

Let's analyze this:

None of the boundary cells are land (except corners but they are water).
Start DFS from any boundary land — in this case, there is none, so we skip DFS.
Check internal cells: (1,0) is land but on edge — count it out; (1,2), (2,1), and (2,2) are land and cannot reach boundary. They are enclaves.

Final Count = 3 enclaves.

Edge Cases

Empty Grid: If the grid has no rows or columns, return 0 — no land exists.
All Zeros: A grid filled with water returns 0 — no land to begin with.
All Boundary Land: If all land is on the edge or connected to it, return 0 — no enclaves possible.
All Land Surrounded by Water: Internal land cells completely boxed in by water are counted — this is a valid enclave case.

Finally

This problem teaches us how to separate the problem space based on what we can eliminate (boundary-connected land) rather than directly searching for enclaves. Using DFS or BFS to eliminate reachable land from the edge is an efficient and intuitive approach. Beginners should understand the importance of boundary analysis and traversal techniques in grid problems.

Algorithm Steps❯

Initialize a visited matrix to keep track of visited land cells.
For each cell on the boundary of the grid, if it is land (1) and unvisited, perform DFS/BFS to mark all reachable land cells as visited.
After all boundary-connected land cells are visited, iterate through the grid and count all unvisited land cells. These are the enclaves.

Code

JavaScript

function numEnclaves(grid) {
  const rows = grid.length, cols = grid[0].length;
  const directions = [[0,1], [1,0], [0,-1], [-1,0]];
  
  function dfs(r, c) {
    if (r < 0 || c < 0 || r >= rows || c >= cols || grid[r][c] !== 1) return;
    grid[r][c] = -1;
    for (const [dr, dc] of directions) {
      dfs(r + dr, c + dc);
    }
  }

  // Run DFS on all boundary land cells
  for (let i = 0; i < rows; i++) {
    if (grid[i][0] === 1) dfs(i, 0);
    if (grid[i][cols - 1] === 1) dfs(i, cols - 1);
  }
  for (let j = 0; j < cols; j++) {
    if (grid[0][j] === 1) dfs(0, j);
    if (grid[rows - 1][j] === 1) dfs(rows - 1, j);
  }

  // Count remaining land cells
  let count = 0;
  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < cols; j++) {
      if (grid[i][j] === 1) count++;
    }
  }

  return count;
}

console.log("Enclave count:", numEnclaves([[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]])); // Output: 3

Time Complexity❯

Case	Time Complexity	Explanation
Best Case	O(m * n)	Even in the best case, we must scan the entire grid to find land on the boundary and count internal land.
Average Case	O(m * n)	Each cell is visited at most once during DFS/BFS and then again during the final count.
Worst Case	O(m * n)	Every land cell is part of a connected component, leading to complete traversal of the grid.

Space Complexity❯

O(m * n)

Explanation: We use a visited matrix or modify the original grid. DFS uses implicit recursion stack or BFS uses a queue.

⬅ Previous TopicSurrounded Regions in Matrix using Graph Traversal

Next Topic ⮕Word Ladder - Shortest Transformation using Graph

Comments

Loading comments...