Number of Enclaves in a Binary Matrix - Visualization

Graphs

Contents

VisualizationProblemExamplesSolutionAlgorithmCodeTimeSpace

Visualization Player

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.

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❯

  1. Initialize a visited matrix to keep track of visited land cells.
  2. 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.
  3. After all boundary-connected land cells are visited, iterate through the grid and count all unvisited land cells. These are the enclaves.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>

#define ROWS 4
#define COLS 4

int directions[4][2] = {{0,1}, {1,0}, {0,-1}, {-1,0}};

void dfs(int grid[ROWS][COLS], int r, int c) {
    if (r < 0 || c < 0 || r >= ROWS || c >= COLS || grid[r][c] != 1) return;
    grid[r][c] = -1;
    for (int i = 0; i < 4; i++) {
        dfs(grid, r + directions[i][0], c + directions[i][1]);
    }
}

int numEnclaves(int grid[ROWS][COLS]) {
    for (int i = 0; i < ROWS; i++) {
        if (grid[i][0] == 1) dfs(grid, i, 0);
        if (grid[i][COLS-1] == 1) dfs(grid, i, COLS-1);
    }
    for (int j = 0; j < COLS; j++) {
        if (grid[0][j] == 1) dfs(grid, 0, j);
        if (grid[ROWS-1][j] == 1) dfs(grid, ROWS-1, j);
    }

    int count = 0;
    for (int i = 0; i < ROWS; i++) {
        for (int j = 0; j < COLS; j++) {
            if (grid[i][j] == 1) count++;
        }
    }
    return count;
}

int main() {
    int grid[4][4] = {
        {0,0,0,0},
        {1,0,1,0},
        {0,1,1,0},
        {0,0,0,0}
    };
    printf("Enclave count: %d\n", numEnclaves(grid));
    return 0;
}

Time Complexity❯

CaseTime ComplexityExplanation
Best CaseO(m * n)Even in the best case, we must scan the entire grid to find land on the boundary and count internal land.
Average CaseO(m * n)Each cell is visited at most once during DFS/BFS and then again during the final count.
Worst CaseO(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.


Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...