Count Sub Islands

LeetCode 2035 | Difficulty: Medium

Medium

Problem Description

You are given two m x n binary matrices grid1 and grid2 containing only 0's (representing water) and 1's (representing land). An island is a group of 1's connected 4-directionally (horizontal or vertical). Any cells outside of the grid are considered water cells.

An island in grid2 is considered a sub-island if there is an island in grid1 that contains all the cells that make up this island in grid2.

Return the *number of islands in grid2 that are considered sub-islands*.

Example 1:

Input: grid1 = [[1,1,1,0,0],[0,1,1,1,1],[0,0,0,0,0],[1,0,0,0,0],[1,1,0,1,1]], grid2 = [[1,1,1,0,0],[0,0,1,1,1],[0,1,0,0,0],[1,0,1,1,0],[0,1,0,1,0]]
Output: 3
Explanation: In the picture above, the grid on the left is grid1 and the grid on the right is grid2.
The 1s colored red in grid2 are those considered to be part of a sub-island. There are three sub-islands.

Example 2:

Input: grid1 = [[1,0,1,0,1],[1,1,1,1,1],[0,0,0,0,0],[1,1,1,1,1],[1,0,1,0,1]], grid2 = [[0,0,0,0,0],[1,1,1,1,1],[0,1,0,1,0],[0,1,0,1,0],[1,0,0,0,1]]
Output: 2 
Explanation: In the picture above, the grid on the left is grid1 and the grid on the right is grid2.
The 1s colored red in grid2 are those considered to be part of a sub-island. There are two sub-islands.

Constraints:

- `m == grid1.length == grid2.length`

- `n == grid1[i].length == grid2[i].length`

- `1 <= m, n <= 500`

- `grid1[i][j]` and `grid2[i][j]` are either `0` or `1`.

Topics: Array, Depth-First Search, Breadth-First Search, Union-Find, Matrix

---

Approach

BFS (Graph/Matrix)

Use a queue to explore nodes level by level. Start from source node(s), visit all neighbors before moving to the next level. BFS naturally finds shortest paths in unweighted graphs.

When to use

Shortest path in unweighted graph, level-order processing, spreading/flood fill.

Union-Find

Maintain disjoint sets with two operations: find (which set does element belong to?) and union (merge two sets). Use path compression and union by rank for near O(1) amortized operations.

When to use

Connected components, cycle detection in undirected graphs, grouping elements.

Matrix

Treat the matrix as a 2D grid. Common techniques: directional arrays (dx, dy) for movement, BFS/DFS for connected regions, in-place marking for visited cells, boundary traversal for spiral patterns.

When to use

Grid traversal, island problems, path finding, rotating/transforming matrices.

---

Solutions

Solution 1: C# (Best: 492 ms)

Metric	Value
Runtime	492 ms
Memory	55.9 MB
Date	2022-02-21

Solution

public class Solution {
    public int CountSubIslands(int[][] grid1, int[][] grid2) {
        int m = grid1.Length;
    int n = grid1[0].Length;
    bool[,] used = new bool[m,n];
    int result = 0;
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            bool isSub = true;
            if(grid2[i][j] == 1 && !used[i,j]) {
                countSubIslands(grid1, grid2, i, j, m, n, ref isSub, used);
            if(isSub) result++;
            }
        }
    }
    return result;

}

private void countSubIslands(int[][] grid1, int[][] grid2, int i, int j, int m, int n, ref bool isSub, bool[,] used)
{
    if(i<0 || i>= m || j<0 || j>=n || used[i,j] || grid2[i][j] == 0)
    {
        return;
    }
    if(grid1[i][j] != 1) isSub &= false;
    used[i, j] = true;
    countSubIslands(grid1, grid2, i - 1, j, m, n, ref isSub, used);
    countSubIslands(grid1, grid2, i + 1, j, m, n, ref isSub, used);
    countSubIslands(grid1, grid2, i, j-1, m, n, ref isSub, used);
    countSubIslands(grid1, grid2, i, j+1, m, n, ref isSub, used);
}
}

---

Complexity Analysis

Approach	Time	Space
Graph BFS/DFS	$O(V + E)$	$O(V)$
Union-Find	$O(n × α(n))$	$O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• LeetCode provides 2 hint(s) for this problem — try solving without them first.

💡 Hints

Hint 1: Let's use floodfill to iterate over the islands of the second grid

Hint 2: Let's note that if all the cells in an island in the second grid if they are represented by land in the first grid then they are connected hence making that island a sub-island