Sponsored
Sponsored
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.
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.
1def dfs(grid1, grid2, i, j, is_sub_island):
2 if i < 0 or i >= len(grid2) or j < 0 or j >= len(grid2[0]) or grid2[i][j] == 0:
3 return
4 if grid1[i][j] == 0:
5 is_sub_island[0] = False
6 grid2[i][j] = 0
7 dfs(grid1, grid2, i+1, j, is_sub_island)
8 dfs(grid1, grid2, i-1, j, is_sub_island)
9 dfs(grid1, grid2, i, j+1, is_sub_island)
10 dfs(grid1, grid2, i, j-1, is_sub_island)
11
12
13class Solution:
14 def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:
15 count = 0
16 for i in range(len(grid2)):
17 for j in range(len(grid2[0])):
18 if grid2[i][j] == 1:
19 is_sub_island = [True]
20 dfs(grid1, grid2, i, j, is_sub_island)
21 if is_sub_island[0]:
22 count += 1
23 return count
24
25
26# Example usage
27if __name__ == "__main__":
28 sol = Solution()
29 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]]
30 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]]
31 print(sol.countSubIslands(grid1, grid2))By utilizing DFS in Python, we iterate over grid2 to identify starting points of islands, and traverse them to assess if each corresponds entirely within islands in grid1, consequently counting valid sub-islands.
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.
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.
1
For JavaScript, this solution uses Union-Find to connect and group islands within grid1, examining grid2 islands for complete overlap to ascertain sub-island status.