Count Sub Islands

medium dfs bfs matrix

Problem

Given two m×n binary grids grid1 and grid2 (1=land), return how many islands in grid2 are sub-islands (subset of grid1's land).

Inputgrid1=[[1,1,1,0],[1,0,1,0]], grid2=[[1,0,1,0],[1,0,1,0]]

Output2

Both grid2 islands sit entirely within grid1's land.

grid1 (rows ';')

grid2

def count_sub_islands(grid1, grid2):
    m, n = len(grid2), len(grid2[0])
    seen = [[False] * n for _ in range(m)]
    def dfs(r, c):
        if r < 0 or r >= m or c < 0 or c >= n: return True
        if seen[r][c] or grid2[r][c] == 0: return True
        seen[r][c] = True
        ok = grid1[r][c] == 1
        for dr, dc in [(1,0),(-1,0),(0,1),(0,-1)]:
            ok = dfs(r+dr, c+dc) and ok
        return ok
    cnt = 0
    for r in range(m):
        for c in range(n):
            if grid2[r][c] == 1 and not seen[r][c]:
                if dfs(r, c): cnt += 1
    return cnt

function countSubIslands(grid1, grid2) {
  const m = grid2.length, n = grid2[0].length;
  const seen = Array.from({length: m}, () => new Array(n).fill(false));
  function dfs(r, c) {
    if (r < 0 || r >= m || c < 0 || c >= n) return true;
    if (seen[r][c] || grid2[r][c] === 0) return true;
    seen[r][c] = true;
    let ok = grid1[r][c] === 1;
    for (const [dr, dc] of [[1,0],[-1,0],[0,1],[0,-1]]) ok = dfs(r+dr, c+dc) && ok;
    return ok;
  }
  let cnt = 0;
  for (let r = 0; r < m; r++) for (let c = 0; c < n; c++)
    if (grid2[r][c] === 1 && !seen[r][c]) if (dfs(r, c)) cnt++;
  return cnt;
}

class Solution {
    int[][] g1, g2; boolean[][] seen; int m, n;
    boolean dfs(int r, int c) {
        if (r < 0 || r >= m || c < 0 || c >= n) return true;
        if (seen[r][c] || g2[r][c] == 0) return true;
        seen[r][c] = true;
        boolean ok = g1[r][c] == 1;
        int[][] D = {{1,0},{-1,0},{0,1},{0,-1}};
        for (int[] d : D) ok = dfs(r+d[0], c+d[1]) && ok;
        return ok;
    }
    public int countSubIslands(int[][] grid1, int[][] grid2) {
        g1 = grid1; g2 = grid2; m = g2.length; n = g2[0].length; seen = new boolean[m][n];
        int cnt = 0;
        for (int r = 0; r < m; r++) for (int c = 0; c < n; c++)
            if (g2[r][c] == 1 && !seen[r][c]) if (dfs(r, c)) cnt++;
        return cnt;
    }
}

class Solution {
    vector<vector<int>>* g1; vector<vector<int>>* g2; vector<vector<int>> seen; int m, n;
    bool dfs(int r, int c) {
        if (r < 0 || r >= m || c < 0 || c >= n) return true;
        if (seen[r][c] || (*g2)[r][c] == 0) return true;
        seen[r][c] = 1;
        bool ok = (*g1)[r][c] == 1;
        int D[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
        for (auto& d : D) ok = dfs(r+d[0], c+d[1]) && ok;
        return ok;
    }
public:
    int countSubIslands(vector<vector<int>>& grid1, vector<vector<int>>& grid2) {
        g1 = &grid1; g2 = &grid2; m = grid2.size(); n = grid2[0].size();
        seen.assign(m, vector<int>(n, 0));
        int cnt = 0;
        for (int r = 0; r < m; r++) for (int c = 0; c < n; c++)
            if (grid2[r][c] == 1 && !seen[r][c]) if (dfs(r, c)) cnt++;
        return cnt;
    }
};

Explanation

We need to count islands in grid2 that fit completely inside the land of grid1. The clean way is to explore each island once with a flood fill (DFS), and while exploring it, check that every single land cell it touches is also land in grid1.

The DFS walks all four neighbors of a cell. It marks cells as seen so it never revisits them. For the whole island it computes a single boolean ok: the island stays a sub-island only if every cell satisfies grid1[r][c] == 1. The line ok = dfs(...) and ok combines results so one bad cell anywhere flips the whole island to false.

A subtle but important detail: the code keeps recursing through the entire island even after it finds a bad cell. That is on purpose — it must mark every cell seen so the outer loop does not start a second flood fill on the same island.

Example: grid2=[[1,0,1,0],[1,0,1,0]]. The left column is one island and the right column is another. We DFS each one; for both, every land cell lines up with land in grid1, so each contributes ok=true and we add 1.

The outer double loop only launches a DFS at an unvisited land cell, so each island is processed exactly once. The final count is the number of islands that came back true.

Time: O(m·n) Space: O(m·n)