⚡Flashcard Drill➔
NeetCode #568LC-1905MediumGraphs
← Back to All Problems

#568 · #1905 · Count Sub Islands(统计子岛屿)

📌 Problem Statement & Constraints

You are given two m x n binary grids grid1 and grid2. An island in grid2 is a sub-island if all of its cells are also land in grid1. Return the number of sub-islands in grid2. Constraints: 1 <= m, n <= 500.

💡 Core Algorithmic Approaches

  1. Flood-fill each island of grid2, and track whether every cell of it is land in grid1.
  2. The DFS returns a boolean: True only if this cell and all its connected cells are land in grid1.
  3. Do not short-circuit the four recursive calls -- all cells must be visited so they are not counted again as a separate island.
  4. Count the islands whose DFS returns True.

💻 Benchmark Python3 Implementation

class Solution:
    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:
        m, n = len(grid1), len(grid1[0])

        def dfs(r: int, c: int) -> bool:
            if not (0 <= r < m and 0 <= c < n) or grid2[r][c] == 0:
                return True                # nothing here, no constraint violated
            grid2[r][c] = 0                # mark visited
            ok = grid1[r][c] == 1          # this cell must be land in grid1
            # evaluate ALL four so the whole island is consumed
            for dr, dc in ((0, 1), (0, -1), (1, 0), (-1, 0)):
                if not dfs(r + dr, c + dc):
                    ok = False
            return ok

        count = 0
        for i in range(m):
            for j in range(n):
                if grid2[i][j] == 1 and dfs(i, j):
                    count += 1
        return count

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(m * n): each cell is visited once.
💾 Space Complexity
O(m * n) for the recursion stack.

⚠️ Interview Pitfalls & Follow-ups

  • Short-circuiting the four recursive calls with and: the rest of the island would remain unmarked and be counted again.
  • Returning True for out-of-bounds: correct here -- it means the island did not extend outside, which imposes no constraint.
  • Checking only the starting cell against grid1: every cell of the island must be land in grid1.
  • Marking visited only when the check passes: all cells must be marked regardless.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Graphs Problems