How to Solve Count Sub Islands

To solve Count Sub Islands, iterate through each cell in grid2 using depth-first search to detect islands. For each island in grid2, check if every land cell corresponds to land in grid1. Increment the sub-island count only when the entire island in grid2 is fully contained within a corresponding island in grid1, leveraging flood-fill to efficiently traverse connected components.

Problem Statement

You are given two binary matrices, grid1 and grid2, each of size m x n containing 0s for water and 1s for land. An island is defined as a group of 1s connected horizontally or vertically. Any cell outside the grid boundaries is considered water.

An island in grid2 qualifies as a sub-island if all its land cells are present in an island in grid1. Return the total number of such sub-islands in grid2. For example, given 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]] and 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]], the correct output is 3.

Examples

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

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

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.

Solution Approach

Flood-Fill Traversal with DFS

Use DFS to traverse every unvisited land cell in grid2. For each island discovered, recursively visit all connected 1s to map its extent. During traversal, check whether each visited cell corresponds to land in grid1. If any cell in grid2 island is water in grid1, mark the island as invalid.

Counting Sub-Islands

Maintain a counter for valid sub-islands. After completing DFS for an island, increment the counter only if the island was fully contained in grid1. This ensures partially overlapping islands are excluded and prevents double-counting.

Optimization and Space Handling

Mark visited cells in grid2 in-place to avoid revisiting. Since each cell is visited once, time complexity is O(mn) and space complexity is O(mn) due to the recursion stack or iterative DFS stack. Avoid unnecessary copies to stay within memory limits.

Complexity Analysis

The algorithm traverses each cell once with DFS, yielding O(mn) time. Space is O(mn) to store recursion stack in worst-case when an island covers the entire grid.

What Interviewers Usually Probe

• Candidate identifies DFS or flood-fill pattern for island detection.
• Candidate considers validating island containment against grid1 during traversal.
• Candidate tracks visited cells to prevent revisiting and ensures correct sub-island count.

Common Pitfalls or Variants

Common pitfalls

• Failing to check every cell of grid2 island against grid1 leads to false positives.
• Not marking visited cells results in double-counting islands or infinite recursion.
• Using BFS without proper containment check may incorrectly include partial overlaps.

Follow-up variants

• Using BFS instead of DFS for flood-fill traversal.
• Counting sub-islands when diagonal connections are considered part of islands.
• Extending to 3D grids or multi-layer maps with similar containment logic.

How GhostInterview Helps

• GhostInterview highlights the flood-fill pattern specifically for Count Sub Islands.
• It identifies failure modes where grid2 islands partially overlap grid1 and prevents false counting.
• It suggests in-place marking and optimized DFS to manage memory and recursion depth.

Topic Pages

• Array
• Depth-First Search
• Breadth-First Search
• Union Find
• Matrix

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

FAQ

What is the main pattern used in Count Sub Islands?

The main pattern is Array plus Depth-First Search to traverse islands and check full containment.

Can BFS be used instead of DFS for this problem?

Yes, BFS can replace DFS for flood-fill traversal, but containment checks for each cell must still be applied.

What is the time complexity of detecting sub-islands?

Time complexity is O(m*n) because every cell in grid2 is visited once during DFS.

Why is marking visited cells important in this problem?

Marking visited cells prevents revisiting, avoids double-counting, and ensures correct sub-island identification.

How does GhostInterview help with this problem?

It guides through DFS flood-fill on grid2, checks containment in grid1, and manages recursion efficiently to count sub-islands accurately.