Dare2Solve
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.
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.
Initialize Variables:
visited
set to track visited cells to avoid redundant work.DFS Traversal:
isSub()
to perform DFS from a given cell.Main Loop:
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:
O(m * n)
. We traverse each cell once, and the DFS explores all connected cells.
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.
class Solution {
public:
int countSubIslands(vector<vector<int>>& grid1, vector<vector<int>>& grid2) {
int count = 0;
int ROWS = grid1.size();
int COLS = grid1[0].size();
vector<pair<int, int>> dir = {{0, -1}, {1, 0}, {0, 1}, {-1, 0}};
unordered_set<string> visited;
auto getKey = [](int r, int c) {
return to_string(r) + "-" + to_string(c);
};
function<bool(int, int)> 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;
}
};
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
class Solution {
private int ROWS;
private int COLS;
private int[][] dir = {{0, -1}, {1, 0}, {0, 1}, {-1, 0}};
private Set<String> 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;
}
}
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
};