You are given two 2D grids, grid1 and grid2, both representing islands, where grid1 represents the original island and grid2 represents a sub-island formed by cutting out a rectangle from grid1. The values 1 in the grids represent land, and 0 represents water.
A sub-island is considered valid if all the cells of the sub-island (grid2) are also present and identical in the original island (grid1). You need to count the number of valid sub-islands.
Table of Contents
Sample Input:
grid1:
[
[1, 1, 1],
[0, 1, 0],
[1, 1, 1]
]
grid2:
[
[1, 1],
[1, 0],
[1, 1]
]
Expected Output:
2
In this example, there are two valid sub-islands in grid1, which are identical to grid2. They are formed by the following rectangles:
- Top-left corner:
[[1, 1], [0, 1], [1, 1]] - Bottom-right corner:
[[1, 0], [1, 1]]
Time and Space Complexity:
The time complexity of the algorithm is O(m * n), where ‘m’ is the number of rows and ‘n’ is the number of columns in the grids. In the worst case, we may have to visit each cell once to compare the sub-islands.
The space complexity is O(m * n) as well, due to the recursion stack, which can grow to the size of the grids in the worst case.
C++ solution:
#include <iostream>
#include <vector>
void dfs(std::vector<std::vector<int>>& grid1, std::vector<std::vector<int>>& grid2, int row, int col, bool& isSubIsland) {
int rows = grid1.size();
int cols = grid1[0].size();
// Base case: If the current cell is out of bounds or it is not land (1) in the sub-island, return.
if (row < 0 || row >= rows || col < 0 || col >= cols || grid2[row][col] == 0) {
return;
}
// Check if the current cell is not land (0) or is different from the corresponding cell in the original island.
if (grid1[row][col] == 0 || grid2[row][col] != 1) {
isSubIsland = false;
return;
}
// Mark the current cell as visited in the sub-island by changing it to 0.
grid2[row][col] = 0;
// Recursively explore all adjacent cells (top, bottom, left, right).
dfs(grid1, grid2, row - 1, col, isSubIsland); // Top neighbor
dfs(grid1, grid2, row + 1, col, isSubIsland); // Bottom neighbor
dfs(grid1, grid2, row, col - 1, isSubIsland); // Left neighbor
dfs(grid1, grid2, row, col + 1, isSubIsland); // Right neighbor
}
int countSubIslands(std::vector<std::vector<int>>& grid1, std::vector<std::vector<int>>& grid2) {
int rows = grid2.size();
int cols = grid2[0].size();
int count = 0;
// Iterate through the sub-island to find each valid sub-island.
for (int i = 0; i < rows; ++i) {
for (int j = 0; j < cols; ++j) {
if (grid2[i][j] == 1) {
// Start the recursion to check if the current sub-island is valid.
bool isSubIsland = true;
dfs(grid1, grid2, i, j, isSubIsland);
// If the sub-island is valid, increment the count of valid sub-islands.
if (isSubIsland) {
count++;
}
}
}
}
return count;
}
int main() {
// Construct the grids for the sample input
std::vector<std::vector<int>> grid1 = {
{1, 1, 1},
{0, 1, 0},
{1, 1, 1}
};
std::vector<std::vector<int>> grid2 = {
{1, 1},
{1, 0},
{1, 1}
};
// Count the number of valid sub-islands
int subIslandCount = countSubIslands(grid1, grid2);
// Print the result
std::cout << "Valid Sub-Islands Count: " << subIslandCount << std::endl;
return 0;
}
The dfs function is a helper function that performs a depth-first search (DFS) to check if the sub-island is valid. It starts from a given cell in the sub-island and marks it as visited by changing it to 0. Then, it recursively explores all its adjacent cells (top, bottom, left, right) that are land (1) in the sub-island and checks if the corresponding cells in the original island are also land (1).
The countSubIslands function is the entry point of the algorithm. It iterates through the sub-island to find each valid sub-island. Whenever it finds a cell that is land (1) in the sub-island, it starts the recursion to check if the entire sub-island is valid. If the sub-island is valid, it increments the count of valid sub-islands.
In the given example, the function will correctly count the number of valid sub-islands, and the output will be 2.