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.
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.