1905. Count Sub Islands - Solutions and Explanation

Problem Statement

In this scenario, we are working with two m x n binary matrices named grid1 and grid2, each element of these matrices is either 0 or 1, where 0 represents water and 1 represents land. Islands are defined as clusters of adjacent 1s that are connected either horizontally or vertically. The boundary of the grid is surrounded by water.

The task is to determine how many islands composed of 1s in grid2 can be considered sub-islands. An island in grid2 qualifies as a sub-island if every land cell (value 1) of this island is also a land cell in the corresponding position in grid1.

The result to be returned is the count of such sub-islands.

Examples

Example 1

Input:

grid1 = [[1,1,1,0,0],[0,1,1,1,1],[0,0,0,0,0],[1,0,0,0,0],[1,1,0,1,1]], grid2 = [[1,1,1,0,0],[0,0,1,1,1],[0,1,0,0,0],[1,0,1,1,0],[0,1,0,1,0]]

Output:

Explanation:

In the picture above, the grid on the left is grid1 and the grid on the right is grid2.
The 1s colored red in grid2 are those considered to be part of a sub-island. There are three sub-islands.

Example 2

Input:

grid1 = [[1,0,1,0,1],[1,1,1,1,1],[0,0,0,0,0],[1,1,1,1,1],[1,0,1,0,1]], grid2 = [[0,0,0,0,0],[1,1,1,1,1],[0,1,0,1,0],[0,1,0,1,0],[1,0,0,0,1]]

Output:

Explanation:

In the picture above, the grid on the left is grid1 and the grid on the right is grid2.
The 1s colored red in grid2 are those considered to be part of a sub-island. There are two sub-islands.

Constraints

m == grid1.length == grid2.length
n == grid1[i].length == grid2[i].length
1 <= m, n <= 500
grid1[i][j] and grid2[i][j] are either 0 or 1.

Approach and Intuition

When considering the implementation for this problem, depth-first search (DFS) can be employed effectively to traverse through the islands in grid2 and simultaneously check their corresponding matches in grid1.

Steps for the DFS approach:

Iterate through each cell (i, j) in grid2.
When a land cell (1) is found, initiate a DFS from that cell to navigate through the entire island.
For each cell visited in grid2 during the DFS:
- Check if the corresponding cell in grid1 is also land (1). If it is, continue; if not, mark the entire island as not a sub-island.
Keep a global counter or a flag to keep track of whether all parts of the current island in grid2 are indeed part of an island in grid1.
After traversing the whole connected component (island) in grid2, if it's confirmed as a sub-island, increase your sub-island count.
Ensure that cells once visited are marked so as not to revisit them, which could lead to incorrect results or infinite loops. This marking can be done either by setting the cell to 0 in grid2 or using a separate visited structure.

Edge Cases:

If any cell in an island in grid2 does not have a corresponding 1 in grid1, then that entire island cannot be counted as a sub-island. This check must be comprehensive for every cell in the island.
The approach should be efficient enough to handle the upper constraint where both m and n can be up to 500.

By taking this standard approach of using DFS to track and verify islands, we can effectively count the number of sub-islands in grid2 as per the conditions provided by grid1. This conceptualization makes use of algorithmic approaches common in solving connected components problems on grids.

Solutions

C++
Java
Python

                            cpp
                            
                        
