Count Sub Islands
MedPrompt
You are given two m x n binary matrices grid1 and grid2 containing only 0's (representing water) and 1's (representing land). An island is a group of 1's connected 4-directionally (horizontal or vertical). Any cells outside of the grid are considered water cells.
An island in grid2 is considered a sub-island if there is an island in grid1 that contains all the cells that make up this island in grid2.
Return the number of islands in grid2 that are considered sub-islands.
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: 3
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: 2
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.lengthn == grid1[i].length == grid2[i].length1 <= m, n <= 500grid1[i][j]andgrid2[i][j]are either0or1.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach operates in two main phases: filtering and counting. The core idea is to first clean up grid2 by removing all islands that are definitely not sub-islands. An island in grid2 is not a sub-island if at least one of its land cells corresponds to a water cell in grid1. We can iterate through the grid, and whenever we find such a land cell in grid2, we perform a traversal (like DFS) to find and "sink" its entire island by changing its 1s to 0s. After this filtering process, any remaining islands in grid2 are guaranteed to be sub-islands. The second phase is then a standard island counting algorithm on the modified grid2.
Algorithm
- Filtering Phase:
- Iterate through each cell
(r, c)ofgrid2. - If a cell is land in
grid2but water ingrid1(i.e.,grid2[r][c] == 1andgrid1[r][c] == 0), this cell belongs to an island that cannot be a sub-island. - From this cell, start a Depth First Search (DFS) or Breadth First Search (BFS) to find all connected land cells of this invalid island.
- During the traversal, "sink" the island by changing all its
1s to0s. This effectively removes all non-sub-islands fromgrid2.
- Iterate through each cell
- Counting Phase:
- After the filtering phase,
grid2only contains land cells that form valid sub-islands. - Initialize a counter
sub_island_countto 0. - Iterate through each cell
(r, c)of the now-modifiedgrid2. - If a cell contains a
1, it signifies the start of a valid sub-island.- Increment
sub_island_count. - Start another traversal (DFS or BFS) from
(r, c)to sink this entire island. This is crucial to ensure that we count each island only once.
- Increment
- After the filtering phase,
- Return Result:
- Return
sub_island_count.
- Return
Walkthrough
The implementation uses a helper dfs function to perform the island sinking. This function is used in both phases.
In the first loop, we scan the grids. If grid2[i][j] is land (1) and grid1[i][j] is water (0), we've found a piece of an invalid island. We call dfs(grid2, i, j) to find all connected parts of this island in grid2 and set them to 0.
After this loop completes, grid2 has been cleansed of all invalid islands. The second loop then performs a standard island count. It scans grid2 again. If it finds a land cell (1), it means we've found a valid sub-island. We increment our count and immediately call dfs(grid2, i, j) to sink this island, so its other parts aren't counted again.
class Solution { public int countSubIslands(int[][] grid1, int[][] grid2) { int m = grid1.length; int n = grid1[0].length; // Step 1: Filter out all islands in grid2 that are not sub-islands. for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (grid2[i][j] == 1 && grid1[i][j] == 0) { // This island in grid2 is not a sub-island. Sink it. dfs(grid2, i, j, m, n); } } } // Step 2: Count the remaining islands in grid2. int subIslandCount = 0; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (grid2[i][j] == 1) { subIslandCount++; // Sink this counted island to avoid recounting it. dfs(grid2, i, j, m, n); } } } return subIslandCount; } // Helper DFS function to find and sink an island. private void dfs(int[][] grid, int r, int c, int m, int n) { if (r < 0 || r >= m || c < 0 || c >= n || grid[r][c] == 0) { return; } // Sink the current land cell. grid[r][c] = 0; // Visit all 4-directionally connected neighbors. dfs(grid, r + 1, c, m, n); dfs(grid, r - 1, c, m, n); dfs(grid, r, c + 1, m, n); dfs(grid, r, c - 1, m, n); }}Complexity
Time
O(M*N), where M is the number of rows and N is the number of columns. Each cell in the grid is visited a constant number of times across the two phases of the algorithm. The DFS traversals ensure that each land cell is processed as part of sinking an island exactly once.
Space
O(M*N) in the worst case. This space is used by the recursion stack for the DFS traversal. In the worst-case scenario, the grid could contain a long, snake-like island that fills most of the grid, leading to a recursion depth of up to M*N.
Trade-offs
Pros
Efficient with O(M*N) time complexity.
Logic is clear and easy to follow due to the separation of concerns (filtering then counting).
Space-efficient as it modifies the grid in-place, avoiding the need for an extra
visitedmatrix.
Cons
Modifies the input
grid2, which might not be desirable in some scenarios.Involves two separate passes over the grid, which might be slightly less performant than a single-pass approach, although the asymptotic complexity is the same.
This approach integrates the process of finding an island in grid2 and validating it into a single, efficient traversal. We iterate through grid2, and upon finding a land cell (1) that hasn't been visited, we initiate a Depth First Search (DFS). This DFS has a dual purpose: it explores the entire island to identify all its cells, and for each cell, it checks if the corresponding cell in grid1 is also land. The DFS function is designed to return a boolean value indicating whether the entire island it just traversed is a valid sub-island. If it is, we increment our count. A key part of this approach is to "sink" the island in grid2 (change 1s to 0s) during the traversal to prevent recounting.
Algorithm
- Initialize
sub_island_countto 0. - Iterate through each cell
(r, c)ofgrid2. - If
grid2[r][c]is1, it marks the potential start of a new island. We must determine if this island is a sub-island. - Call a recursive helper function, say
isSubIslandDFS(r, c), which will traverse the entire island starting from(r, c). - This
isSubIslandDFSfunction will: a. Serve as a standard DFS to explore the island. It will change the1s ingrid2to0s to "sink" the island, effectively marking it as visited. b. For each cell(i, j)it visits, it checks if the corresponding cellgrid1[i][j]is also land (1). c. It returns a boolean value. It returnstrueonly if the current cell and all recursively explored cells of the island are valid (i.e., correspond to land ingrid1). Otherwise, it returnsfalse. - Back in the main loop, if the call to
isSubIslandDFS(r, c)returnstrue, it means the entire island just processed was a valid sub-island. Incrementsub_island_count. - After iterating through all cells, return
sub_island_count.
Walkthrough
The main function iterates through grid2. When it finds a 1, it calls a helper DFS function isSubIslandDfs. This helper function returns true if the island starting at that point is a sub-island, and false otherwise.
The isSubIslandDfs function is recursive. For a given cell (r, c):
- It first handles base cases (out of bounds or water in
grid2). - It sinks the current cell
grid2[r][c] = 0to prevent re-visiting. - It checks if the current cell is valid:
isCurrentCellOk = (grid1[r][c] == 1). - It then makes recursive calls for all 4 neighbors.
- Crucially, it combines the results using the bitwise AND operator
&. This ensures that all recursive calls are executed, which is necessary to sink the entire island. If we used the logical AND&&, the traversal would short-circuit and stop upon finding the first invalid cell, leaving the rest of the island intact and causing it to be processed again later. - The final result is the logical AND of the current cell's validity and the results from all its neighbors.
class Solution { public int countSubIslands(int[][] grid1, int[][] grid2) { int m = grid1.length; int n = grid1[0].length; int subIslandCount = 0; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { // If we find a land cell in grid2, check if the entire island is a sub-island. if (grid2[i][j] == 1) { if (isSubIslandDfs(grid1, grid2, i, j, m, n)) { subIslandCount++; } } } } return subIslandCount; } private boolean isSubIslandDfs(int[][] grid1, int[][] grid2, int r, int c, int m, int n) { // Base case for recursion: out of bounds or already water. if (r < 0 || r >= m || c < 0 || c >= n || grid2[r][c] == 0) { return true; } // Sink the island cell in grid2 to mark it as visited. grid2[r][c] = 0; // A sub-island requires the corresponding cell in grid1 to be land. boolean isCurrentCellOk = (grid1[r][c] == 1); // Recursively check all 4 neighbors. Use bitwise AND `&` to prevent short-circuiting. // This ensures the entire island in grid2 is explored and sunk, even if one part fails the check. boolean isNorthOk = isSubIslandDfs(grid1, grid2, r - 1, c, m, n); boolean isSouthOk = isSubIslandDfs(grid1, grid2, r + 1, c, m, n); boolean isWestOk = isSubIslandDfs(grid1, grid2, r, c - 1, m, n); boolean isEastOk = isSubIslandDfs(grid1, grid2, r, c + 1, m, n); return isCurrentCellOk & isNorthOk & isSouthOk & isWestOk & isEastOk; }}Complexity
Time
O(M*N). The main loop iterates through every cell. The DFS function ensures that each land cell in `grid2` is visited exactly once, as it's immediately sunk. Therefore, the total time complexity is proportional to the number of cells in the grid.
Space
O(M*N) in the worst case for the recursion stack. Similar to the other DFS-based approach, a deeply nested recursive path can consume stack space proportional to the number of cells in the grid.
Trade-offs
Pros
Extremely efficient, with optimal O(M*N) time complexity.
Processes each island in a single pass, which can be slightly more performant than a two-pass approach.
Space-efficient by modifying the grid in-place.
Cons
Modifies the input
grid2.The logic within the recursive function can be subtle, especially the need to ensure the entire island is traversed even after a disqualifying condition is found.
Solutions
Solution
class Solution {private final int[] dirs = {-1, 0, 1, 0, -1};private int[][] grid1;private int[][] grid2;private int m;private int n;public int countSubIslands(int[][] grid1, int[][] grid2) { m = grid1.length; n = grid1[0].length; this.grid1 = grid1; this.grid2 = grid2; int ans = 0; for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { if (grid2[i][j] == 1) { ans += dfs(i, j); } } } return ans; }private int dfs(int i, int j) { int ok = grid1[i][j]; grid2[i][j] = 0; for (int k = 0; k < 4; ++k) { int x = i + dirs[k], y = j + dirs[k + 1]; if (x >= 0 && x < m && y >= 0 && y < n && grid2[x][y] == 1) { ok &= dfs(x, y); } } return ok; }}function countSubIslands ( grid1 , grid2 ) { const [ m , n ] = [ grid1 . length , grid1 [ 0 ]. length ]; let ans = 0 ; const dirs = [ - 1 , 0 , 1 , 0 , - 1 ]; const dfs = ( i , j ) => { let ok = grid1 [ i ][ j ]; grid2 [ i ][ j ] = 0 ; for ( let k = 0 ; k < 4 ; ++ k ) { const [ x , y ] = [ i + dirs [ k ], j + dirs [ k + 1 ]]; if ( x >= 0 && x < m && y >= 0 && y < n && grid2 [ x ][ y ]) { ok &= dfs ( x , y ); } } return ok ; }; for ( let i = 0 ; i < m ; ++ i ) { for ( let j = 0 ; j < n ; j ++ ) { if ( grid2 [ i ][ j ]) { ans += dfs ( i , j ); } } } return ans ; }class Solution {public: int countSubIslands(vector<vector<int>> &grid1, vector<vector<int>> &grid2) { int m = grid1.size(), n = grid1[0].size(); int ans = 0; int dirs[5] = {-1, 0, 1, 0, -1}; function<int(int, int)> dfs = [&](int i, int j) { int ok = grid1[i][j]; grid2[i][j] = 0; for (int k = 0; k < 4; ++k) { int x = i + dirs[k], y = j + dirs[k + 1]; if (x >= 0 && x < m && y >= 0 && y < n && grid2[x][y]) { ok &= dfs(x, y); } } return ok; }; for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { if (grid2[i][j]) { ans += dfs(i, j); } } } return ans; }};class Solution: def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int: def dfs(i: int, j: int) -> int: ok = grid1[i][j] grid2[i][j] = 0 for a, b in pairwise(dirs): x, y = i + a, j + b if 0 <= x < m and 0 <= y < n and grid2[x][y] and not dfs(x, y): ok = 0 return ok m, n = len(grid1), len(grid1[0]) dirs = (- 1, 0, 1, 0, - 1) return sum(dfs(i, j) for i in range(m) for j in range(n) if grid2[i][j])Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.