1905. Count Sub Islands

Problem Description

In this problem, you are given two matrices grid1 and grid2 of the same dimensions, m x n, where each cell contains a 0 or a 1. The value 1 represents a piece of land, while 0 represents water. An island is defined as a group of 1s that are connected horizontally or vertically. The task is to count the number of islands in grid2 that are sub-islands. A sub-island in grid2 is characterized by every bit of land (1) that is also part of an island in grid1. In other words, we want to count the islands in grid2 where every land cell of that island is also land in grid1.

Intuition

The solution to this problem lies in traversing the islands in grid2 and checking whether they are completely contained within the islands of grid1. Depth-First Search (DFS) is a fitting approach for traversing islands, as we can explore all connected land cells (1s) from any starting land cell.

The DFS function will be the core of our approach. It is recursively called on adjacent land cells of grid2. For each land cell in grid2, the function checks whether the corresponding cell in grid1 is also a land cell. If not, this land cell does not fulfill the condition of being part of a sub-island.

During each DFS call, we mark the visited cells in grid2 as water (by setting them to 0) to avoid revisiting them. The DFS will return False if any part of the current 'island' in grid2 is not land in grid1, indicating that this island cannot be considered a sub-island. Only if all parts of an island in grid2 are also land in grid1, it will return True.

This process is repeated for all cells in grid2. The sum of instances where DFS returns True gives us the count of sub-islands. This approach effectively traverses through all possible islands in grid2, and by comparing against grid1, it determines the count of sub-islands as specified in the problem.

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

Solution Approach

The solution makes use of Depth-First Search (DFS), which is a recursive algorithm used to explore all possible paths from a given point in a graph-like structure, such as our binary matrix. In this context, we use DFS to explore and mark the cells that make up each island in grid2.

We define a recursive function dfs inside our Solution class's countSubIslands method. This dfs function is crucial to the solution:

• It takes the current coordinate (i, j) as input, corresponding to the current cell in grid2.
• If the cell in grid1 at (i, j) is not land (if grid1[i][j] is not 1), the current path of DFS cannot be a sub-island, and it returns False.
• The function marks the cell in grid2 as visited by setting grid2[i][j] to 0.
• The DFS explores all 4-directionally adjacent cells (up, down, left, right) by calling itself on each neighboring land cell (x, y) in grid2 that hasn't been visited yet.
• If any recursive call to dfs returns False, it means that not all cells of this island in grid2 are present in grid1. Hence, the function propagates this failure by returning False as well.
• If all adjacent land cells of the current cell in grid2 are also land cells in grid1, the function returns True, indicating that the current path is a valid sub-island.

In the countSubIslands method, we iterate through every cell of grid2:

• We initiate a DFS search from each unvisited land cell found in grid2.
• We use a list comprehension that counts how many times the dfs function returns True for the starting cells of potential sub-islands. This gives us the total number of sub-islands in grid2.

We gather this count and return it as the solution. The use of recursion via DFS allows us to explore each island in grid2 exhaustively, easily comparing its cells with grid1 to determine if it's a sub-island or not.

Example Walkthrough

Let's illustrate the solution approach using a small example.

Imagine we have the following two matrices (grid1 and grid2):

1grid1:      grid2:
21 1 0       1 1 0
30 1 1       0 1 0
41 0 1       1 0 1

Here, we want to find the number of sub-islands in grid2 where every '1' (land) is also present on the same position in grid1.

When applying the DFS algorithm, we start at each unvisited cell containing a '1' in grid2, and we attempt to traverse the entire island to which this cell belongs.

We start at the first cell of grid2:

• The corresponding cell in grid1 is also a '1', so we continue the DFS and mark the cell in grid2 as visited by setting it to '0'.
• DFS explores adjacent cells. The cell to the right is a '1' in both grid1 and grid2, so we continue and mark it in grid2.
• Now, all adjacent cells (up, down, left, right) are '0' in grid2, so this path's DFS concludes this is a valid sub-island.

Next, we skip the second cell on the first row since it has already been visited, and move on to unvisited '1's.

The next starting point for DFS will be the second cell of the second row:

• In grid1, the cell is '1', but we notice the cell below it which is '1' in grid2 is '0' in grid1, which invalidates this path for a sub-island.
• Even though the DFS would explore the right cell in grid2, which is '1' in grid1, the previous failure means that the whole island is not a sub-island.

Finally, we visit the last row:

• Starting from the first cell, the DFS would recognize this cell as a '1' in both grids, but the cells right and down are '0' in grid2, so there is no need to continue the DFS from this point.
• Moving to the third cell, it's a '1' in both grids, and all adjacent cells are '0' in grid2, so this is considered a valid sub-island.

Now, our list comprehension would have counted two instances where dfs returned True, indicating that there are two sub-islands in grid2.

Thus, based on our DFS exploration and the rules specified, we return the count of sub-islands, which in this example is 2.

Solution Implementation

Time and Space Complexity

Time Complexity

The time complexity of the given code primarily depends on the number of calls to the dfs function as it traverses grid2. In the worst case, every cell in grid2 might be equal to 1, requiring a dfs call for each. Since we iterate over each cell exactly once due to the modification of grid2 in the dfs function (we set grid2[i][j] to 0 to avoid revisiting), the worst-case time complexity is O(m * n) where m is the number of rows and n is the number of columns in grid2. This is because the time complex for each dfs call can be bounded by the surrounding cells (at most 4 additional calls per cell), leading to each cell being visited only once.

Space Complexity

The space complexity is determined by the maximum depth of the recursion stack during the execution of the dfs function. In the worst case, the recursion could be as deep as the total number of cells in grid2 if the grid represents one large island that needs to be traversed entirely. Therefore, the worst-case space complexity would be O(m * n) due to the depth of the recursive call stack. However, in practice, the space complexity is often less since not all cells will be part of a singular recursive chain.

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