1905. Count Sub Islands
Difficulty: Medium
Topics: Array
, DepthFirst Search
, BreadthFirst Search
, Union Find
, Matrix
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 4directionally (horizontal or vertical). Any cells outside of the grid are considered water cells.
An island in grid2
is considered a subisland if there is an island in grid1
that contains all the cells that make up this island in grid2
.
Return the number of islands in grid2
that are considered subislands.
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

Explanation:
 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 subisland. There are three subislands.
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

Explanation:
 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 subisland. There are two subislands.
Constraints:
m == grid1.length == grid2.length
n == grid1[i].length == grid2[i].length
1 <= m, n <= 500

grid1[i][j]
andgrid2[i][j]
are either0
or1
.
Hint:
 Let's use floodfill to iterate over the islands of the second grid
 Let's note that if all the cells in an island in the second grid if they are represented by land in the first grid then they are connected hence making that island a subisland
Solution:
We'll use the DepthFirst Search (DFS) approach to explore the islands in grid2
and check if each island is entirely contained within a corresponding island in grid1
. Here's how we can implement the solution:
Steps:

Traverse the Grid: We'll iterate through each cell in
grid2
. 
Identify Islands in
grid2
: When we encounter a land cell (1
) ingrid2
, we'll use DFS to explore the entire island. 
Check SubIsland Condition: While performing DFS on an island in
grid2
, we'll check if all the corresponding cells ingrid1
are also land cells. If they are, the island is a subisland. 
Count SubIslands: For each island in
grid2
that meets the subisland condition, we'll increment our subisland count.
Let's implement this solution in PHP: 1905. Count Sub Islands
<?php
/**
* @param $grid1
* @param $grid2
* @return int
*/
function countSubIslands($grid1, $grid2) {
...
...
...
/**
* go to ./solution.php
*/
}
/**
* @param $grid1
* @param $grid2
* @param $i
* @param $j
* @param $m
* @param $n
* @return inttrue
*/
function dfs(&$grid1, &$grid2, $i, $j, $m, $n) {
...
...
...
/**
* go to ./solution.php
*/
}
// Example usage:
// Example 1
$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]
];
echo countSubIslands($grid1, $grid2); // Output: 3
// Example 2
$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]
];
echo countSubIslands($grid1, $grid2); // Output: 2
?>
Explanation:

DFS Function: The
dfs
function explores the island ingrid2
and checks if the corresponding cells ingrid1
are all land cells. If any cell ingrid2
is land but the corresponding cell ingrid1
is water, the island ingrid2
is not a subisland. 
Mark Visited: As we traverse
grid2
, we mark cells as visited by setting them to0
. 
Main Loop: We iterate through all cells in
grid2
. Whenever we find a land cell that hasn't been visited, we initiate a DFS to check if it's part of a subisland.
Time Complexity:
The time complexity is (O(m \times n)) where m
is the number of rows and n
is the number of columns. This is because we potentially visit every cell once.
This solution should work efficiently within the given constraints.
Contact Links
If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!
If you want more helpful content like this, feel free to follow me:
Top comments (0)