Editorial
Core insight
Count Sub Islands · Graph Traversal Patterns (DFS & BFS)
Core Insight for Count Sub Islands
The key insight for LeetCode 1905 is that we can validate the "sub-island" condition simultaneously while traversing the island in grid2. We do not need to store coordinates.
The condition for a sub-island is strict: ALL cells in the grid2 island must be land in grid1. This implies that if we encounter a single cell in the current grid2 island where grid1[r][c] is water (0), the entire island is disqualified.
However, a crucial detail often missed is that we cannot simply stop the traversal (short-circuit) when we find an invalid cell. We must continue the DFS to mark the entire island in grid2 as visited. If we stop early, the unvisited parts of the invalid island will be discovered later by the main loop, erroneously treated as a new island, and potentially counted.
Visualizing the Algorithm:
Imagine the recursion tree expanding from the first cell of an island in grid2. As the DFS flows into neighbor cells (up, down, left, right), it effectively "colors" the island to mark it as processed. Each node in this recursion tree performs a local check: "Is there land at this position in grid1?" The results of these checks are aggregated. If the local check fails or any child node reports a failure, the root of the recursion tree knows this island is not a sub-island.
Deep dive
Full breakdown
Full reasoning, pitfalls, and implementation flow
LeetCode 1905: Count Sub Islands Solution & Explanation
Problem Overview
TL;DR: Traverse every island in grid2 using Depth-First Search (DFS) and verify that every land cell visited corresponds to a land cell in grid1.
The problem asks us to determine the number of "sub-islands" in a binary matrix grid2. A sub-island is defined as a group of connected 1s (land) in grid2 where every single cell in that group also contains a 1 in the corresponding position in grid1. If even one cell of an island in grid2 overlaps with a 0 (water) in grid1, that group is not a sub-island. This is a popular interview question that tests your ability to manipulate matrices and perform graph traversals efficiently.
Brute Force Approach for Count Sub Islands
A naive or brute-force approach might involve a multi-pass strategy. First, one might traverse grid2 to identify all distinct islands and store the coordinates of every cell belonging to each island in a list of lists. After collecting all islands, the algorithm would iterate through each stored island and check the coordinates against grid1.
Pseudo-code:
1. Create a list `islands` to store sets of coordinates.
2. Iterate through grid2:
If cell is 1 and not visited:
Perform DFS/BFS to find the full island.
Store all (r, c) pairs of this island in `islands`.
3. Initialize count = 0.
4. For each island in `islands`:
is_sub_island = True
For each (r, c) in island:
If grid1[r][c] == 0:
is_sub_island = False
Break
If is_sub_island is True:
count++
5. Return count.Time Complexity: because we visit nodes a constant number of times. Space Complexity: to store the coordinates of all islands explicitly.
Why it is suboptimal: While the time complexity is technically linear with respect to the grid size, the space complexity is higher than necessary because we explicitly store island coordinates. Furthermore, this approach requires two distinct phases (collection and validation), which adds unnecessary code complexity. In an interview, we want to validate the sub-island property during the traversal to save space and keep the logic concise.
Algorithm Strategy: Graph Traversal Patterns (DFS & BFS)
- Iterate through
grid2: Use a nested loop to check every cell in the matrix. - Identify Unvisited Land: When a cell
grid2[i][j] == 1is found, it indicates the start of a new, unvisited island. - Initiate DFS: Start a Depth-First Search from this cell.
- Track Validity: The DFS function will return a boolean value indicating whether the connected component traversed is a valid sub-island.
- The function returns
trueif all cells in the component satisfygrid1[r][c] == 1. - It returns
falseif any cell corresponds togrid1[r][c] == 0.
- The function returns
- Enforce Full Traversal: The DFS must traverse the entire connected component in
grid2and mark cells as visited (e.g., by flipping1to0ingrid2) to prevent recounting. - Count: If the DFS returns
true, increment the sub-island counter.
Execution Flow
Let's trace the execution for a specific island in grid2:
- Main Loop: The scanner finds a
1atgrid2[0][0]. - DFS Start: We call
dfs(0, 0). - State Check: Inside the DFS:
- We check if the current cell in
grid1is1. Ifgrid1[0][0]is0, we flag this island as invalid (but continue traversing). - We mark
grid2[0][0]as0to mark it as visited.
- We check if the current cell in
- Recursive Expansion: We attempt to move in 4 directions.
- Move Right to
(0, 1): It's a1. Recursedfs(0, 1). - Move Down to
(1, 0): It's a0. Stop branch.
- Move Right to
- Aggregation:
- Suppose
dfs(0, 1)encounters a cell wheregrid1is0. It returnsfalse. - The parent call
dfs(0, 0)receives thisfalse. - Even if
(0, 0)itself was valid, thefalsefrom the neighbor propagates up.
- Suppose
- Completion: The DFS completes, having flipped all
1s in this component to0. The final result is returned to the main loop. Iftrue,countincreases.
Proof of Correctness
The algorithm relies on the property of Connected Components. By definition, a DFS starting at an unvisited node will visit every node reachable from (i.e., the entire island) exactly once, provided we mark nodes as visited.
The invariant we maintain is:
Our DFS implements this logical conjunction (AND operation). If any node fails the check (grid1[r][c] == 0), the conjunction becomes false. By visiting every node in the component, we ensure that the check is exhaustive for that island. By marking nodes as visited immediately, we ensure termination and prevent cycles. Thus, the count is strictly the number of components satisfying the invariant.
Pattern Reuse Notes
The Graph DFS - Connected Components pattern is fundamental for many grid problems.
- LeetCode 200: Number of Islands: The base case for this pattern. Just counts components without the secondary validation check.
- LeetCode 130: Surrounded Regions: Uses the same traversal but focuses on identifying islands connected to the boundary.
- LeetCode 417: Pacific Atlantic Water Flow: Runs DFS from boundaries to find reachable cells, intersecting two sets of reachable components.
- LeetCode 547: Number of Provinces: Applies the same connected components logic to an adjacency matrix instead of a grid.
Feynman coach · Before you peek at the code
Can you explain the core insight in your own words?
If you can explain it before reading code, you’re far more likely to recall it under interview pressure.
Loading your attempt…
Reference Implementation
C++ Solution for LeetCode 1905
1class Solution {
2public:
3 int m, n;
4
5 // DFS returns true if the connected component is a valid sub-island
6 bool dfs(vector<vector<int>>& grid1, vector<vector<int>>& grid2, int r, int c) {
7 // Boundary checks and water check
8 if (r < 0 || r >= m || c < 0 || c >= n || grid2[r][c] == 0) {
9 return true;
10 }
11
12 // Mark as visited in grid2 to avoid cycles and recounting
13 grid2[r][c] = 0;
14
15 // Check validity for the current cell
16 bool isSub = (grid1[r][c] == 1);
17
18 // Recurse in all 4 directions.
19 // IMPORTANT: We must NOT use short-circuit operators (&&).
20 // We need to traverse the entire island to mark all cells as visited.
21 bool up = dfs(grid1, grid2, r - 1, c);
22 bool down = dfs(grid1, grid2, r + 1, c);
23 bool left = dfs(grid1, grid2, r, c - 1);
24 bool right = dfs(grid1, grid2, r, c + 1);
25
26 // The island is valid only if the current cell is valid AND all parts are valid
27 return isSub && up && down && left && right;
28 }
29
30 int countSubIslands(vector<vector<int>>& grid1, vector<vector<int>>& grid2) {
31 m = grid1.size();
32 n = grid1[0].size();
33 int count = 0;
34
35 for (int i = 0; i < m; i++) {
36 for (int j = 0; j < n; j++) {
37 // If we find an unvisited land cell in grid2
38 if (grid2[i][j] == 1) {
39 if (dfs(grid1, grid2, i, j)) {
40 count++;
41 }
42 }
43 }
44 }
45 return count;
46 }
47};Java Solution for LeetCode 1905
1class Solution {
2 private int m;
3 private int n;
4
5 public int countSubIslands(int[][] grid1, int[][] grid2) {
6 m = grid1.length;
7 n = grid1[0].length;
8 int count = 0;
9
10 for (int i = 0; i < m; i++) {
11 for (int j = 0; j < n; j++) {
12 // Start DFS if we find unvisited land in grid2
13 if (grid2[i][j] == 1) {
14 // If the entire island is valid, increment count
15 if (dfs(grid1, grid2, i, j)) {
16 count++;
17 }
18 }
19 }
20 }
21 return count;
22 }
23
24 private boolean dfs(int[][] grid1, int[][] grid2, int r, int c) {
25 // Base case: check boundaries or if cell is water/visited
26 if (r < 0 || r >= m || c < 0 || c >= n || grid2[r][c] == 0) {
27 return true;
28 }
29
30 // Mark current cell as visited
31 grid2[r][c] = 0;
32
33 // Determine if current cell is valid (must be land in grid1)
34 boolean isCurrentValid = (grid1[r][c] == 1);
35
36 // Visit all neighbors.
37 // We use bitwise AND (&) or separate boolean variables to ensure
38 // DFS executes for ALL directions. Logical AND (&&) would short-circuit.
39 boolean up = dfs(grid1, grid2, r - 1, c);
40 boolean down = dfs(grid1, grid2, r + 1, c);
41 boolean left = dfs(grid1, grid2, r, c - 1);
42 boolean right = dfs(grid1, grid2, r, c + 1);
43
44 return isCurrentValid && up && down && left && right;
45 }
46}Python Solution for LeetCode 1905
1class Solution:
2 def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:
3 m, n = len(grid1), len(grid1[0])
4
5 def dfs(r, c):
6 # Base case: out of bounds or water/visited
7 if r < 0 or r >= m or c < 0 or c >= n or grid2[r][c] == 0:
8 return True
9
10 # Mark as visited
11 grid2[r][c] = 0
12
13 # Check if this cell is valid (must be land in grid1)
14 is_valid = (grid1[r][c] == 1)
15
16 # Recurse all 4 directions
17 # We must execute all DFS calls to ensure the whole island is marked visited.
18 res1 = dfs(r + 1, c)
19 res2 = dfs(r - 1, c)
20 res3 = dfs(r, c + 1)
21 res4 = dfs(r, c - 1)
22
23 # Return True only if current cell and all connected parts are valid
24 return is_valid and res1 and res2 and res3 and res4
25
26 count = 0
27 for i in range(m):
28 for j in range(n):
29 if grid2[i][j] == 1:
30 if dfs(i, j):
31 count += 1
32
33 return count