Problem Description

You are given two m x n binary matrices grid1 and grid2 where each cell contains either 0 (representing water) or 1 (representing land).

An island is defined as a group of 1s that are connected horizontally or vertically (4-directionally). Any cells outside the grid boundaries are considered water.

The task is to find how many islands in grid2 are sub-islands of islands in grid1.

A sub-island is an island in grid2 where every single cell of that island has a corresponding land cell (1) at the same position in grid1. In other words, if you overlay an island from grid2 onto grid1, every land cell of the grid2 island must match with a land cell in grid1.

For example:

• If grid2 has an island at positions [(0,0), (0,1), (1,0)]
• This island is a sub-island only if grid1 also has 1s at all three positions: (0,0), (0,1), and (1,0)
• If even one of these positions in grid1 is 0 (water), then the island in grid2 is NOT a sub-island

The function should return the total count of islands in grid2 that qualify as sub-islands.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: The problem involves a 2D grid where land cells (1s) form islands through 4-directional connectivity. This is a classic graph problem where each cell is a node and adjacent land cells form edges.

Is it a tree?

• No: The problem is not about tree structures. We have a 2D grid with potentially multiple disconnected islands, and cells can form cycles (e.g., a square of four 1s).

Is the problem related to directed acyclic graphs?

• No: The connectivity between land cells is undirected (if cell A is connected to cell B, then B is also connected to A), and the problem doesn't involve directed edges or acyclic properties.

Is the problem related to shortest paths?

• No: We're not finding shortest paths between nodes. Instead, we need to explore entire islands to verify if they are sub-islands.

Does the problem involve connectivity?

• Yes: The core of the problem is about connectivity - we need to identify connected components (islands) in grid2 and check if all cells in each component have corresponding land cells in grid1.

Does the problem have small constraints?

• Yes: With grid dimensions up to m x n, and the need to explore each island completely while checking conditions, the problem has manageable constraints suitable for DFS exploration.

DFS/backtracking?

• Yes: DFS is perfect for exploring all cells of an island, marking visited cells, and simultaneously checking if the island qualifies as a sub-island.

Conclusion: The flowchart suggests using DFS to traverse each island in grid2, explore all its connected cells, and verify whether every cell in the island has a corresponding land cell in grid1.

Intuition

The key insight is that we need to verify if every island in grid2 is completely "covered" by land in grid1. Think of it like placing a puzzle piece (island from grid2) on top of a board (grid1) - the piece only fits if there's solid ground underneath every part of it.

When we encounter a land cell (1) in grid2, we know it's part of an island. We need to explore the entire island to check two things:

1. Find all cells that belong to this island in grid2
2. Verify that each of these cells has a corresponding land cell in grid1

DFS is perfect for this because it naturally explores all connected cells of an island. As we traverse each cell of an island in grid2, we can simultaneously check if grid1 has a 1 at the same position. If we find even one cell where grid2 has land but grid1 has water, the entire island fails to be a sub-island.

To avoid counting the same island multiple times, we can mark visited cells in grid2 by setting them to 0 as we explore. This serves two purposes:

• Prevents revisiting cells within the current island traversal
• Ensures we don't count the same island again when we continue scanning the grid

The elegant part of the solution is combining the traversal with the validation - we use DFS to both explore the island and verify the sub-island condition in a single pass. The DFS returns 1 if all cells of the current island have corresponding land in grid1, and 0 otherwise. By starting a DFS from each unvisited land cell in grid2 and summing up the results, we get the total count of sub-islands.

Learn more about Depth-First Search, Breadth-First Search and Union Find patterns.

Solution Approach

The solution uses DFS to traverse each island in grid2 and validate whether it's a sub-island. Here's how the implementation works:

Main Function Structure:

• We iterate through every cell (i, j) in grid2
• When we find a land cell (grid2[i][j] == 1), we initiate a DFS from that position
• Sum up the return values from all DFS calls to get the total count of sub-islands

DFS Implementation: The dfs(i, j) function performs the critical work:

1. Check Current Cell: First, we check if grid1[i][j] is 1. We store this in variable ok. If it's 0, this island cannot be a sub-island, but we still need to explore all its cells.

2. Mark as Visited: Set grid2[i][j] = 0 to mark this cell as visited, preventing infinite loops and ensuring we don't count the same island twice.

3. Explore Neighbors: Using the direction array dirs = (-1, 0, 1, 0, -1) and pairwise, we generate the four adjacent positions:

   • (i-1, j) - up
   • (i, j+1) - right
   • (i+1, j) - down
   • (i, j-1) - left

