Count Sub Islands — The AND Logic DFS Mistake Everyone Makes

Problem Statement#

You are given two m x n binary matrices grid1 and grid2. An island is a group of 1s connected 4-directionally surrounded by 0s (or the boundary). 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 sub-islands in grid2.

Constraints:

• m == grid1.length == grid2.length
• n == grid1[0].length == grid2[0].length
• 1 <= m, n <= 500
• grid1[i][j] and grid2[i][j] are 0 or 1

Example 1:

grid1:           grid2:
1  1  1  0  0   1  1  1  0  0
0  1  1  1  1   0  0  1  1  1
0  0  0  0  0   0  1  0  0  0
1  0  0  0  0   0  1  0  0  0
1  1  0  1  1   1  1  0  1  1
 
Output: 3
Explanation: Three islands in grid2 are sub-islands of grid1.

Example 2:

grid1:           grid2:
1  0  1  0  1   0  0  1  1  1
1  1  1  1  1   0  0  0  0  1
0  0  0  0  0   0  0  0  1  1
1  1  0  1  1   0  1  0  1  0
 
Output: 2

Example 3:

grid1:   grid2:
1  1     1  0
1  0     1  1
 
Output: 1
Explanation: The island in grid2 at (0,0),(1,0) is a sub-island because
             grid1 has land at both those positions.
             (1,1) in grid2 is land but grid1 has 0 there, so the island
             containing (1,1) alone is not a sub-island.

Why This Problem Matters#

Count Sub Islands is a favorite at Amazon and Facebook because it combines two concepts: connected component traversal and a multi-condition validity check. Straightforward flood fill just identifies islands; this problem requires that each island in grid2 passes an additional test against grid1. The challenge is that the test is AND-logic across the entire island: every single cell of the island in grid2 must also be land in grid1.

The critical interviewer trap is the temptation to short-circuit: if one cell in grid2's island has grid1[r][c] == 0, you might think you can return false immediately and stop the DFS. That is wrong. Stopping early leaves the remaining cells of the island unvisited, so they will be counted again as new islands in future iterations. You must always finish the full DFS traversal of the island (to mark it as visited), while tracking the validity result separately.

This problem also builds on LC 200 (Number of Islands) and directly precedes LC 827 (Making a Large Island). Mastering the "complete DFS but track boolean" idiom here prepares you for any island problem with a compound validity condition.

The Core Insight#

For each unvisited land cell in grid2, start a DFS that:

1. Marks every cell in the island as visited (set grid2[r][c] = 0).
2. Simultaneously checks if every visited cell also has grid1[r][c] == 1.
3. Returns True only if all cells pass the check.

The key implementation detail: the DFS must recurse into all four directions regardless of whether the current cell fails the grid1 check. You want to discover and mark all cells belonging to this island before returning. Collect the AND of all per-cell checks across the whole island, then return the combined result.

One clean way to implement this: make the DFS return a boolean per call. Use is_valid = dfs(r+1, c) and ... — but be careful, Python and short-circuits. The safer pattern is to collect results with bitwise AND or to run all four recursive calls first, then AND the results.

Visual Dry Run#

grid1:        grid2:
1  1  1       1  1  0
0  1  0       0  1  0
0  0  1       0  0  1

Islands in grid2:

• Island A: (0,0), (0,1), (1,1) — connected component starting at (0,0)
• Island B: (2,2) — single cell

Check Island A:

• (0,0): grid1=1 ✓
• (0,1): grid1=1 ✓
• (1,1): grid1=1 ✓
• All cells valid → Island A is a sub-island

Check Island B:

• (2,2): grid1=1 ✓
• All cells valid → Island B is a sub-island

Total: 2 sub-islands.

Now suppose grid1[2][2] = 0. Then Island B fails the check (grid1 has sea where grid2 has land) → not a sub-island. Answer = 1.

Common Mistakes#

1. Short-circuiting DFS when a cell is invalid. If you write if grid1[r][c] == 0: return False without recursing further, the remaining cells of the island in grid2 stay marked as 1. They will be picked up as a "new island" in the outer loop, causing double-counting. Always recurse fully; track validity separately.

2. Using Python's short-circuit and in recursive DFS. return dfs(r+1,c) and dfs(r-1,c) and dfs(r,c+1) and dfs(r,c-1) — if the first call returns False, Python skips the remaining three calls. Those cells remain unvisited. Use the pattern: run all four calls and collect results, then combine.

3. Checking grid1 before the bounds/visited check. Always check bounds and whether grid2[r][c] == 1 before accessing grid1[r][c]. Accessing grid1 with out-of-bounds indices throws an exception.

4. Forgetting that the outer loop should also skip cells already set to 0. After flood-filling an island in grid2 (setting all its cells to 0), those cells must not be re-entered. The condition if grid2[r][c] == 1 in the outer loop naturally handles this, but make sure you check grid2, not grid1.

5. Comparing island shapes instead of cell membership. A common misunderstanding: the problem does not require that the sub-island has the same shape as any island in grid1. It only requires that each cell of the grid2 island is land in grid1. The grid1 island may be larger.

