Count Sub Islands — DFS Subset Check

Problem

An island in grid2 is a sub-island if every cell of that island also appears as land in grid1. Return the count.

Approach — DFS with AND logic

DFS floods each island in grid2. The island is valid if ALL cells it covers are also 1 in grid1. Crucially, continue DFS even if a cell fails (to mark the whole island visited), but track the boolean.

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

Solutions

Python

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

C++

class Solution {
    bool dfs(vector<vector<int>>& g1, vector<vector<int>>& g2, int r, int c){
        if(r<0||r>=g2.size()||c<0||c>=g2[0].size()||g2[r][c]!=1) return true;
        g2[r][c]=0;
        bool ok = g1[r][c]==1;
        if(!dfs(g1,g2,r+1,c)) ok=false;
        if(!dfs(g1,g2,r-1,c)) ok=false;
        if(!dfs(g1,g2,r,c+1)) ok=false;
        if(!dfs(g1,g2,r,c-1)) ok=false;
        return ok;
    }
public:
    int countSubIslands(vector<vector<int>>& g1, vector<vector<int>>& g2){
        int cnt=0;
        for(int r=0;r<g2.size();r++) for(int c=0;c<g2[0].size();c++)
            if(g2[r][c]==1 && dfs(g1,g2,r,c)) cnt++;
        return cnt;
    }
};

Complexity

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

Key Takeaway

When checking an island property, always complete the DFS (don't short-circuit) to mark all cells visited; just track the boolean separately.