#1905

Medium

auto_awesomeArray plus Depth-First Search

LeetCode Problem Workspace

Count Sub Islands

Identify and count all islands in grid2 that are fully contained within islands of grid1 using DFS traversal efficiently.

array depth first search breadth first search union find matrix

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(m n) and space complexity is O(m n) due to the recursion stack or iterative DFS stack. Avoid unnecessary copies to stay within memory limits.

Complexity Analysis

Metric	Value
Time	O(m * n)
Space	O(m * n)

The algorithm traverses each cell once with DFS, yielding O(m n) time. Space is O(m n) 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.

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.

terminal

Solution

Solution 1: DFS

We can traverse each cell $(i, j)$ in the matrix `grid2`. If the value of the cell is $1$, we start a depth-first search from this cell, set the value of all cells connected to this cell to $0$, and record whether the corresponding cell in `grid1` is also $1$ for all cells connected to this cell. If it is $1$, it means that this cell is also an island in `grid1`, otherwise it is not. Finally, we count the number of sub-islands in `grid2`.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:
        def dfs(i: int, j: int) -> int:
            ok = grid1[i][j]
            grid2[i][j] = 0
            for a, b in pairwise(dirs):
                x, y = i + a, j + b
                if 0 <= x < m and 0 <= y < n and grid2[x][y] and not dfs(x, y):
                    ok = 0
            return ok

        m, n = len(grid1), len(grid1[0])
        dirs = (-1, 0, 1, 0, -1)
        return sum(dfs(i, j) for i in range(m) for j in range(n) if grid2[i][j])

Continue Practicing

#1970 last day where you can still cross #1631 path with minimum effort #1559 detect cycles in 2d grid