Count Sub Islands - Leetcode Solution

The Count Sub Islands problem on LeetCode challenges us to count the number of sub islands in a given grid of islands. A sub island is defined as an island that is entirely contained within another island.

To solve this problem, we need to perform a DFS (depth-first search) on every island in the given grid and check if it is a valid sub island or not. If a given island is found to be a sub island, we increment the count.

Here is a detailed step-by-step solution to solve this problem:

Step 1: Initialize count to 0 and create a visited 2D array of the same size as the input grid to keep track of already visited islands.

Step 2: Traverse through the input grid row by row and column by column, checking if the current cell is not visited and is an island (i.e., has a value of 1).

Step 3: If the current cell is an island and not visited, perform DFS on it to check if it is a valid sub island. The DFS function will take in the current cell position, the visited array, and the parent island area (which is initially zero).

Step 4: During DFS, start exploring the neighboring cells of the current cell in all four directions (left, right, top, bottom). If the neighboring cell is also a 1 and not visited, continue DFS recursively on that cell, marking it as visited and adding its area to the parent island's area.

Step 5: Once DFS completes, check if the parent island is entirely contained within the current island or not. This can be verified by checking if the parent island's area is equal to the area of the current island. If yes, increment count.

Step 6: After completing DFS on all islands, return the count of sub islands.

Here is the Python code implementation of the above solution:

def countSubIslands(grid1: List[List[int]], grid2: List[List[int]]) -> int:
    rows, cols = len(grid1), len(grid1[0])
    visited = [[False for j in range(cols)] for i in range(rows)]
    count = 0
    
    def DFS(i: int, j: int, parent_area: int) -> bool:
        if i < 0 or i >= rows or j < 0 or j >= cols or visited[i][j] or grid2[i][j] != 1:
            return True
        visited[i][j] = True
        area = 1 + parent_area
        if not DFS(i+1, j, area) or not DFS(i-1, j, area) or not DFS(i, j+1, area) or not DFS(i, j-1, area):
            return False
        if grid1[i][j] == 1:
            return parent_area == area
        return True
    
    for i in range(rows):
        for j in range(cols):
            if not visited[i][j] and grid2[i][j] == 1:
                if DFS(i, j, 0):
                    count += 1
                    
    return count

In the above code, we are taking in two input grids - grid1 and grid2. grid1 is the original input grid of islands, whereas grid2 is a modified grid where some cells might have zero values. We perform DFS on grid2 to check for sub islands. We first initialize count and visited arrays. We then traverse through grid2 to find unvisited islands and perform DFS on them. During DFS, we explore the neighboring cells and keep calculating the area of the parent island. After DFS completes, we check if the area of the parent island is entirely contained within the current island or not and increment count accordingly. Finally, we return the count of sub islands.

Time Complexity: O(MN), where MN is the size of the input grid. Space Complexity: O(M*N), for the visited array.

1