
Description
This problem involves identifying sub-islands within a grid. A sub-island in grid2 is defined as a connected component of 1s that exists entirely within a corresponding island in grid1. The task is to count the number of such sub-islands present in grid2.
Given two grids, grid1 and grid2, both of size m x n, we need to determine how many sub-islands in grid2 are also islands in grid1.
Intuition
The problem can be solved by iterating through each cell in grid2 and checking if it can be part of a sub-island that exists within grid1. By using a depth-first search (DFS), we can traverse the connected components (islands) in grid2 and verify if all parts of this component are also islands in grid1.
If any part of the component in grid2 is not an island in grid1, the whole component is not a sub-island. Otherwise, it is counted as a valid sub-island.
Approach
- Initialize Variables:
- Initialize a counter to keep track of the number of sub-islands found.
- Store grid dimensions and directions for DFS traversal.
- Use a
visited
set to track visited cells to avoid redundant work. - DFS Traversal:
- Create a helper function
isSub()
to perform DFS from a given cell. - This function checks if the current island in grid2 can be entirely mapped to grid1. If any cell in this connected component does not align with a corresponding 1 in grid1, return false. - Mark all cells of the component as visited. - Main Loop:
- Traverse each cell in grid2.
- If a cell is part of an unvisited island (
grid2[r][c] == 1
), initiate a DFS to determine if it's a valid sub-island. If it is, increment the sub-island counter. - Result: - After processing all cells, return the counter as the result.
Complexity
Time Complexity:
O(m * n)
. We traverse each cell once, and the DFS explores all connected cells.
Space Complexity:
O(m * n)
. The space complexity is primarily due to the visited
set, which stores up to m * n
elements, where m
is the number of rows and n
is the number of columns.
Code
C++
class Solution {
public:
int countSubIslands(vector>& grid1, vector>& grid2) {
int count = 0;
int ROWS = grid1.size();
int COLS = grid1[0].size();
vector> dir = {{0, -1}, {1, 0}, {0, 1}, {-1, 0}};
unordered_set visited;
auto getKey = [](int r, int c) {
return to_string(r) + "-" + to_string(c);
};
function isSub = [&](int r, int c) {
bool areSubParts = (grid1[r][c] == 1);
for (auto [rD, cD] : dir) {
int rNext = r + rD;
int cNext = c + cD;
string keyNext = getKey(rNext, cNext);
if (0 <= rNext && rNext < ROWS && 0 <= cNext && cNext < COLS && !visited.count(keyNext)) {
visited.insert(keyNext);
if (grid2[rNext][cNext] == 1) {
bool isNextSub = isSub(rNext, cNext);
areSubParts = areSubParts && isNextSub;
}
}
}
return areSubParts;
};
for (int r = 0; r < ROWS; ++r) {
for (int c = 0; c < COLS; ++c) {
string key = getKey(r, c);
if (!visited.count(key)) {
visited.insert(key);
if (grid2[r][c] == 1 && isSub(r, c)) {
count++;
}
}
}
}
return count;
}
};
Python
class Solution:
def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:
count = 0
ROWS, COLS = len(grid1), len(grid1[0])
dir = [(0, -1), (1, 0), (0, 1), (-1, 0)]
visited = set()
def get_key(r, c):
return f"{r}-{c}"
def is_sub(r, c):
are_sub_parts = (grid1[r][c] == 1)
for rD, cD in dir:
r_next, c_next = r + rD, c + cD
key_next = get_key(r_next, c_next)
if (
0 <= r_next < ROWS
and 0 <= c_next < COLS
and key_next not in visited
):
visited.add(key_next)
if grid2[r_next][c_next] == 1:
is_next_sub = is_sub(r_next, c_next)
are_sub_parts = are_sub_parts and is_next_sub
return are_sub_parts
for r in range(ROWS):
for c in range(COLS):
key = get_key(r, c)
if key not in visited:
visited.add(key)
if grid2[r][c] == 1 and is_sub(r, c):
count += 1
return count
Java
class Solution {
private int ROWS;
private int COLS;
private int[][] dir = {{0, -1}, {1, 0}, {0, 1}, {-1, 0}};
private Set visited;
public int countSubIslands(int[][] grid1, int[][] grid2) {
int count = 0;
ROWS = grid1.length;
COLS = grid1[0].length;
visited = new HashSet<>();
for (int r = 0; r < ROWS; r++) {
for (int c = 0; c < COLS; c++) {
String key = getKey(r, c);
if (!visited.contains(key)) {
visited.add(key);
if (grid2[r][c] == 1 && isSub(grid1, grid2, r, c)) {
count++;
}
}
}
}
return count;
}
private String getKey(int r, int c) {
return r + "-" + c;
}
private boolean isSub(int[][] grid1, int[][] grid2, int r, int c) {
boolean areSubParts = (grid1[r][c] == 1);
for (int[] d : dir) {
int rNext = r + d[0];
int cNext = c + d[1];
String keyNext = getKey(rNext, cNext);
if (0 <= rNext && rNext < ROWS && 0 <= cNext && cNext < COLS && !visited.contains(keyNext)) {
visited.add(keyNext);
if (grid2[rNext][cNext] == 1) {
boolean isNextSub = isSub(grid1, grid2, rNext, cNext);
areSubParts = areSubParts && isNextSub;
}
}
}
return areSubParts;
}
}
JavaScript
var countSubIslands = function (grid1, grid2) {
let count = 0
const ROWS = grid1.length
const COLS = grid1[0].length
const dir = [
[0, -1],
[1, 0],
[0, 1],
[-1, 0],
]
const visited = new Set()
const getKey = (r, c) => {
return `${r}-${c}`
}
const isSub = (r, c) => {
let areSubParts = (grid1[r][c] == 1)
for (let [rD, cD] of dir) {
const rNext = r + rD
const cNext = c + cD
const keyNext = getKey(rNext, cNext)
if (
0 <= rNext
&& rNext < ROWS
&& 0 <= cNext
&& cNext < COLS
&& !visited.has(keyNext)
) {
visited.add(keyNext)
if (grid2[rNext][cNext] == 1) {
const isNextSub = isSub(rNext, cNext)
areSubParts = areSubParts && isNextSub
}
}
}
return areSubParts
}
for (let r = 0; r < ROWS; r++) {
for (let c = 0; c < COLS; c++) {
const key = getKey(r, c)
if (!visited.has(key)) {
visited.add(key)
if (
grid2[r][c] == 1
&& isSub(r, c)
) {
count++
}
}
}
}
return count
};