Count Sub Islands
MediumArrayDepth-First SearchBreadth-First SearchUnion FindMatrix
Solution
export function countSubIslands(grid1: number[][], grid2: number[][]): number {
const [m, n] = [grid1.length, grid1[0].length];
for (let y = 0; y < m; y++) {
for (let x = 0; x < n; x++) {
if (grid1[y][x] === 0 && grid2[y][x] === 1) {
findSubIslands(grid2, y, x);
}
}
}
let answer = 0;
for (let y = 0; y < m; y++) {
for (let x = 0; x < n; x++) {
if (grid2[y][x] === 1) {
findSubIslands(grid2, y, x);
answer += 1;
}
}
}
return answer;
}
function findSubIslands(grid: number[][], y: number, x: number): void {
if (y < 0 || grid.length <= y || x < 0 || grid[0].length <= x || grid[y][x] === 0) {
return;
}
grid[y][x] = 0;
findSubIslands(grid, y + 1, x);
findSubIslands(grid, y - 1, x);
findSubIslands(grid, y, x + 1);
findSubIslands(grid, y, x - 1);
}
Complexity
- Time:
O(MN)
- Space:
O(MN)