Count Sub Islands Leetcode Problem 1905 [Python Solution]

Welcome back, coding enthusiasts!

Today, we'll tackle the Count Sub Islands problem from LeetCode.

This is a medium-level problem falling under the category of Graphs and is encountered by companies like Meta, Google, and Amazon.

So, if you're looking to enhance your graph algorithm skills, you're in the right place.

Problem Overview

You are given two m x n binary matrices, grid1 and grid2, containing only 0's (representing water) and 1's (representing land).

An island is a group of 1's connected 4-directionally (horizontally or vertically).

Any cells outside of the grid are considered water cells.

An island in grid2 is considered a sub-island if there is an island in grid1 that contains all the cells that make up this island in grid2.

Your task is to return the number of islands in grid2 that are considered sub-islands.

Example

Let's take a look at an example to better understand the problem:

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 considered part of sub-islands.

There are three sub-islands in this example.

Understanding Constraints

Before we dive into the solution, let's understand the constraints of this problem:

m is the number of rows in both grid1 and grid2.
n is the number of columns in both grid1 and grid2.
Both grid1 and grid2 have the same dimensions.
The values in grid1 and grid2 are either 0 or 1. Now that we have a clear understanding of the problem and its constraints, let's proceed with the solution.

Count Sub Islands LeetCode Problem Solution

We'll tackle this problem using a simultaneous Depth-First Search (DFS) approach.

The main idea is to iterate through every cell in grid2, and if we encounter a land cell (1) that hasn't been visited yet, we'll perform a DFS on it.

During the DFS, we'll check if the corresponding cell in grid1 is also a land cell (1).

If it is, we mark it as visited and continue the DFS.

If we successfully traverse an entire island in grid2 and every cell has a corresponding land cell in grid1, we increment our count of sub-islands.

We'll keep track of visited cells in a set to ensure we don't visit the same cell multiple times.

The DFS function is responsible for handling the traversal in all four directions while adhering to the constraints.

Let's dive into the Python solution:

1. Bruteforce Approach

Before implementing the DFS approach, let's understand that a brute-force approach is possible but highly inefficient.

It would involve mapping each island in grid1 to a list of its coordinates, doing the same for grid2, and then comparing these two hash maps.

This approach is neither efficient nor straightforward to code, so we won't delve into it.

2. Efficient Approach with Simultaneous DFS

Now, let's proceed with the efficient approach using simultaneous DFS.

Here's the Python code for it:

View on GitHub ➹

def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -&gt; int:
    # Get the dimensions of the grids
    ROWS, COLS = len(grid1), len(grid1[0])

    # Initialize a set to keep track of visited cells
    visit = set()

    def dfs(r, c):
        # Base case: Check if we go out of bounds or encounter water
        if (
            r &lt; 0
            or c &lt; 0
            or r == ROWS
            or c == COLS
            or grid2[r][c] == 0
            or (r, c) in visit
        ):
            return True

        # Mark the cell as visited
        visit.add((r, c))
        res = True

        if grid1[r][c] == 0:
            res = False

        # Recursive DFS in all four directions
        res = dfs(r - 1, c) and res
        res = dfs(r + 1, c) and res
        res = dfs(r, c - 1) and res
        res = dfs(r, c + 1) and res

        return res

    # Initialize the count of sub-islands
    count = 0

    # Iterate through all cells in grid2
    for r in range(ROWS):
        for c in range(COLS):
            if grid2[r][c] and (r, c) not in visit and dfs(r, c):
                count += 1

    return count

This code efficiently counts the sub-islands in grid2 and has a time complexity of O(m * n) and a space complexity of O(m * n) due to the use of the visit set.

Time and Space Complexity

Time Complexity: O(m * n)
Space Complexity: O(m * n)

This solution is both efficient and concise, ensuring we visit each cell only once and maintain a clean code structure.

Reasoning Behind Our Approach

The main idea behind our approach is to perform a simultaneous DFS on both grid1 and grid2.

We iterate through all the cells in grid2, and for each unvisited land cell, we perform a DFS to check if it forms a sub-island with corresponding cells in grid1.

If successful, we increment the count.

This approach ensures that we don't visit the same cells multiple times and efficiently handles the problem.

Conclusion

In this blog post, we explored the Count Sub Islands problem from LeetCode, which falls under the category of Graphs.

We discussed the problem statement, constraints, and provided a Python solution using a simultaneous Depth-First Search approach.

This solution efficiently counts the sub-islands in grid2 and has a time and space complexity of O(m * n).

I hope this explanation and Python solution have been helpful to you in understanding and solving this problem.

If you have any questions, suggestions, or comments, please feel free to share them below.

Happy coding!

For more details and to try the problem yourself, you can visit the LeetCode problem page.

Keep coding, keep learning,

and stay curious!