Problem Description

The "Number of Enclaves" problem asks you to count the number of land cells in a 2D grid that cannot reach the boundary of the grid by moving up, down, left, or right. The grid is represented as a 2D array grid where grid[i][j] == 1 means the cell is land and grid[i][j] == 0 means the cell is water.

A land cell is considered an enclave if it cannot walk off the boundary of the grid in any number of moves. You can only move to adjacent land cells (no diagonals). The task is to return the total number of such enclave land cells.

• All moves are 4-directional (up, down, left, right).
• You cannot reuse or revisit the same cell in a single traversal.
• The grid is rectangular, and its size can be up to 500 x 500.

Thought Process

At first glance, one might think about counting all the land cells and then trying to check, for each, if a path exists to the boundary. However, checking for each cell individually would be very inefficient.

Instead, notice that the only land cells that cannot reach the boundary are those that are fully surrounded by water or other land cells not connected to the edge. So, if we can remove all land cells that are connected to the boundary, the remaining ones are enclaves.

This leads to a more efficient approach: "flood fill" (BFS or DFS) from the boundary land cells, marking all land they can reach. Then, count the land cells that remain unvisited.

Solution Approach

The algorithm can be broken down into the following steps:

1. Identify all boundary land cells: Iterate over the first and last rows and columns. For every cell that is land (1), start a flood fill (DFS or BFS).
2. Flood fill from boundaries: For each boundary land cell, perform a DFS or BFS to mark all connected land cells as visited (for example, by setting them to 0 or using a visited array).
3. Count remaining land cells: After the flood fill, iterate through the grid and count all cells still marked as land (1). These are enclaves.

We use flood fill because it efficiently marks all reachable land from the boundary in O(N) time, and we avoid extra space by modifying the grid in place.

Example Walkthrough

Consider this grid:

    grid = [
      [0,0,0,0],
      [1,0,1,0],
      [0,1,1,0],
      [0,0,0,0]
    ]
  

1. Boundary scan: The boundary cells are all 0s (water), so no flood fill starts.
2. No boundary-connected land: All land is inside the grid and not on the edge.
3. Count land cells: There are 4 land cells at positions (1,0), (1,2), (2,1), (2,2). All are enclaves since they can't reach the boundary.

The answer is 4.

Time and Space Complexity

• Brute-force: If we tried to check from every land cell whether it can reach the boundary, time complexity could be O(N³) (for each cell, potentially traverse the grid).
• Optimized (Flood Fill): We visit each cell at most once (during boundary flood fill and final count), so time complexity is O(m * n), where m and n are grid dimensions.
• Space Complexity: O(1) extra space if we modify the grid in place, or O(m * n) if we use a visited array or queue for BFS.

Summary

The key insight is to realize that only land cells not connected to the boundary are enclaves. By removing all land reachable from the boundary via a flood fill, we efficiently isolate and count the enclaves. This approach is both simple and optimal for the problem constraints.

Code Implementation

class Solution:
    def numEnclaves(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        
        def dfs(x, y):
            if x < 0 or x >= m or y < 0 or y >= n or grid[x][y] == 0:
                return
            grid[x][y] = 0
            for dx, dy in [(-1,0),(1,0),(0,-1),(0,1)]:
                dfs(x+dx, y+dy)
        
        for i in range(m):
            for j in [0, n-1]:
                if grid[i][j] == 1:
                    dfs(i, j)
        for j in range(n):
            for i in [0, m-1]:
                if grid[i][j] == 1:
                    dfs(i, j)
        
        return sum(grid[i][j] == 1 for i in range(m) for j in range(n))
      

class Solution {
public:
    void dfs(vector<vector<int>>& grid, int x, int y, int m, int n) {
        if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y] == 0) return;
        grid[x][y] = 0;
        int dirs[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
        for (auto& d : dirs) {
            dfs(grid, x + d[0], y + d[1], m, n);
        }
    }
    int numEnclaves(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        for (int i = 0; i < m; ++i) {
            if (grid[i][0] == 1) dfs(grid, i, 0, m, n);
            if (grid[i][n-1] == 1) dfs(grid, i, n-1, m, n);
        }
        for (int j = 0; j < n; ++j) {
            if (grid[0][j] == 1) dfs(grid, 0, j, m, n);
            if (grid[m-1][j] == 1) dfs(grid, m-1, j, m, n);
        }
        int count = 0;
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j)
                if (grid[i][j] == 1) count++;
        return count;
    }
};
      

class Solution {
    int m, n;
    public int numEnclaves(int[][] grid) {
        m = grid.length;
        n = grid[0].length;
        for (int i = 0; i < m; ++i) {
            if (grid[i][0] == 1) dfs(grid, i, 0);
            if (grid[i][n-1] == 1) dfs(grid, i, n-1);
        }
        for (int j = 0; j < n; ++j) {
            if (grid[0][j] == 1) dfs(grid, 0, j);
            if (grid[m-1][j] == 1) dfs(grid, m-1, j);
        }
        int count = 0;
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j)
                if (grid[i][j] == 1) count++;
        return count;
    }
    void dfs(int[][] grid, int x, int y) {
        if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y] == 0) return;
        grid[x][y] = 0;
        int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
        for (int[] d : dirs)
            dfs(grid, x + d[0], y + d[1]);
    }
}
      

var numEnclaves = function(grid) {
    const m = grid.length, n = grid[0].length;
    function dfs(x, y) {
        if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y] === 0) return;
        grid[x][y] = 0;
        [[-1,0],[1,0],[0,-1],[0,1]].forEach(([dx, dy]) => dfs(x+dx, y+dy));
    }
    for (let i = 0; i < m; ++i) {
        if (grid[i][0] === 1) dfs(i, 0);
        if (grid[i][n-1] === 1) dfs(i, n-1);
    }
    for (let j = 0; j < n; ++j) {
        if (grid[0][j] === 1) dfs(0, j);
        if (grid[m-1][j] === 1) dfs(m-1, j);
    }
    let count = 0;
    for (let i = 0; i < m; ++i)
        for (let j = 0; j < n; ++j)
            if (grid[i][j] === 1) count++;
    return count;
};