class Solution {
    int move[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    bool isLand(int x, int y, vector<vector<int>>& grid) {
        return grid[x][y] == 1;
    }

    class DisjointSet {
    public:
        vector<int> parent;
        vector<int> rank;

        DisjointSet(int n) {
            parent.resize(n);
            rank.resize(n, 0);
            for (int i = 0; i < n; ++i) {
                parent[i] = i;
            }
        }

        int find(int u) {
            if (parent[u] != u) {
                parent[u] = find(parent[u]);
            }
            return parent[u];
        }

        void unionByRank(int u, int v) {
            int rootU = find(u);
            int rootV = find(v);
            if (rootU != rootV) {
                if (rank[rootU] > rank[rootV]) {
                    parent[rootV] = rootU;
                } else if (rank[rootU] < rank[rootV]) {
                    parent[rootU] = rootV;
                } else {
                    parent[rootV] = rootU;
                    rank[rootU]++;
                }
            }
        }
    };

    int xyTo1D(int x, int y, int cols) {
        return x * cols + y;
    }

public:
    int countSubIslands(vector<vector<int>>& grid1, vector<vector<int>>& grid2) {
        int rows = grid2.size();
        int cols = grid2[0].size();
        DisjointSet ds(rows * cols);

        for (int x = 0; x < rows; ++x) {
            for (int y = 0; y < cols; ++y) {
                if (isLand(x, y, grid2)) {
                    for (auto& dir : move) {
                        int newX = x + dir[0], newY = y + dir[1];
                        if (newX >= 0 && newY >= 0 && newX < rows &&
                            newY < cols && isLand(newX, newY, grid2)) {
                            ds.unionByRank(
                                xyTo1D(x, y, cols),
                                xyTo1D(newX, newY, cols));
                        }
                    }
                }
            }
        }

        vector<bool> subIsland(rows * cols, true);
        for (int x = 0; x < rows; ++x) {
            for (int y = 0; y < cols; ++y) {
                if (isLand(x, y, grid2) && !isLand(x, y, grid1)) {
                    int root = ds.find(xyTo1D(x, y, cols));
                    subIsland[root] = false;
                }
            }
        }

        int subIslandCount = 0;
        for (int x = 0; x < rows; ++x) {
            for (int y = 0; y < cols; ++y) {
                if (isLand(x, y, grid2)) {
                    int root = ds.find(xyTo1D(x, y, cols));
                    if (subIsland[root]) {
                        subIslandCount++;
                        subIsland[root] = false;
                    }
                }
            }
        }

        return subIslandCount;
    }
};

The given C++ code defines a solution to find the number of sub-islands within a given grid. The code uses a class Solution with several helper functions and a nested DisjointSet class to manage components using the union-find algorithm.

Here’s what occurs in the program:

Matrix Movements: Movement directions are defined in a 2D array move to facilitate exploring adjacent cells in the grid.
Land Checking: The isLand function checks if a given cell in the grid contains land (represented as 1).
Disjoint Set for Union-Find:
- Initialization: Initializes parent and rank for each cell.
- Find and Union Operations: Implements the path compression technique in the find function and union by rank in the unionByRank function, which helps in merging components efficiently.
Main Function - countSubIslands:
- Initialization: Determine the rows and columns of the grid and initiate a DisjointSet.
- Identify All Components: For each land cell in grid2, it connects the cell to its adjacent cells (if also land) using union-find operations.
- Track Sub-island Components: Marks all components (starting roots in the union-find) that touch a cell in grid2 which is not a land in grid1 as not sub-islands.
- Counting Sub-islands: It counts and marks components that are confirmed as sub-islands (each component is only counted once).
Output: The function countSubIslands returns the number of sub-islands by examining each connected component of land cells in grid2 that corresponds completely with lands in grid1.

This solution efficiently maps out connected components of islands and then utilizes the disjoint set structure to count the number of valid sub-islands in grid2 based on the reference grid1. Overall, it demonstrates a complex example of union-find algorithm application in a grid-based problem.

                            java
                            
                        
class Solution {

    // Possible moves in the grid
    private final int[][] moves = {
        { 0, 1 },
        { 1, 0 },
        { 0, -1 },
        { -1, 0 },
    };

    // Check if the cell at position (x, y) in 'grid' is part of land
    private boolean isLand(int x, int y, int[][] grid) {
        return grid[x][y] == 1;
    }

    // Union-Find structure
    class DisjointSet {

        private final int[] root;
        private final int[] size;

        // Initialize a new Disjoint Set
        DisjointSet(int n) {
            root = new int[n];
            size = new int[n];
            for (int i = 0; i < n; i++) {
                root[i] = i;
                size[i] = 1;
            }
        }

        // Find operation with path compression
        int find(int u) {
            if (root[u] != u) {
                root[u] = find(root[u]);
            }
            return root[u];
        }

        // Union operation by size
        void union(int u, int v) {
            int rootU = find(u);
            int rootV = find(v);
            if (rootU != rootV) {
                if (size[rootU] > size[rootV]) {
                    root[rootV] = rootU;
                } else if (size[rootU] < size[rootV]) {
                    root[rootU] = rootV;
                } else {
                    root[rootV] = rootU;
                    size[rootU]++;
                }
            }
        }
    }

    // Convert grid coordinates to linear index
    private int index(int x, int y, int cols) {
        return x * cols + y;
    }

