Count Sub Islands - Video Solutions

Problem Overview: You are given two binary matrices grid1 and grid2. An island is a group of connected 1s (4-directionally). A sub-island exists when every land cell of an island in grid2 lies on land in the same position of grid1. The task is to count how many islands in grid2 are completely contained within islands of grid1.

Approach 1: DFS Flood Fill (O(m * n) time, O(m * n) space)

This approach treats each island in grid2 as a connected component and validates whether all its cells also correspond to land in grid1. Iterate through the matrix, and whenever you find an unvisited land cell in grid2, run a Depth‑First Search. During the DFS traversal, mark cells as visited and check the same position in grid1. If any cell of the explored island overlaps with water in grid1, the entire island cannot be a sub‑island. Maintain a boolean flag while exploring neighbors (up, down, left, right). If the flag remains true after the traversal, increment the result.

This works because DFS explores every cell of the island exactly once while validating the constraint. The grid is scanned once, and each cell participates in at most one DFS traversal. Time complexity is O(m * n). Space complexity is O(m * n) in the worst case due to recursion stack or visited marking. This approach directly applies standard graph traversal patterns used in Depth-First Search and grid problems involving a matrix.

Approach 2: Union-Find (Disjoint Set) (O(m * n * α(n)) time, O(m * n) space)

The Union-Find approach models each land cell as a node in a disjoint-set structure. First build connected components for islands in grid2 by unioning adjacent land cells. After building the sets, iterate through all land cells again and check whether any cell in a component overlaps with water in grid1. If that happens, mark the root of that component as invalid. Finally, count the number of distinct roots representing islands that were never marked invalid.

Union-Find is useful when you want explicit connected component management and fast merges using path compression and union by rank. The amortized complexity per operation is nearly constant (α(n)). Overall complexity becomes O(m * n * α(n)) time and O(m * n) space. This method is a strong example of the Union Find pattern commonly used in connectivity problems.

Recommended for interviews: The DFS flood-fill approach is the most expected solution. It is straightforward, easy to implement, and clearly shows understanding of grid traversal using DFS or BFS. Interviewers typically prefer this method because it validates each island during traversal with minimal overhead. The Union-Find solution demonstrates deeper knowledge of disjoint set structures and is useful when problems require dynamic connectivity or component merging.