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.
1function dfs(grid1, grid2, i, j, isSubIsland) {
2 if (i < 0 || i >= grid2.length || j < 0 || j >= grid2[0].length || grid2[i][j] === 0) {
3 return;
4 }
5 if (grid1[i][j] === 0) {
6 isSubIsland[0] = false;
7 }
8 grid2[i][j] = 0;
9 dfs(grid1, grid2, i + 1, j, isSubIsland);
10 dfs(grid1, grid2, i - 1, j, isSubIsland);
11 dfs(grid1, grid2, i, j + 1, isSubIsland);
12 dfs(grid1, grid2, i, j - 1, isSubIsland);
13}
14
15function countSubIslands(grid1, grid2) {
16 let count = 0;
17 for (let i = 0; i < grid2.length; i++) {
18 for (let j = 0; j < grid2[0].length; j++) {
19 if (grid2[i][j] === 1) {
20 let isSubIsland = [true];
21 dfs(grid1, grid2, i, j, isSubIsland);
22 if (isSubIsland[0]) {
23 count++;
24 }
25 }
26 }
27 }
28 return count;
29}
30
31// Example usage
32const grid1 = [
33 [1,1,1,0,0],
34 [0,1,1,1,1],
35 [0,0,0,0,0],
36 [1,0,0,0,0],
37 [1,1,0,1,1]
38];
39const grid2 = [
40 [1,1,1,0,0],
41 [0,0,1,1,1],
42 [0,1,0,0,0],
43 [1,0,1,1,0],
44 [0,1,0,1,0]
45];
46console.log(countSubIslands(grid1, grid2));The JavaScript implementation executes a DFS to discover sub-islands by exploring all potential islands in grid2, ensuring boundary conditions are honored and checking against 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.
1using namespace std;
class UnionFind {
public:
UnionFind(int size) : parent(size), rank(size, 0) {
for (int i = 0; i < size; ++i) {
parent[i] = i;
}
}
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
void unite(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) {
if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else {
parent[rootY] = rootX;
rank[rootX]++;
}
}
}
private:
vector<int> parent;
vector<int> rank;
};
int countSubIslands(vector<vector<int>>& grid1, vector<vector<int>>& grid2) {
int m = grid1.size(), n = grid1[0].size();
UnionFind uf(m * n);
auto getIndex = [&](int x, int y) -> int {
return x * n + y;
};
// Union for grid1
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid1[i][j] == 1) {
for (const auto& d : vector<pair<int, int>>{{1, 0}, {0, 1}}) {
int ni = i + d.first, nj = j + d.second;
if (ni < m && nj < n && grid1[ni][nj] == 1) {
uf.unite(getIndex(i, j), getIndex(ni, nj));
}
}
}
}
}
vector<bool> found(m * n, false);
int count = 0;
// Check for grid2
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid2[i][j] == 1) {
bool isSubIsland = true;
int root = uf.find(getIndex(i, j));
if (!found[root]) {
for (const auto& d : vector<pair<int, int>>{{1, 0}, {0, 1}, {-1, 0}, {0, -1}}) {
int ni = i + d.first, nj = j + d.second;
if (ni >= 0 && nj >= 0 && ni < m && nj < n && grid2[ni][nj] == 1) {
if (uf.find(getIndex(i, j)) != uf.find(getIndex(ni, nj))) {
isSubIsland = false;
}
}
}
if (isSubIsland) {
found[root] = true;
count++;
}
}
}
}
}
return count;
}
int main() {
vector<vector<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}};
vector<vector<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}};
cout << countSubIslands(grid1, grid2) << endl;
return 0;
}This C++ solution leverages the Union-Find (Disjoint Set) structure to efficiently find and merge islands (connected components) within grid1. Once connected components are established for grid1, islands in grid2 are checked for eligibility as sub-islands based on component containment.