# Count Sub Islands
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/count-sub-islands)
Canonical: https://scaleengineer.com/dsa/problems/count-sub-islands
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search), [Union Find](https://scaleengineer.com/algorithms/union-find)
**Data structures:** Array, Matrix
**Companies:** [DoorDash](https://scaleengineer.com/companies/doordash), [Zepto](https://scaleengineer.com/companies/zepto), [X](https://scaleengineer.com/companies/x)
---
## Problem
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:**

![](https://assets.glich.co/dsa/count-sub-islands/image0.png) 

**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:**

![](https://assets.glich.co/dsa/count-sub-islands/image1.png) 

**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.length`
* `n == grid1[i].length == grid2[i].length`
* `1 <= m, n <= 500`
* `grid1[i][j]` and `grid2[i][j]` are either `0` or `1`.

# Approaches
## Filter and Count using DFS
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 `1`s to `0`s. 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`.
**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.
**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 `visited` matrix.
**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.
### Explanation
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.

```java
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);
    }
}
```
### Algorithm
1. **Filtering Phase:**
   - Iterate through each cell `(r, c)` of `grid2`.
   - If a cell is land in `grid2` but water in `grid1` (i.e., `grid2[r][c] == 1` and `grid1[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 `1`s to `0`s. This effectively removes all non-sub-islands from `grid2`.
2. **Counting Phase:**
   - After the filtering phase, `grid2` only contains land cells that form valid sub-islands.
   - Initialize a counter `sub_island_count` to 0.
   - Iterate through each cell `(r, c)` of the now-modified `grid2`.
   - 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.
3. **Return Result:**
   - Return `sub_island_count`.

## Integrated Traversal and Validation using DFS
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 `1`s to `0`s) during the traversal to prevent recounting.
**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.
**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.
### Explanation
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] = 0` to 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.

```java
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;
    }
}
```
### Algorithm
1. Initialize `sub_island_count` to 0.
2. Iterate through each cell `(r, c)` of `grid2`.
3. If `grid2[r][c]` is `1`, it marks the potential start of a new island. We must determine if this island is a sub-island.
4. Call a recursive helper function, say `isSubIslandDFS(r, c)`, which will traverse the entire island starting from `(r, c)`.
5. This `isSubIslandDFS` function will:
   a. Serve as a standard DFS to explore the island. It will change the `1`s in `grid2` to `0`s to "sink" the island, effectively marking it as visited.
   b. For each cell `(i, j)` it visits, it checks if the corresponding cell `grid1[i][j]` is also land (`1`).
   c. It returns a boolean value. It returns `true` only if the current cell and all recursively explored cells of the island are valid (i.e., correspond to land in `grid1`). Otherwise, it returns `false`.
6. Back in the main loop, if the call to `isSubIslandDFS(r, c)` returns `true`, it means the entire island just processed was a valid sub-island. Increment `sub_island_count`.
7. After iterating through all cells, return `sub_island_count`.

# Solutions
### Java

```java
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;
  }
}

```

### JavaScript

```javascript
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 ; }
```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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])

```