Number of Enclaves — Boundary DFS Count

Problem

Return the number of land cells that cannot walk off the boundary of the grid.

Approach — Boundary DFS then Count

DFS from all border land cells, mark them visited. Count remaining unvisited land cells.

Time: O(mn) | Space: O(mn)

Solutions

Python

class Solution:
    def numEnclaves(self, grid: list[list[int]]) -> int:
        R,C=len(grid),len(grid[0])
        def dfs(r,c):
            if not(0<=r<R and 0<=c<C) or grid[r][c]!=1: return
            grid[r][c]=0
            for dr,dc in[(1,0),(-1,0),(0,1),(0,-1)]: dfs(r+dr,c+dc)
        for r in range(R): dfs(r,0); dfs(r,C-1)
        for c in range(C): dfs(0,c); dfs(R-1,c)
        return sum(grid[r][c] for r in range(R) for c in range(C))

C++

class Solution {
    void dfs(vector<vector<int>>& g,int r,int c){
        if(r<0||r>=g.size()||c<0||c>=g[0].size()||g[r][c]!=1) return;
        g[r][c]=0;
        dfs(g,r+1,c);dfs(g,r-1,c);dfs(g,r,c+1);dfs(g,r,c-1);
    }
public:
    int numEnclaves(vector<vector<int>>& g){
        int R=g.size(),C=g[0].size();
        for(int r=0;r<R;r++){dfs(g,r,0);dfs(g,r,C-1);}
        for(int c=0;c<C;c++){dfs(g,0,c);dfs(g,R-1,c);}
        int cnt=0;
        for(auto& row:g) for(int v:row) cnt+=v;
        return cnt;
    }
};

Complexity

Time: O(mn) | Space: O(mn)