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 1
s 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 ingrid2
. - If the cell in
grid1
at(i, j)
is not land (ifgrid1[i][j]
is not1
), the current path of DFS cannot be a sub-island, and it returnsFalse
. - The function marks the cell in
grid2
as visited by settinggrid2[i][j]
to0
. - The DFS explores all 4-directionally adjacent cells (up, down, left, right) by calling itself on each neighboring land cell
(x, y)
ingrid2
that hasn't been visited yet. - If any recursive call to
dfs
returnsFalse
, it means that not all cells of this island ingrid2
are present ingrid1
. Hence, the function propagates this failure by returningFalse
as well. - If all adjacent land cells of the current cell in
grid2
are also land cells ingrid1
, the function returnsTrue
, 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 returnsTrue
for the starting cells of potential sub-islands. This gives us the total number of sub-islands ingrid2
.
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 EvaluatorExample 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 ingrid2
as visited by setting it to '0'. - DFS explores adjacent cells. The cell to the right is a '1' in both
grid1
andgrid2
, so we continue and mark it ingrid2
. - 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' ingrid2
is '0' ingrid1
, which invalidates this path for a sub-island. - Even though the DFS would explore the right cell in
grid2
, which is '1' ingrid1
, 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.
Which of these pictures shows the visit order of a depth-first search?
Recommended Readings
https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS
https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell
Union Find Disjoint Set Union Data Structure Introduction Prerequisite Depth First Search Review problems dfs_intro Once we have a strong grasp of recursion and Depth First Search we can now introduce Disjoint Set Union DSU This data structure is motivated by the following problem Suppose we have sets of elements