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.
1public class Solution {
2 public void DFS(int[][] grid1, int[][] grid2, int i, int j, ref bool isSubIsland) {
3 if (i < 0 || i >= grid2.Length || j < 0 || j >= grid2[0].Length || grid2[i][j] == 0) return;
4 if (grid1[i][j] == 0) isSubIsland = false;
5 grid2[i][j] = 0;
6 DFS(grid1, grid2, i + 1, j, ref isSubIsland);
7 DFS(grid1, grid2, i - 1, j, ref isSubIsland);
8 DFS(grid1, grid2, i, j + 1, ref isSubIsland);
9 DFS(grid1, grid2, i, j - 1, ref isSubIsland);
10 }
11
12 public int CountSubIslands(int[][] grid1, int[][] grid2) {
13 int m = grid2.Length, n = grid2[0].Length, count = 0;
14 for (int i = 0; i < m; i++) {
15 for (int j = 0; j < n; j++) {
16 if (grid2[i][j] == 1) {
17 bool isSubIsland = true;
18 DFS(grid1, grid2, i, j, ref isSubIsland);
19 if (isSubIsland) count++;
20 }
21 }
22 }
23 return count;
24 }
25
26 public static void Main() {
27 Solution solution = new Solution();
28 int[][] grid1 = new int[][] {
29 new int[] {1, 1, 1, 0, 0},
30 new int[] {0, 1, 1, 1, 1},
31 new int[] {0, 0, 0, 0, 0},
32 new int[] {1, 0, 0, 0, 0},
33 new int[] {1, 1, 0, 1, 1}
34 };
35 int[][] grid2 = new int[][] {
36 new int[] {1, 1, 1, 0, 0},
37 new int[] {0, 0, 1, 1, 1},
38 new int[] {0, 1, 0, 0, 0},
39 new int[] {1, 0, 1, 1, 0},
40 new int[] {0, 1, 0, 1, 0}
41 };
42 Console.WriteLine(solution.CountSubIslands(grid1, grid2));
43 }
44}This C# implementation effectively finds all islands in grid2 and uses DFS to determine if they are sub-islands by evaluating matching land areas in grid1.
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
This Python implementation adopts a Union-Find strategy to align components within grid1 and aligns islands in grid2 relative to these components, allowing only completely overlapping islands to be counted as sub-islands.