1905. Count Sub Islands


Problem Description

In this problem, you are given two matrices grid1 and grid2 of the same dimensions, m x n, where each cell contains a 0 or a 1. The value 1 represents a piece of land, while 0 represents water. An island is defined as a group of 1s that are connected horizontally or vertically. The task is to count the number of islands in grid2 that are sub-islands. A sub-island in grid2 is characterized by every bit of land (1) that is also part of an island in grid1. In other words, we want to count the islands in grid2 where every land cell of that island is also land in grid1.

Flowchart Walkthrough

First, let's analyze the problem using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

  • Yes: The grids in the problem can be treated as graphs where each cell is a node, and edges exist between adjacent cells with the value 1.

Is it a tree?

  • No: Each grid may have multiple connected components, each of which may contain cycles due to their grid structure, so the structures are not trees.

Is the problem related to directed acyclic graphs (DAGs)?

  • No: This problem involves checking sub-islands across two grid maps, which does not fit the nature of directed acyclic graphs.

Is the problem related to shortest paths?

  • No: The goal is to count sub-islands, not to find shortest paths.

Does the problem involve connectivity?

  • Yes: The problem requires identifying whether one area (island) in one grid encloses completely within an area (island) in another grid, which involves checking connectivity.

Is the graph weighted?

  • No: Connectivity in each grid is uniform, with edges existing solely based on adjacency without varied weights.

Conclusion: The flowchart suggests that for an unweighted connectivity problem such as this, where DFS is typically preferred for easily tracking visited nodes and recursively exploring neighbors, Depth-First Search (DFS) is the appropriate algorithm to use. DFS helps track and match islands in one grid to those in another comprehensively.

Intuition

The solution to this problem lies in traversing the islands in grid2 and checking whether they are completely contained within the islands of grid1. Depth-First Search (DFS) is a fitting approach for traversing islands, as we can explore all connected land cells (1s) from any starting land cell.

The DFS function will be the core of our approach. It is recursively called on adjacent land cells of grid2. For each land cell in grid2, the function checks whether the corresponding cell in grid1 is also a land cell. If not, this land cell does not fulfill the condition of being part of a sub-island.

During each DFS call, we mark the visited cells in grid2 as water (by setting them to 0) to avoid revisiting them. The DFS will return False if any part of the current 'island' in grid2 is not land in grid1, indicating that this island cannot be considered a sub-island. Only if all parts of an island in grid2 are also land in grid1, it will return True.

This process is repeated for all cells in grid2. The sum of instances where DFS returns True gives us the count of sub-islands. This approach effectively traverses through all possible islands in grid2, and by comparing against grid1, it determines the count of sub-islands as specified in the problem.

Learn more about Depth-First Search, Breadth-First Search and Union Find patterns.

Solution Approach

The solution makes use of Depth-First Search (DFS), which is a recursive algorithm used to explore all possible paths from a given point in a graph-like structure, such as our binary matrix. In this context, we use DFS to explore and mark the cells that make up each island in grid2.

We define a recursive function dfs inside our Solution class's countSubIslands method. This dfs function is crucial to the solution:

  • It takes the current coordinate (i, j) as input, corresponding to the current cell in grid2.
  • If the cell in grid1 at (i, j) is not land (if grid1[i][j] is not 1), the current path of DFS cannot be a sub-island, and it returns False.
  • The function marks the cell in grid2 as visited by setting grid2[i][j] to 0.
  • The DFS explores all 4-directionally adjacent cells (up, down, left, right) by calling itself on each neighboring land cell (x, y) in grid2 that hasn't been visited yet.
  • If any recursive call to dfs returns False, it means that not all cells of this island in grid2 are present in grid1. Hence, the function propagates this failure by returning False as well.
  • If all adjacent land cells of the current cell in grid2 are also land cells in grid1, the function returns True, indicating that the current path is a valid sub-island.

In the countSubIslands method, we iterate through every cell of grid2:

  • We initiate a DFS search from each unvisited land cell found in grid2.
  • We use a list comprehension that counts how many times the dfs function returns True for the starting cells of potential sub-islands. This gives us the total number of sub-islands in grid2.

We gather this count and return it as the solution. The use of recursion via DFS allows us to explore each island in grid2 exhaustively, easily comparing its cells with grid1 to determine if it's a sub-island or not.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's illustrate the solution approach using a small example.

Imagine we have the following two matrices (grid1 and grid2):

1grid1:      grid2:
21 1 0       1 1 0
30 1 1       0 1 0
41 0 1       1 0 1

Here, we want to find the number of sub-islands in grid2 where every '1' (land) is also present on the same position in grid1.

When applying the DFS algorithm, we start at each unvisited cell containing a '1' in grid2, and we attempt to traverse the entire island to which this cell belongs.

We start at the first cell of grid2:

  • The corresponding cell in grid1 is also a '1', so we continue the DFS and mark the cell in grid2 as visited by setting it to '0'.
  • DFS explores adjacent cells. The cell to the right is a '1' in both grid1 and grid2, so we continue and mark it in grid2.
  • Now, all adjacent cells (up, down, left, right) are '0' in grid2, so this path's DFS concludes this is a valid sub-island.

