⚡Flashcard Drill➔
NeetCode #613LC-305HardGraphsNC Algo100
← Back to All Problems

#613 · #305 · Number of Islands II(岛屿数量 II)

📌 Problem Statement & Constraints

You are given m, n and a list of positions where land is added one cell at a time. After each addition, return the number of islands. Constraints: 1 <= m, n <= 10^4, 1 <= positions.length <= 10^4, 1 <= m * n <= 10^4.

💡 Core Algorithmic Approaches

  1. Adding land merges islands, so union-find is the natural incremental structure.
  2. When a cell is added, it starts as a new island (count + 1).
  3. For each of its four already-land neighbours, union them; each successful union decrements the count.
  4. Duplicate positions in the input must be ignored.

💻 Benchmark Python3 Implementation

class Solution:
    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:
        parent = {}

        def find(x):
            while parent[x] != x:
                parent[x] = parent[parent[x]]   # path halving
                x = parent[x]
            return x

        count = 0
        res = []
        for r, c in positions:
            if (r, c) in parent:           # already land -> no change
                res.append(count)
                continue
            parent[(r, c)] = (r, c)        # new island
            count += 1
            for dr, dc in ((0, 1), (0, -1), (1, 0), (-1, 0)):
                nb = (r + dr, c + dc)
                if nb in parent:
                    ra, rb = find((r, c)), find(nb)
                    if ra != rb:           # merge two islands
                        parent[ra] = rb
                        count -= 1
            res.append(count)
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(k * alpha(k)) where k is the number of positions.
💾 Space Complexity
O(k) for the union-find map.

⚠️ Interview Pitfalls & Follow-ups

  • Recomputing the island count with a full BFS per query: O(k * m * n).
  • Forgetting the duplicate-position case: the count must not change.
  • Incrementing the count before the neighbour merges: the order does not matter, but the count must start at +1 for the new cell.
  • Using a 2D parent array of size m*n: it works when m*n <= 10^4, but a dict keyed by coordinate is more flexible.
⚡
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