Number of Islands II

Free with account Updated Nov 19, 2026 · 6 min read
On this page

    Problem statement

    An m × n grid starts as all water. A list of positions turns cells into land, one at a time. After each addition, report the number of islands, where an island is a group of land cells connected horizontally or vertically. A position may be added more than once.

    Number of Islands, but the map keeps changing. Re-running a BFS after every addition is too slow, so this is the textbook use of Union-Find: it answers "how many groups?" while groups keep merging. Original problem: LeetCode 305.

    Example

    Each added cell (red outline) starts a new island or joins existing ones; adding (0,1) merges three islands into one.
    Each added cell (red outline) starts a new island or joins existing ones; adding (0,1) merges three islands into one.
    m = 3, n = 4
    positions = [(0,0), (0,2), (1,1), (0,1), (2,3), (1,2), (0,0)]
    Output:     [  1,     2,     3,     1,     2,     2,     2  ]

    Constraints (assumed)

    • 1 ≤ m, n ≤ 10⁴, but up to 10⁴ positions; the grid can be much larger than the number of land cells.
    • Positions are inside the grid and may repeat.

    What this question tests

    • Recognising incremental connectivity and choosing Union-Find over repeated graph searches.
    • The counting trick: +1 for every new cell, −1 for every union that joins two different sets.
    • Details: duplicate positions, 2D-to-1D indexing, path compression.

    Questions to ask first

    1. Can the same position be added twice? (Here: yes; the count must not change.)
    2. Are diagonals connected? (Here: no, only 4 directions.)
    3. How big is the grid compared with the number of additions? That decides between an array of size m × n and a hash map of land cells.
    4. Can land ever turn back into water? (Here: no. Removals make the problem much harder.)