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 land cells in the center cannot reach the boundary.
[[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]	0	All land cells are connected to the boundary and can escape.
[[1]]	0	Single land cell is on the boundary, hence not an enclave.
[[1,1,1],[1,0,1],[1,1,1]]	1	Only the center cell is an enclave.
[[0,0],[0,0]]	0	No land cells present.

Solution❯

Understanding the Problem

In this problem, we are given a grid with 0s and 1s, where 1 represents land and 0 represents water. An enclave is a group of land cells that cannot reach the boundary of the grid by moving in 4 directions (up, down, left, right).

Boundary Land Cells

The first thing to observe is that any land cell connected to the boundary (first or last row/column) cannot be part of an enclave. So we start by marking all land cells that are reachable from the boundary using either BFS or DFS.

Marking Reachable Land

We traverse the boundary of the grid. If we find a 1, we launch a DFS or BFS to mark all connected land cells as visited. These cells are not enclaves since they can reach the boundary directly or indirectly.

Counting Enclaves

After marking all boundary-connected land, we iterate through the internal cells of the grid. Any land cell that is still unvisited is an enclave because it cannot reach the boundary. We count and return these cells.

Example

For a grid like:

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

The land cells at (1,2), (2,1), and (2,2) are not connected to the boundary, so they are considered enclaves. The result will be 3.

Edge Cases

Empty Grid: Return 0 because there are no land cells.
All Boundary Land: Return 0 because all land is connected to boundary.
Full Land but Enclosed: Internal land surrounded by water will be counted correctly.

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