Next, we skip the second cell on the first row since it has already been visited, and move on to unvisited '1's.

The next starting point for DFS will be the second cell of the second row:

  • In grid1, the cell is '1', but we notice the cell below it which is '1' in grid2 is '0' in grid1, which invalidates this path for a sub-island.
  • Even though the DFS would explore the right cell in grid2, which is '1' in grid1, the previous failure means that the whole island is not a sub-island.

Finally, we visit the last row:

  • Starting from the first cell, the DFS would recognize this cell as a '1' in both grids, but the cells right and down are '0' in grid2, so there is no need to continue the DFS from this point.
  • Moving to the third cell, it's a '1' in both grids, and all adjacent cells are '0' in grid2, so this is considered a valid sub-island.

Now, our list comprehension would have counted two instances where dfs returned True, indicating that there are two sub-islands in grid2.

Thus, based on our DFS exploration and the rules specified, we return the count of sub-islands, which in this example is 2.

Solution Implementation

1class Solution:
2    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:
3        # Depth-first search function to explore the island in grid2 and check if it's a sub-island of grid1
4        def dfs(row, col):
5            is_sub_island = grid1[row][col] == 1  # Check if the current position is land in grid1
6            grid2[row][col] = 0  # Mark the current position in grid2 as visited (water)
7            # Explore in all 4 neighboring directions (left, right, up, down)
8            for delta_row, delta_col in [[0, -1], [0, 1], [-1, 0], [1, 0]]:
9                new_row, new_col = row + delta_row, col + delta_col
10                # If the new position is within the bounds and is land in grid2
11                if 0 <= new_row < num_rows and 0 <= new_col < num_cols and grid2[new_row][new_col] == 1:
12                    # If any part of the island in grid2 is not in grid1, it's not a sub-island
13                    if not dfs(new_row, new_col):
14                        is_sub_island = False
15            return is_sub_island
16
17        # Get the number of rows and columns in either of the grids
18        num_rows, num_cols = len(grid1), len(grid1[0])
19
20        # Count the number of sub-islands in grid2 that are also in grid1
21        sub_islands_count = 0
22        for row in range(num_rows):
23            for col in range(num_cols):
24                # If the current position is land in grid2 and is also a sub-island
25                if grid2[row][col] == 1 and dfs(row, col):
26                    sub_islands_count += 1
27
28        # Return the total count of sub-islands
29        return sub_islands_count
30
1class Solution {
2  
3    // Method to count sub-islands
4    public int countSubIslands(int[][] grid1, int[][] grid2) {
5        int rows = grid1.length;    // Number of rows in the grid
6        int cols = grid1[0].length; // Number of columns in the grid
7        int subIslandsCount = 0;    // Initialize count of sub-islands
8      
9        // Iterate over all cells in grid2
10        for (int i = 0; i < rows; ++i) {
11            for (int j = 0; j < cols; ++j) {
12                // If we find a land cell in grid2, we perform DFS to check if it's a sub-island
13                if (grid2[i][j] == 1 && isSubIsland(i, j, rows, cols, grid1, grid2)) {
14                    subIslandsCount++; // Increment count if a sub-island is found
15                }
16            }
17        }
18        return subIslandsCount; // Return the total count of sub-islands
19    }
20
21    // Helper method to perform DFS and check if the current island in grid2 is a sub-island of grid1
22    private boolean isSubIsland(int row, int col, int rows, int cols, int[][] grid1, int[][] grid2) {
23        // Check if the current cell is also a land cell in grid1; initialize as a potential sub-island
24        boolean isSub = grid1[row][col] == 1;
25        grid2[row][col] = 0; // Mark the cell as visited by setting it to water
26      
27        // Directions for top, right, bottom, and left (for traversing adjacent cells)
28        int[] dirRow = {-1, 0, 1, 0};
29        int[] dirCol = {0, 1, 0, -1};
30      
31        // Explore all adjacent cells
32        for (int k = 0; k < 4; ++k) {
33            int newRow = row + dirRow[k];
34            int newCol = col + dirCol[k];
35            // Check if the adjacent cell is within grid bounds and has not been visited
36            if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols && grid2[newRow][newCol] == 1
37                // Recursively call DFS; if any part of the island is not a sub-island, mark as not a sub-island
38                && !isSubIsland(newRow, newCol, rows, cols, grid1, grid2)) {
39                isSub = false;
40            }
41        }
42        return isSub; // Return true if all parts of the island are sub-islands, false otherwise
43    }
44}
45
1class Solution {
2public:
3    // Function to count the number of sub-islands
4    int countSubIslands(vector<vector<int>>& grid1, vector<vector<int>>& grid2) {
5        int rowCount = grid1.size(); // Number of rows in the grid
6        int colCount = grid1[0].size(); // Number of columns in the grid
7        int subIslandCount = 0; // Counter for sub-islands
8      
9        // Loop through every cell in grid2
10        for (int row = 0; row < rowCount; ++row) {
11            for (int col = 0; col < colCount; ++col) {
12                // If cell is land and DFS confirms it's a sub-island, increment count
13                if (grid2[row][col] == 1 && depthFirstSearch(row, col, rowCount, colCount, grid1, grid2)) {
14                    ++subIslandCount;
15                }
16            }
17        }
18      
19        return subIslandCount; // Return the total count of sub-islands
20    }
21
22    // Helper DFS function to explore the island and check if it is a sub-island
23    bool depthFirstSearch(int row, int col, int rowCount, int colCount, vector<vector<int>>& grid1, vector<vector<int>>& grid2) {
24        // Initialize as true if the corresponding cell in grid1 is also land
25        bool isSubIsland = grid1[row][col] == 1;
26        // Mark the cell as visited in grid2
27        grid2[row][col] = 0;
28      
29        // Defining directions for exploring adjacent cells
30        vector<int> directions = {-1, 0, 1, 0, -1};
31        // Explore all four adjacent cells
32        for (int k = 0; k < 4; ++k) {
33            int nextRow = row + directions[k];
34            int nextCol = col + directions[k + 1];
35          
36            // Continue DFS if the next cell is within bounds and is land
37            if (nextRow >= 0 && nextRow < rowCount && 
38                nextCol >= 0 && nextCol < colCount && 
39                grid2[nextRow][nextCol] == 1) {
40                // If any part of the island is not a sub-island, set the flag to false
41                if (!depthFirstSearch(nextRow, nextCol, rowCount, colCount, grid1, grid2)) {
42                    isSubIsland = false;
43                }
44            }
45        }
46      
47        // Return true if all parts of the island are a sub-island
48        return isSubIsland;
49    }
50};
51
1function countSubIslands(grid1: number[][], grid2: number[][]): number {
2    let rowCount = grid1.length;
3    let colCount = grid1[0].length;
4    let subIslandCount = 0;  // This will hold the count of sub-islands.
5
6    // Iterate over each cell in the second grid.
7    for (let row = 0; row < rowCount; ++row) {
8        for (let col = 0; col < colCount; ++col) {
9            // Start DFS if we find land (1) on grid2.
10            if (grid2[row][col] === 1 && dfs(grid1, grid2, row, col)) {
11                subIslandCount++;  // Increment when a sub-island is found.
12            }
13        }
14    }
15    return subIslandCount;
16}
17
18function dfs(grid1: number[][], grid2: number[][], i: number, j: number): boolean {
19    let rowCount = grid1.length;
20    let colCount = grid1[0].length;
21    let isSubIsland = true;  // Flag indicating if a piece of land is a sub-island.
22
23    // If corresponding cell in grid1 isn't land, this piece can't be a sub-island.
24    if (grid1[i][j] === 0) {
25        isSubIsland = false;
26    }
27
28    grid2[i][j] = 0;  // Sink the visited land piece to avoid revisits.
29
30    // The 4 possible directions we can move (right, left, down, up).
31    const directions = [
32        [0, 1],
33        [0, -1],
34        [1, 0],
35        [-1, 0],
36    ];
37
38    // Explore all 4 directions.
39    for (let [dx, dy] of directions) {
40        let newX = i + dx;
41        let newY = j + dy;
42
43        // Check for valid grid bounds and if the cell is land in grid2.
44        if (newX >= 0 && newX < rowCount && newY >= 0 && newY < colCount && grid2[newX][newY] === 1) {
45            // Recursively call dfs. If one direction is not a sub-island, the whole is not.
46            if (!dfs(grid1, grid2, newX, newY)) {
47                isSubIsland = false;
48            }
49        }
50    }
51
52    return isSubIsland;  // Return the status of current piece being part of sub-island.
53}
54

Time and Space Complexity

Time Complexity

The time complexity of the given code primarily depends on the number of calls to the dfs function as it traverses grid2. In the worst case, every cell in grid2 might be equal to 1, requiring a dfs call for each. Since we iterate over each cell exactly once due to the modification of grid2 in the dfs function (we set grid2[i][j] to 0 to avoid revisiting), the worst-case time complexity is O(m * n) where m is the number of rows and n is the number of columns in grid2. This is because the time complex for each dfs call can be bounded by the surrounding cells (at most 4 additional calls per cell), leading to each cell being visited only once.

Space Complexity

The space complexity is determined by the maximum depth of the recursion stack during the execution of the dfs function. In the worst case, the recursion could be as deep as the total number of cells in grid2 if the grid represents one large island that needs to be traversed entirely. Therefore, the worst-case space complexity would be O(m * n) due to the depth of the recursive call stack. However, in practice, the space complexity is often less since not all cells will be part of a singular recursive chain.

Learn more about how to find time and space complexity quickly using problem constraints.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Which of these pictures shows the visit order of a depth-first search?


Recommended Readings