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 (horizontal or vertical). 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.
Return the number of islands in grid2 that are considered sub-islands.
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 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 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 sub-island. There are two sub-islands.
Constraints:
m == grid1.length == grid2.lengthn == grid1[i].length == grid2[i].length1 <= m, n <= 500grid1[i][j] and grid2[i][j] are either 0 or 1.This approach uses Depth-First Search (DFS) to explore each island in grid2, checking if it matches an area in grid1. We iterate through each cell in grid2, initiating a DFS whenever we encounter land (1). During DFS, we verify if the entire island in grid2 can be found in grid1. If during exploration, we encounter a cell that is 1 in grid2 but 0 in grid1, we mark it as not a sub-island.
We first traverse all cells in grid2. Upon encountering a cell that is part of an island (i.e., its value is 1), we start a DFS to explore the entire structure connected to this cell. During this DFS, for every cell in the current island of grid2, we check if corresponding cells in grid1 are also land. If we find a water cell (0) in grid1 where there's land in grid2, we set isSubIsland to false. If DFS completes and isSubIsland remains true, we increment our count of sub-islands.
C++
Java
Python
C#
JavaScript
Time Complexity: O(m * n), where m and n are the dimensions of the grids, as each cell is visited a constant number of times.
Space Complexity: O(1) additional space not counting input and stack space for recursion.
This approach uses the Union-Find data structure to efficiently group connected islands. By initially identifying all islands in both grids, we can ascertain the sub-islands by ensuring that connected components (islands) in grid2 are completely represented within connected components in grid1.
This C solution uses a Union-Find (Disjoint Set Union) to connect land cells into islands for grid1 and checks consistency for grid2. Islands in grid2 are counted as sub-islands only if each forms a connected component fully within an island in grid1.
C++
Java
Python
C#
JavaScript
Time Complexity: O(m * n * (α(m*n))), where α is the Inverse Ackermann function, a very slow-growing function.
Space Complexity: O(m * n) to store the parent and rank arrays.
| Approach | Complexity |
|---|---|
| DFS Approach | Time Complexity: O(m * n), where m and n are the dimensions of the grids, as each cell is visited a constant number of times. |
| Union-Find Approach | Time Complexity: O(m * n * (α(m*n))), where α is the Inverse Ackermann function, a very slow-growing function. |
NUMBER OF ISLANDS - Leetcode 200 - Python • NeetCode • 384,140 views views
Watch 9 more video solutions →Practice Count Sub Islands with our built-in code editor and test cases.
Practice on FleetCode