ProgramGuru

Number of Enclaves in Grid

Problem and examples

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.

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.

Explore Number of Enclaves in a Binary Matrix

Load an example or enter your own input. Use the player controls to follow each change.

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.

  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.

Implementation and efficiency

C implementation

#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;
}

C++ implementation

#include <iostream>
#include <vector>
using namespace std;

vector<pair<int, int>> directions = {{0,1}, {1,0}, {0,-1}, {-1,0}};

void dfs(vector<vector<int>>& grid, int r, int c) {
    int rows = grid.size(), cols = grid[0].size();
    if (r < 0 || c < 0 || r >= rows || c >= cols || grid[r][c] != 1) return;
    grid[r][c] = -1;
    for (auto [dr, dc] : directions) {
        dfs(grid, r + dr, c + dc);
    }
}

int numEnclaves(vector<vector<int>>& grid) {
    int rows = grid.size(), cols = grid[0].size();
    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 (auto& row : grid) {
        for (int cell : row) {
            if (cell == 1) count++;
        }
    }
    return count;
}

int main() {
    vector<vector<int>> grid = {
        {0,0,0,0},
        {1,0,1,0},
        {0,1,1,0},
        {0,0,0,0}
    };
    cout << "Enclave count: " << numEnclaves(grid) << endl;
    return 0;
}

Python implementation

def num_enclaves(grid):
    rows, cols = len(grid), len(grid[0])
    directions = [(0,1), (1,0), (0,-1), (-1,0)]

    def dfs(r, c):
        if r < 0 or c < 0 or r >= rows or c >= cols or grid[r][c] != 1:
            return
        grid[r][c] = -1
        for dr, dc in directions:
            dfs(r + dr, c + dc)

    for i in range(rows):
        if grid[i][0] == 1:
            dfs(i, 0)
        if grid[i][cols-1] == 1:
            dfs(i, cols-1)
    for j in range(cols):
        if grid[0][j] == 1:
            dfs(0, j)
        if grid[rows-1][j] == 1:
            dfs(rows-1, j)

    return sum(cell == 1 for row in grid for cell in row)

print("Enclave count:", num_enclaves([[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]))

Java implementation

public class EnclaveCounter {
    static int[][] directions = {{0,1}, {1,0}, {0,-1}, {-1,0}};

    public static void dfs(int[][] grid, int r, int c) {
        int rows = grid.length, cols = grid[0].length;
        if (r < 0 || c < 0 || r >= rows || c >= cols || grid[r][c] != 1) return;
        grid[r][c] = -1;
        for (int[] d : directions) {
            dfs(grid, r + d[0], c + d[1]);
        }
    }

    public static int numEnclaves(int[][] grid) {
        int rows = grid.length, cols = grid[0].length;
        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[] row : grid) {
            for (int cell : row) {
                if (cell == 1) count++;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        int[][] grid = {
            {0,0,0,0},
            {1,0,1,0},
            {0,1,1,0},
            {0,0,0,0}
        };
        System.out.println("Enclave count: " + numEnclaves(grid));
    }
}

JavaScript implementation

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);
    }
  }

  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);
  }

  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]]));

Go implementation

package main
import "fmt"

var directions = [][]int{{0,1}, {1,0}, {0,-1}, {-1,0}}

func dfs(grid [][]int, r, c int) {
    rows, cols := len(grid), len(grid[0])
    if r < 0 || c < 0 || r >= rows || c >= cols || grid[r][c] != 1 {
        return
    }
    grid[r][c] = -1
    for _, dir := range directions {
        dfs(grid, r+dir[0], c+dir[1])
    }
}

func numEnclaves(grid [][]int) int {
    rows, cols := len(grid), len(grid[0])
    for 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 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)
        }
    }

    count := 0
    for _, row := range grid {
        for _, cell := range row {
            if cell == 1 {
                count++
            }
        }
    }
    return count
}

func main() {
    grid := [][]int{
        {0,0,0,0},
        {1,0,1,0},
        {0,1,1,0},
        {0,0,0,0},
    }
    fmt.Println("Enclave count:", numEnclaves(grid))
}

Rust implementation

