Number of Islands II
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

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
- Can the same position be added twice? (Here: yes; the count must not change.)
- Are diagonals connected? (Here: no, only 4 directions.)
- 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.
- Can land ever turn back into water? (Here: no. Removals make the problem much harder.)
Try it yourself first
You have the full problem. Sketch your answer, then sign up free to read the complete walkthrough.
- The complete design, flow by flow, with pictures
- Deep dives into the hard parts
- What mid, senior and staff candidates are expected to say
- Full company question lists
Free forever. No card needed.