Number of Enclaves | Multi-source BFS

1. Problem Statement & Overview

The Number of Enclaves problem requires us to find the total count of land cells (represented by 1s) in an $N \times M$ binary matrix (grid) from which it is impossible to walk off the boundary of the grid in any number of moves.

Cell Types: 0 represents a sea cell, and 1 represents a land cell.
Allowed Movements: We can move in 4 cardinal directions (up, down, left, right) from one land cell to an adjacent land cell.
Boundary Condition: A cell is considered "escapable" if we can reach the outer edge (boundary row or column) of the matrix through valid land-to-land steps.

2. Core Mental Model & Intuition

The fundamental key to solving this problem efficiently is inverting our perspective:

Real-Life Analogy & Mental Hook: Think of the grid as a group of islands. If an island touches the outer ocean boundary anywhere, any piece of land connected to that boundary can eventually lead someone out of the grid. Conversely, any internal land cells completely trapped inland—surrounded by sea or other non-boundary-connected land—can never reach the edge.

Instead of searching from every internal cell outward to see if it hits a boundary (which is inefficient and redundant), we start outward from the boundary itself.

3. The Boundary-First Strategy (Multi-source BFS)

Any 1 located on the outer boundary of the grid (row = 0, row = N-1, col = 0, or col = M-1) is immediately capable of reaching the boundary (since it is on the boundary). Furthermore, any land cell connected directly or indirectly to these boundary ones is also escapable.

Step-by-Step Evolution:

Identify Boundary Lands: Scan all elements on the top row, bottom row, left column, and right column. If a cell contains 1, it is a boundary land.
Enqueue & Mark Visited: Push all boundary land coordinates into a Breadth-First Search (BFS) Queue and mark them in a visited matrix.
Multi-source Traversal: Perform a BFS outward from all boundary lands simultaneously, visiting all reachable land neighbors.
Count Unvisited Lands: After the queue is exhausted, any land cell (grid[i][j] == 1) that remains unvisited means it has no connection to the boundary. We count these remaining cells as our final answer (enclaves).

4. Visualizing the BFS Flow Walkthrough

Structure & Concept Flow

Grid State (Boundary Lands Identified)

Push all boundary '1's into Queue & mark visited = 1

Pop element from Queue (e.g., row = 0, col = 3)

Check 4 directions (Up, Right, Down, Left)

If neighbor is '1' and unvisited:

+-- Push neighbor into Queue

+-- Mark neighbor as visited = 1

Repeat until Queue is empty

Scan entire grid: count all cells where (grid[i][j] == 1 AND visited[i][j] == 0)

5. Directional Deltas for Grid Traversal

To check all 4 adjacent neighbors (Top, Right, Bottom, Left) from any given cell (row, col), we use directional array deltas:

Top: row - 1, col (delta_row = -1, delta_col = 0)
Right: row, col + 1 (delta_row = 0, delta_col = 1)
Bottom: row + 1, col (delta_row = 1, delta_col = 0)
Left: row, col - 1 (delta_row = 0, delta_col = -1)

6. Complete Code Implementation

C++ Implementation

C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int numEnclaves(vector<vector<int>>& grid) {
        int n = grid.size();
        int m = grid[0].size();
        
        queue<pair<int, int>> q;
        vector<vector<int>> visited(n, vector<int>(m, 0));
        
        // Step 1: Push all boundary '1's into the queue
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                // Check if it's on the boundary and is a land cell
                if (i == 0 || j == 0 || i == n - 1 || j == m - 1) {
                    if (grid[i][j] == 1) {
                        q.push({i, j});
                        visited[i][j] = 1;
                    }
                }
            }
        }
        
        // Delta arrays for 4-directional movement (Up, Right, Down, Left)
        int delRow[] = {-1, 0, 1, 0};
        int delCol[] = {0, 1, 0, -1};
        
        // Step 2: Multi-source BFS traversal
        while (!q.empty()) {
            int row = q.front().first;
            int col = q.front().second;
            q.pop();
            
            for (int i = 0; i < 4; i++) {
                int nRow = row + delRow[i];
                int nCol = col + delCol[i];
                
                // Check bounds, whether it's unvisited, and if it's a land cell
                if (nRow >= 0 && nRow < n && nCol >= 0 && nCol < m 
                    && visited[nRow][nCol] == 0 && grid[nRow][nCol] == 1) {
                    q.push({nRow, nCol});
                    visited[nRow][nCol] = 1;
                }
            }
        }
        
        // Step 3: Count remaining unvisited land cells (enclaves)
        int enclaveCount = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 1 && visited[i][j] == 0) {
                    enclaveCount++;
                }
            }
        }
        
        return enclaveCount;
    }
};