4. Recursive Exploration: For each valid neighbor that is:

   • Within grid boundaries: 0 <= x < m and 0 <= y < n
   • Is land in grid2: grid2[x][y] == 1

   We recursively call dfs(x, y). If any recursive call returns 0 (meaning that part of the island isn't covered by grid1), we set ok = 0.

5. Return Result: The function returns ok, which will be:

   • 1 if this cell and all connected cells have corresponding land in grid1
   • 0 if any cell in this island doesn't have corresponding land in grid1

Key Design Decisions:

• In-place Modification: We modify grid2 directly to mark visited cells, avoiding the need for a separate visited array.

• Short-circuit Logic: Even if we discover the island isn't a sub-island (ok = 0), we continue exploring all its cells to properly mark them as visited.

• Compact Direction Handling: The pairwise function with dirs array provides a clean way to iterate through the four directions.

The time complexity is O(m × n) where we visit each cell at most once, and space complexity is O(m × n) in the worst case for the recursion stack when the entire grid is one island.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach:

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

Step 1: Start scanning grid2 We begin at position (0,0). We find grid2[0][0] = 1, so we start a DFS.

Step 2: First DFS from (0,0)

• Check grid1[0][0] = 1 ✓ (ok = 1)
• Mark grid2[0][0] = 0 (visited)
• Check neighbors:
  • Up: out of bounds
  • Right: (0,1) has grid2[0][1] = 0 (water, skip)
  • Down: (1,0) has grid2[1][0] = 1 (land, recurse)
  • Left: out of bounds

Step 3: Recursive DFS from (1,0)

• Check grid1[1][0] = 1 ✓ (ok = 1)
• Mark grid2[1][0] = 0 (visited)
• Check neighbors:
  • Up: (0,0) already visited (now 0)
  • Right: (1,1) has grid2[1][1] = 1 (land, recurse)
  • Down: (2,0) has grid2[2][0] = 0 (water, skip)
  • Left: out of bounds

Step 4: Recursive DFS from (1,1)

• Check grid1[1][1] = 1 ✓ (ok = 1)
• Mark grid2[1][1] = 0 (visited)
• Check neighbors:
  • Up: (0,1) has grid2[0][1] = 0 (water, skip)
  • Right: (1,2) has grid2[1][2] = 0 (water, skip)
  • Down: (2,1) has grid2[2][1] = 1 (land, recurse)
  • Left: (1,0) already visited (now 0)

Step 5: Recursive DFS from (2,1)

• Check grid1[2][1] = 1 ✓ (ok = 1)
• Mark grid2[2][1] = 0 (visited)
• Check neighbors: all are water or out of bounds
• Returns 1 to step 4

Step 6: Backtrack and complete

• Step 4 returns 1 to step 3
• Step 3 returns 1 to step 2
• Step 2 returns 1 (this island is a sub-island!)
• Count = 1

Step 7: Continue scanning grid2 The rest of grid2 is now all 0s (water or visited), so no more islands to check.

Final Result: 1 sub-island

The island at positions [(0,0), (1,0), (1,1), (2,1)] in grid2 has corresponding land cells at all positions in grid1, making it a valid sub-island.

Solution Implementation

Time and Space Complexity

Time Complexity: O(m × n) where m is the number of rows and n is the number of columns in the grids.

The algorithm visits each cell in grid2 at most once. The main loop iterates through all m × n cells, and for each cell that contains a 1 in grid2, it triggers a DFS traversal. During the DFS, each cell is visited exactly once because once visited, it's marked as 0 (preventing revisits). Therefore, the total number of operations across all DFS calls is bounded by the total number of cells, resulting in O(m × n) time complexity.

Space Complexity: O(m × n) where m is the number of rows and n is the number of columns in the grids.

The space complexity is dominated by the recursive call stack during DFS traversal. In the worst case, if grid2 contains a single island that spans all cells in a snake-like pattern, the DFS recursion depth could reach m × n levels deep. This would occur when the island forms a path that visits every cell sequentially, causing the recursive calls to stack up to a maximum depth of m × n. Therefore, the space complexity is O(m × n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall: Early Termination When Finding Non-Matching Cell

The Problem: A common mistake is to immediately return 0 when encountering a cell in the island that doesn't have corresponding land in grid1, like this:

def dfs(row: int, col: int) -> int:
    # WRONG: Early return when finding water in grid1
    if grid1[row][col] == 0:
        return 0  # This stops exploring the rest of the island!
  
    grid2[row][col] = 0
  
    for i in range(4):
        next_row = row + directions[i]
        next_col = col + directions[i + 1]
        if (0 <= next_row < rows and 
            0 <= next_col < cols and 
            grid2[next_row][next_col] == 1):
            if not dfs(next_row, next_col):
                return 0
  
    return 1

Why This Fails: When you return early, you leave parts of the island in grid2 unexplored and unmarked. These unvisited cells remain as 1s and will be encountered again in the main loop, causing them to be incorrectly counted as separate islands.

Example Scenario:

grid1:          grid2:
1 0 0           1 1 0
1 1 0           1 1 0

With early termination:

1. Start DFS at (0,0) - it's valid
2. Move to (0,1) - grid1[0][1] is 0, so return 0 immediately
3. The cells (1,0) and (1,1) in grid2 remain unvisited (still 1s)
4. Main loop later starts new DFS from (1,0), incorrectly counting it as another island

The Correct Approach: Always explore the entire island to mark all cells as visited, but track whether it's a valid sub-island:

def dfs(row: int, col: int) -> int:
    # Store validation result but continue exploration
    is_sub_island = grid1[row][col]
  
    # Mark as visited
    grid2[row][col] = 0
  
    # Explore ALL connected cells regardless of validity
    for i in range(4):
        next_row = row + directions[i]
        next_col = col + directions[i + 1]
        if (0 <= next_row < rows and 
            0 <= next_col < cols and 
            grid2[next_row][next_col] == 1):
            # Update validity but continue exploring
            if not dfs(next_row, next_col):
                is_sub_island = 0
  
    return is_sub_island

This ensures:

• Every cell of each island is visited exactly once
• Islands are correctly identified as single connected components
• The sub-island validation is properly propagated through the entire island