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
- Flood-fill each island of
grid2, and track whether every cell of it is land ingrid1. - The DFS returns a boolean:
Trueonly if this cell and all its connected cells are land ingrid1. - Do not short-circuit the four recursive calls -- all cells must be visited so they are not counted again as a separate island.
- 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
Truefor 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 ingrid1. - 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.