Java Implementation

JAVA

import java.util.Queue;
import java.util.LinkedList;

class Solution {
    class Pair {
        int row;
        int col;
        public Pair(int row, int col) {
            this.row = row;
            this.col = col;
        }
    }

    public int numEnclaves(int[][] grid) {
        int n = grid.length;
        int m = grid[0].length;
        
        Queue<Pair> q = new LinkedList<>();
        int[][] visited = new int[n][m];
        
        // Step 1: Push all boundary '1's into the queue
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (i == 0 || j == 0 || i == n - 1 || j == m - 1) {
                    if (grid[i][j] == 1) {
                        q.add(new Pair(i, j));
                        visited[i][j] = 1;
                    }
                }
            }
        }
        
        // Delta arrays for 4-directional movement
        int[] delRow = {-1, 0, 1, 0};
        int[] delCol = {0, 1, 0, -1};
        
        // Step 2: Multi-source BFS traversal
        while (!q.isEmpty()) {
            int row = q.peek().row;
            int col = q.peek().col;
            q.remove();
            
            for (int i = 0; i < 4; i++) {
                int nRow = row + delRow[i];
                int nCol = col + delCol[i];
                
                if (nRow >= 0 && nRow < n && nCol >= 0 && nCol < m 
                    && visited[nRow][nCol] == 0 && grid[nRow][nCol] == 1) {
                    q.add(new Pair(nRow, nCol));
                    visited[nRow][nCol] = 1;
                }
            }
        }
        
        // Step 3: Count remaining unvisited land cells
        int enclaveCount = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 1 && visited[nRow_or_visited_check... i.e. visited[i][j] == 0]) {
                    enclaveCount++;
                }
            }
        }
        
        return enclaveCount;
    }
}

(Note: In the Java code loop above, the final scan checks grid[i][j] == 1 && visited[i][j] == 0)

7. Complexity Analysis

Complexity Type	Analysis	Explanation
Time Complexity	$O(N \times M)$	Traversing the boundary takes $O(N + M)$ time. The BFS queue visits each cell and its neighbors at most once, taking $4 \times O(N \times M)$ operations in the worst-case scenario where all cells are land. Final grid scan takes $O(N \times M)$ .
Space Complexity	$O(N \times M)$	Required for maintaining the `visited` matrix of dimensions $N \times M$ and the BFS `queue` which can hold up to $O(N \times M)$ elements in the worst case.

8. Summary and Key Takeaways

Invert the Goal: When asked to find cells that cannot reach a boundary, start by exploring outward from the boundaries themselves.
Multi-Source BFS Pattern: Initializing the BFS queue with multiple starting nodes simultaneously (all boundary lands) allows us to propagate connection states efficiently in a single pass.
Visited Tracking: Always utilize a parallel visited matrix or modify values in-place (if permitted) to prevent infinite loops during graph cycles.
Boundary Identification Condition: A cell (i, j) is on the boundary if i == 0, i == n - 1, j == 0, or j == m - 1.
Directional Arrays (delRow, delCol): Keep code clean and modular when exploring 4-way or 8-way directional grids by predefining delta arrays.