6. Treating diagonal neighbors as connected. Both grids use 4-directional connectivity (up, down, left, right). Diagonal neighbors do not count as connected.

Solutions#

Python#

def countSubIslands(grid1: list[list[int]], grid2: list[list[int]]) -> int:
    ROWS, COLS = len(grid2), len(grid2[0])
 
    def dfs(r: int, c: int) -> bool:
        # Base case: out of bounds or sea cell in grid2 — not part of current island
        if r < 0 or r >= ROWS or c < 0 or c >= COLS or grid2[r][c] != 1:
            return True  # no constraint violation from this direction
 
        # Mark this cell visited by sinking it in grid2
        grid2[r][c] = 0
 
        # Check if this cell is also land in grid1
        is_sub = (grid1[r][c] == 1)
 
        # CRITICAL: recurse into ALL four directions first, collect results
        # Do NOT short-circuit — every neighbor must be visited to mark island fully
        down  = dfs(r + 1, c)
        up    = dfs(r - 1, c)
        right = dfs(r, c + 1)
        left  = dfs(r, c - 1)
 
        # Island is a sub-island only if ALL cells pass the grid1 check
        return is_sub and down and up and right and left
 
    count = 0
    for r in range(ROWS):
        for c in range(COLS):
            if grid2[r][c] == 1:              # found an unvisited island in grid2
                if dfs(r, c):                 # check if the whole island is a sub-island
                    count += 1
    return count

JavaScript#

var countSubIslands = function(grid1, grid2) {
    const ROWS = grid2.length;
    const COLS = grid2[0].length;
 
    // DFS marks the full island in grid2 and returns whether it is a sub-island
    function dfs(r, c) {
        // Base case: out of bounds or not a land cell in grid2
        if (r < 0 || r >= ROWS || c < 0 || c >= COLS || grid2[r][c] !== 1) {
            return true;  // no invalid cell found from this direction
        }
 
        // Sink this cell in grid2 to mark it visited
        grid2[r][c] = 0;
 
        // Check if the corresponding cell in grid1 is also land
        const isSub = grid1[r][c] === 1;
 
        // CRITICAL: run all four recursive calls before combining results
        // JavaScript uses short-circuit evaluation — store results in variables
        const down  = dfs(r + 1, c);
        const up    = dfs(r - 1, c);
        const right = dfs(r, c + 1);
        const left  = dfs(r, c - 1);
 
        // Valid sub-island only if current cell and all neighbor results are valid
        return isSub && down && up && right && left;
    }
 
    let count = 0;
    for (let r = 0; r < ROWS; r++) {
        for (let c = 0; c < COLS; c++) {
            if (grid2[r][c] === 1) {      // unvisited island in grid2
                if (dfs(r, c)) count++;   // check sub-island validity
            }
        }
    }
    return count;
};

Complexity Analysis#

Each cell in grid2 is set to 0 the first time it is visited, so it can never be entered again. Total work across all DFS calls is O(m*n). The recursion stack depth can reach O(m*n) in the worst case (a single snake-shaped island). For very large grids, convert to BFS with an explicit queue to avoid stack overflow.

Follow-up Questions#

Q: What if you cannot modify grid2? Use a separate visited = [[False]*COLS for _ in range(ROWS)] boolean matrix. Check visited[r][c] instead of grid2[r][c] == 0. The algorithm is otherwise identical.

Q: How would you count sub-islands if diagonal movement is also allowed? Change the directions list from 4 entries to 8 entries (adding (-1,-1), (-1,1), (1,-1), (1,1)). Everything else stays the same.

Q: What is the hardest variation of this pattern? LC 827 (Making a Large Island) extends this concept to island merging: instead of just checking membership, you color each island with a unique ID, store sizes, and then for each 0 cell, compute the merged size of all neighboring distinct islands.

Q: Can you solve this using Union-Find? Yes, but it is significantly more complex. You would union-find connected components of grid1, assign representative IDs, then for each grid2 island check that all its cells belong to the same grid1 component. DFS/BFS is simpler and equally efficient.

This Pattern Solves#

• LC 200 — Number of Islands (basic island counting)
• LC 695 — Max Area of Island
• LC 827 — Making a Large Island (island coloring + merge)
• LC 1254 — Number of Closed Islands
• LC 130 — Surrounded Regions

Key Takeaways#

• Never short-circuit DFS when a cell fails a validity check — complete the full traversal to mark all cells visited before combining results
• Separate "mark visited" from "check valid": run all four recursive calls first, collect their booleans, then AND them together
• The AND logic for sub-island validity must span the entire island — one invalid cell invalidates the whole island
• Sinking cells (setting to 0) in grid2 prevents double-counting in the outer loop
• Time O(mn), space O(mn) — each cell in grid2 visited at most once
• This pattern generalizes to any island problem where all cells must satisfy a compound condition
• The Python and operator short-circuits — always store recursive results in variables before combining