1905. Count Sub Islands

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

1. 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.
2. 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.
3. 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.
4. 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
};