    public int countSubIslands(int[][] grid1, int[][] grid2) {
        int rows = grid2.length;
        int cols = grid2[0].length;
        DisjointSet ds = new DisjointSet(rows * cols);

        // Iteration over grid2 to connect land components
        for (int x = 0; x < rows; x++) {
            for (int y = 0; y < cols; y++) {
                if (isLand(x, y, grid2)) {
                    for (int[] move : moves) {
                        int adjX = x + move[0];
                        int adjY = y + move[1];
                        if (adjX >= 0 && adjY >= 0 && adjX < rows && adjY < cols && isLand(adjX, adjY, grid2)) {
                            ds.union(index(x, y, cols), index(adjX, adjY, cols));
                        }
                    }
                }
            }
        }

        // Validate sub-islands against grid1
        boolean[] validSubIsland = new boolean[rows * cols];
        for (int i = 0; i < validSubIsland.length; i++) {
            validSubIsland[i] = true;
        }
        for (int x = 0; x < rows; x++) {
            for (int y = 0; y < cols; y++) {
                if (isLand(x, y, grid2) && !isLand(x, y, grid1)) {
                    int root = ds.find(index(x, y, cols));
                    validSubIsland[root] = false;
                }
            }
        }

        // Count distinct sub-islands
        int count = 0;
        for (int x = 0; x < rows; x++) {
            for (int y = 0; y < cols; y++) {
                if (isLand(x, y, grid2)) {
                    int root = ds.find(index(x, y, cols));
                    if (validSubIsland[root]) {
                        count++;
                        validSubIsland[root] = false;
                    }
                }
            }
        }

        return count;
    }
}

The presented solution in Java addresses the problem of counting sub-islands in a two-dimensional grid. The main approach is to utilize a disjoint set (Union-Find) data structure to efficiently determine the connectivity and count of sub-islands in grid2 that are completely contained within islands of grid1.

Grid Navigation Setup:
- Define four possible moves which allow traversal in all cardinal directions within the grid.
Checking for Land:
- Implement a function to determine whether a specific cell in the grid is part of the land (indicated by the value 1).
Union-Find Data Structure:
- Initialize and manage a union-find system to keep track of connected components (islands) in the grid.
- Uses path compression in the find operation to speed up subsequent queries.
- Employs union by size to keep the tree flat, leading to efficient queries and updates.
Core Functions:
- Use a helper function to linearly index the grid's two-dimensional position for effective union-find operations.
- In the main function, connect respective positions in grid2 where the land cells are adjacent.
- Exclude cells in grid2 from being part of a sub-island if they correspond to water cells (value 0) in grid1.
Validation and Counting:
- Establish an array to validate potential sub-islands, marking invalid positions where grid1 does not have land.
- Iterate through grid2, counting the unique root representatives of valid sub-islands ensuring each root is counted exactly once to avoid duplications.

This solution efficiently integrates disjoint set data structure with grid traversal and component validation checks to calculate the total number of distinct sub-islands. The strategy focuses on marking union-find roots that are ineligible due to mismatches in the primary grid, therefore directly capturing and counting only valid sub-islands based on the given criteria.

                            python
                            
                        
class Solution:
    possible_moves = [(0, 1), (1, 0), (0, -1), (-1, 0)]

    def check_land(self, x, y, grid):
        return grid[x][y] == 1

    class DisjointSet:
        def __init__(self, size):
            self.parent = list(range(size))
            self.rank = [0] * size

        def find(self, node):
            if self.parent[node] != node:
                self.parent[node] = self.find(self.parent[node])
            return self.parent[node]

        def union(self, node1, node2):
            root1 = self.find(node1)
            root2 = self.find(node2)
            if root1 != root2:
                if self.rank[root1] > self.rank[root2]:
                    self.parent[root2] = root1
                elif self.rank[root1] < self.rank[root2]:
                    self.parent[root1] = root2
                else:
                    self.parent[root2] = root1
                    self.rank[root1] += 1

    def xy_to_index(self, x, y, cols):
        return x * cols + y

    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:
        rows = len(grid2)
        cols = len(grid2[0])
        ds = self.DisjointSet(rows * cols)

        for row in range(rows):
            for col in range(cols):
                if self.check_land(row, col, grid2):
                    for move in self.possible_moves:
                        new_row = row + move[0]
                        new_col = col + move[1]
                        if (0 <= new_row < rows and 0 <= new_col < cols and
                            self.check_land(new_row, new_col, grid2)):
                            ds.union(self.xy_to_index(row, col, cols), self.xy_to_index(new_row, new_col, cols))

        sub_island = [True] * (rows * cols)
        for row in range(rows):
            for col in range(cols):
                if self.check_land(row, col, grid2) and not self.check_land(row, col, grid1):
                    root = ds.find(self.xy_to_index(row, col, cols))
                    sub_island[root] = False

        count = 0
        for row in range(rows):
            for col in range(cols):
                if self.check_land(row, col, grid2):
                    root = ds.find(self.xy_to_index(row, col, cols))
                    if sub_island[root]:
                        count += 1
                        sub_island[root] = False

        return count

The provided Python solution defines a method to count sub-islands where every part of a sub-island from a second grid (grid2) is also present in the first grid (grid1). The approach utilizes a Disjoint Set (Union-Find) data structure, which helps in efficiently managing and merging sets of elements.

Initialize a Disjoint Set for the total number of elements in the grid (rows * cols).
Traverse through grid2 and union connected components (lands connected horizontally or vertically).
For each land found in grid2, check if it is also a land in grid1. If not, mark its root in the union-find structure as not being a sub-island.
Iterate through all positions in grid2 again. For each piece of land that is confirmed as a sub-island in both grids (by checking the Disjoint Set), count it and ensure it is not double-counted by marking it as counted.

The problem is solved using a DFS-like algorithm through the Disjoint Set to unionize and find connected components. This way, you determine whether chunks of land in grid2 are sub-islands by checking if they exist entirely within grid1. The final result is computed by counting unique roots of sub-islands that are still marked as true in a separate tracking array.

Optimally, this solution works across all cells of the two grids and applies union and find operations making it efficient and suitable for large data sets. The use of additional Boolean arrays for tracking visited and valid sub-island roots ensures that each sub-island is only counted once.

Comments

No comments yet.

Count Sub Islands

Problem Statement

Examples

Example 1

Example 2

Constraints

Approach and Intuition

Solutions

Comments

Products

Features

Solutions

Marketplace

Resources

Company