fn dfs(grid: &mut Vec<Vec<i32>>, r: isize, c: isize) {
    let rows = grid.len() as isize;
    let cols = grid[0].len() as isize;
    if r < 0 || c < 0 || r >= rows || c >= cols || grid[r as usize][c as usize] != 1 {
        return;
    }
    grid[r as usize][c as usize] = -1;
    let directions = [(0,1), (1,0), (0,-1), (-1,0)];
    for (dr, dc) in directions {
        dfs(grid, r + dr, c + dc);
    }
}

fn num_enclaves(mut grid: Vec<Vec<i32>>) -> i32 {
    let rows = grid.len();
    let cols = grid[0].len();
    for i in 0..rows {
        if grid[i][0] == 1 { dfs(&mut grid, i as isize, 0); }
        if grid[i][cols-1] == 1 { dfs(&mut grid, i as isize, (cols-1) as isize); }
    }
    for j in 0..cols {
        if grid[0][j] == 1 { dfs(&mut grid, 0, j as isize); }
        if grid[rows-1][j] == 1 { dfs(&mut grid, (rows-1) as isize, j as isize); }
    }
    grid.iter().flatten().filter(|&x| *x == 1).count() as i32
}

fn main() {
    let grid = vec![
        vec![0,0,0,0],
        vec![1,0,1,0],
        vec![0,1,1,0],
        vec![0,0,0,0],
    ];
    println!("Enclave count: {}", num_enclaves(grid));
}

Kotlin implementation

fun dfs(grid: Array<IntArray>, r: Int, c: Int) {
    val rows = grid.size
    val cols = grid[0].size
    if (r < 0 || c < 0 || r >= rows || c >= cols || grid[r][c] != 1) return
    grid[r][c] = -1
    val directions = arrayOf(intArrayOf(0,1), intArrayOf(1,0), intArrayOf(0,-1), intArrayOf(-1,0))
    for (d in directions) {
        dfs(grid, r + d[0], c + d[1])
    }
}

fun numEnclaves(grid: Array<IntArray>): Int {
    val rows = grid.size
    val cols = grid[0].size
    for (i in 0 until rows) {
        if (grid[i][0] == 1) dfs(grid, i, 0)
        if (grid[i][cols - 1] == 1) dfs(grid, i, cols - 1)
    }
    for (j in 0 until cols) {
        if (grid[0][j] == 1) dfs(grid, 0, j)
        if (grid[rows - 1][j] == 1) dfs(grid, rows - 1, j)
    }
    return grid.sumBy { row -> row.count { it == 1 } }
}

fun main() {
    val grid = arrayOf(
        intArrayOf(0,0,0,0),
        intArrayOf(1,0,1,0),
        intArrayOf(0,1,1,0),
        intArrayOf(0,0,0,0)
    )
    println("Enclave count: ${numEnclaves(grid)}")
}

Swift implementation

func dfs(_ grid: inout [[Int]], _ r: Int, _ c: Int) {
    let rows = grid.count
    let cols = grid[0].count
    if r < 0 || c < 0 || r >= rows || c >= cols || grid[r][c] != 1 {
        return
    }
    grid[r][c] = -1
    let directions = [(0,1), (1,0), (0,-1), (-1,0)]
    for (dr, dc) in directions {
        dfs(&grid, r + dr, c + dc)
    }
}

func numEnclaves(_ grid: inout [[Int]]) -> Int {
    let rows = grid.count
    let cols = grid[0].count
    for i in 0..<rows {
        if grid[i][0] == 1 { dfs(&grid, i, 0) }
        if grid[i][cols - 1] == 1 { dfs(&grid, i, cols - 1) }
    }
    for j in 0..<cols {
        if grid[0][j] == 1 { dfs(&grid, 0, j) }
        if grid[rows - 1][j] == 1 { dfs(&grid, rows - 1, j) }
    }
    return grid.flatMap { $0 }.filter { $0 == 1 }.count
}

var grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]
print("Enclave count: \(numEnclaves(&grid))")

TypeScript implementation

function numEnclaves(grid: number[][]): number {
  const rows = grid.length, cols = grid[0].length;
  const directions: [number, number][] = [[0,1], [1,0], [0,-1], [-1,0]];

  function dfs(r: number, c: number): void {
    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);
    }
  }

  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);
  }

  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]]));

Time complexity

CaseTimeExplanation
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)

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