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.
1class Solution {
2 public void dfs(int[][] grid1, int[][] grid2, int i, int j, boolean[] isSubIsland) {
3 if (i < 0 || i >= grid2.length || j < 0 || j >= grid2[0].length || grid2[i][j] == 0) {
4 return;
5 }
6 if (grid1[i][j] == 0) {
7 isSubIsland[0] = false;
8 }
9 grid2[i][j] = 0;
10 dfs(grid1, grid2, i + 1, j, isSubIsland);
11 dfs(grid1, grid2, i - 1, j, isSubIsland);
12 dfs(grid1, grid2, i, j + 1, isSubIsland);
13 dfs(grid1, grid2, i, j - 1, isSubIsland);
14 }
15
16 public int countSubIslands(int[][] grid1, int[][] grid2) {
17 int count = 0;
18 for (int i = 0; i < grid2.length; i++) {
19 for (int j = 0; j < grid2[0].length; j++) {
20 if (grid2[i][j] == 1) {
21 boolean[] isSubIsland = {true};
22 dfs(grid1, grid2, i, j, isSubIsland);
23 if (isSubIsland[0]) {
24 count++;
25 }
26 }
27 }
28 }
29 return count;
30 }
31
32 public static void main(String[] args) {
33 Solution sol = new Solution();
34 int[][] 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}};
35 int[][] 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}};
36 System.out.println(sol.countSubIslands(grid1, grid2));
37 }
38}This Java version implements the DFS strategy to find and verify sub-islands within the grid. The solution ensures that matching islands between grid1 and grid2 are identified correctly.
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 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.