Problem Description

You are given two binary matrices, grid1 and grid2, with the same dimensions. Each cell contains either a 0 (water) or a 1 (land). An island is a group of 1's connected 4-directionally (up, down, left, right).

An island in grid2 is considered a sub-island if every cell of the island in grid2 is also a land cell in grid1 at the same position.

Your task is to count the number of sub-islands in grid2.

• You may not reuse the same cell in multiple islands.
• Both grids are the same size (m x n).
• There is only one valid solution for each input.

Thought Process

At first glance, the problem seems similar to the classic "number of islands" problem. However, the twist is that we must check if an island in grid2 is completely contained within an island in grid1.

A brute-force approach might be to, for every island in grid2, check every cell and see if it is also land in grid1. But we need to avoid counting islands that overlap with water in grid1.

To optimize, we can use depth-first search (DFS) or breadth-first search (BFS) to traverse each island in grid2, marking visited cells. During traversal, we can check if any cell is not land in grid1. If so, the whole island is not a sub-island. Otherwise, we count it.

Solution Approach

• Step 1: Iterate through every cell in grid2.
• Step 2: When a land cell (1) is found that hasn't been visited, start a DFS (or BFS) from that cell to traverse the entire island.
• Step 3: During traversal, mark each visited cell in grid2 (e.g., set it to 0 or use a visited array).
• Step 4: For each cell in the island, check if the corresponding cell in grid1 is also land (1). If any cell is water (0) in grid1, the current island is not a sub-island.
• Step 5: If the entire island in grid2 is over land in grid1, increment the sub-island count.

We use DFS here because it is straightforward to implement and efficiently traverses connected components in a grid. Marking cells as visited ensures we don't double-count or revisit cells.

Example Walkthrough

Suppose:

    grid1 = [
      [1,1,1,0,0],
      [0,1,1,1,1],
      [0,0,0,0,0],
      [1,0,1,1,1],
      [0,1,0,1,0]
    ]
    grid2 = [
      [1,1,1,0,0],
      [0,0,1,1,1],
      [0,1,0,0,0],
      [1,0,1,1,1],
      [0,0,0,1,0]
    ]
  

• Start at (0,0): It's a land cell in grid2. Start DFS. All corresponding cells in grid1 are land, so this is a sub-island.
• Next, at (1,3): New island in grid2. Traverse. All corresponding cells are land in grid1, so it's a sub-island.
• At (2,1): It's land in grid2 but water in grid1. Not a sub-island.
• At (3,0): Land in both, but only a single cell. It's a sub-island.
• At (3,2): Start DFS. All corresponding cells are land in grid1, so it's a sub-island.

The total sub-islands counted would be 3.

Code Implementation

class Solution:
    def countSubIslands(self, grid1, grid2):
        m, n = len(grid1), len(grid1[0])
        def dfs(x, y):
            if x < 0 or x >= m or y < 0 or y >= n or grid2[x][y] == 0:
                return True
            grid2[x][y] = 0
            res = True
            if grid1[x][y] == 0:
                res = False
            for dx, dy in [(-1,0),(1,0),(0,-1),(0,1)]:
                if not dfs(x+dx, y+dy):
                    res = False
            return res
        count = 0
        for i in range(m):
            for j in range(n):
                if grid2[i][j] == 1:
                    if dfs(i, j):
                        count += 1
        return count
      

class Solution {
public:
    int m, n;
    bool dfs(vector<vector<int>>& grid1, vector<vector<int>>& grid2, int x, int y) {
        if (x < 0 || x >= m || y < 0 || y >= n || grid2[x][y] == 0)
            return true;
        grid2[x][y] = 0;
        bool res = true;
        if (grid1[x][y] == 0)
            res = false;
        vector<pair<int,int>> dirs = {{-1,0},{1,0},{0,-1},{0,1}};
        for (auto d : dirs) {
            if (!dfs(grid1, grid2, x + d.first, y + d.second))
                res = false;
        }
        return res;
    }
    int countSubIslands(vector<vector<int>>& grid1, vector<vector<int>>& grid2) {
        m = grid1.size();
        n = grid1[0].size();
        int count = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid2[i][j] == 1) {
                    if (dfs(grid1, grid2, i, j))
                        ++count;
                }
            }
        }
        return count;
    }
};
      

class Solution {
    int m, n;
    public int countSubIslands(int[][] grid1, int[][] grid2) {
        m = grid1.length;
        n = grid1[0].length;
        int count = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid2[i][j] == 1) {
                    if (dfs(grid1, grid2, i, j))
                        count++;
                }
            }
        }
        return count;
    }
    private boolean dfs(int[][] grid1, int[][] grid2, int x, int y) {
        if (x < 0 || x >= m || y < 0 || y >= n || grid2[x][y] == 0)
            return true;
        grid2[x][y] = 0;
        boolean res = true;
        if (grid1[x][y] == 0)
            res = false;
        int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
        for (int[] d : dirs) {
            if (!dfs(grid1, grid2, x + d[0], y + d[1]))
                res = false;
        }
        return res;
    }
}
      

var countSubIslands = function(grid1, grid2) {
    const m = grid1.length, n = grid1[0].length;
    function dfs(x, y) {
        if (x < 0 || x >= m || y < 0 || y >= n || grid2[x][y] === 0)
            return true;
        grid2[x][y] = 0;
        let res = true;
        if (grid1[x][y] === 0)
            res = false;
        const dirs = [[-1,0],[1,0],[0,-1],[0,1]];
        for (const [dx, dy] of dirs) {
            if (!dfs(x + dx, y + dy))
                res = false;
        }
        return res;
    }
    let count = 0;
    for (let i = 0; i < m; ++i) {
        for (let j = 0; j < n; ++j) {
            if (grid2[i][j] === 1) {
                if (dfs(i, j))
                    count++;
            }
        }
    }
    return count;
};
      

Time and Space Complexity

• Brute-force: For each island in grid2, we could check every cell in grid1, which would be O((m*n)^2) in the worst case.
• Optimized (DFS/BFS): Each cell is visited at most once, so the time complexity is O(m*n). Each DFS call uses stack space up to O(m*n) in the worst case (for a very large island), so space complexity is also O(m*n).
• Why: We traverse each cell once, and marking visited ensures no repeats. The call stack or queue for BFS/DFS is proportional to the island size.

Summary

The key insight is to use DFS or BFS to traverse islands in grid2 and check if every part of the island is also land in grid1. By marking visited cells, we avoid double-counting, and by checking corresponding cells in grid1, we ensure only valid sub-islands are counted. This approach is both efficient and elegant, leveraging classic graph traversal techniques for grid-based problems.