← DSA Atlas
Dedicated problem page · #305

Number of Islands II

HardUnion-Find / Disjoint Set UnionIncremental connectivityUnion-Find with a running component count
Solve on LeetCode ↗
305
HardUnion-Find / Disjoint Set UnionUnion-Find with a running component countIncremental connectivity

Number of Islands II

Given an m x n grid initially all water (0), you perform a sequence of addLand operations at positions[i] = [r, c], turning that cell into land (1). After each operation, report the current number of islands, where an island is a group of land cells connected 4-directionally. Return the list of counts, one per operation.

Open official problem prompt ↗
In plain English

Maintain the number of connected land components as land cells are added one by one, answering after each addition.

Picture it like this

Think of lighting up tiles on a floor one at a time. Each new lit tile is a fresh puddle of light; wherever it touches an already-lit neighbor, two puddles merge into one.

Example
Input
m = 3, n = 3, positions = [[0,0],[0,1],[1,2],[2,1]]
Output
[1,1,2,3]
Why
Add (0,0): 1 island. Add (0,1): merges with (0,0), still 1. Add (1,2): isolated, 2 islands. Add (2,1): isolated, 3 islands.
Constraints
1 <= m, n, positions.length <= 10^41 <= m * n <= 10^4positions[i].length == 20 <= ri < m0 <= ci < n
Pattern lesson

See the pattern, then code

Incremental connectivity
Recognition clue

Land appears one cell at a time and you must report connectivity after every insertion. Growing-only connectivity with per-step queries is the classic dynamic Union-Find setting.

↗
Union-Find / Disjoint Set Union

Dynamic connectivity, merging groups, redundant edges, or Kruskal's algorithm.. Each new land cell starts as its own island (increment the count), then for every already-land 4-neighbor whose set differs, union them and decrement the count. The count only changes by these local merges.

New words, made simpleKnow these before the algorithm
Dynamic connectivity
Maintaining group structure while edges/nodes are added incrementally.
Component count
The number of distinct connected groups, updated by +1 on insertion and -1 per successful merge.
Cell key
A (row, col) tuple used as the Union-Find element instead of a flattened integer id.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Full BFS/DFS recount each step

Recomputes everything each step; far too slow for 10^4 operations.

After every addLand, scan the whole grid and count islands from scratch.

Time O(L * m * n)Space O(m*n)
Best choiceIncremental Union-Find

Only touches the new cell and its four neighbors per step.

Add the new cell as a component, then merge with existing land neighbors, adjusting a running count.

Time O(L α(L))Space O(L)
The rule we keep true

Invariant

After processing each operation, count equals the number of distinct roots among all land cells added so far.

Why this is correct

Reasoning

Adding an isolated cell increases components by exactly one. Each distinct land neighbor that is currently in a different component reduces the component count by exactly one when merged. Since only the new cell's adjacencies can change connectivity, updating count locally keeps it exact.

The algorithm in three movesSay these aloud before coding
1Track a parent map over land cells and a running island count

add (0,0): count=1 -> [1]

2On addLand, if the cell is already land record the current count and skip

add (0,1): neighbor (0,0), union, count=1 -> [1,1]

3Add the cell as a new set and increment count

add (1,2): no land neighbor, count=2 -> [1,1,2]

4For each land neighbor with a different root, union and decrement count

add (2,1): no land neighbor, count=3 -> [1,1,2,3]

5Append the count after processing the cell

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
(0,0)0
(0,1)1
(1,2)2
(2,1)3
1 · Readr=0,c=0
2 · AskAny land neighbor?
3 · Update stateparent={(0,0)}, count=1
4 · ResultNo neighbors, append 1
Key takeaway

Adding (0,1) with left neighbor (0,0) already land triggers one merge, keeping the count at 1.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 3-5State

    A parent map keyed by cell, a running island count, and the result list.

  2. 2
    Lines 12-14Duplicate guard

    If the same position is added again it is already land, so report the unchanged count and skip.

  3. 3
    Lines 15-16New component

    Register the cell as its own root and bump the count before checking neighbors.

  4. 4
    Lines 17-23Merge neighbors

    For each of the four directions, if the neighbor is land and in a different set, union and decrement.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • Repeated position in the input must not double-count (guarded by the membership check)
  • A cell surrounded by land on all four sides can merge up to four separate components in one step
  • A 1x1 grid where the only cell is added
!

Common beginner mistakes

  • Incrementing count for a duplicate position that is already land
  • Decrementing count when a neighbor is already in the same set (must compare roots first)
  • Treating a diagonal cell as a neighbor; only 4-directional adjacency connects islands
Check your understanding

Why must you compare roots before decrementing the count when a neighbor is land?

More in Union-Find / Disjoint Set Union

#684Redundant ConnectionCycle detection while building#721Accounts MergeMerge by shared key#947Most Stones Removed with Same Row or ColumnConnected components, keep one per group#952Largest Component Size by Common FactorUnion by prime factors#990Satisfiability of Equality EquationsEquality classes then contradiction check#1319Number of Operations to Make Network ConnectedCount components, connect with spare edges