Coding Interview PatternsNumber of Islands II
HardUnion Find

Number of Islands II

Explanation & Solution

Practice Problem

Description

You are given an empty 2D binary grid of size m x n. The grid represents a map where 0s represent water and 1s represent land. Initially, all the cells of the grid are water cells (i.e., all cells are 0s).

We may perform an addLand operation which turns the water at position into a land. You are given an array positions where positions[i] = [ri, ci] is the position (ri, ci) at which we should operate the ith addLand operation.

Return an array of integers answer where answer[i] is the number of islands after turning the cell (ri, ci) into a land.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically.

Input: m = 3, n = 3, positions = [[0,0],[0,1],[1,2],[2,1]]

Output:[1,1,2,3]
0
1
1
1
2
2
3
3

Explanation:

  • Add land at (0,0): 1 island
  • Add land at (0,1): still 1 island (connected to (0,0))
  • Add land at (1,2): 2 islands (not connected to others)
  • Add land at (2,1): 3 islands

Constraints

  • 1 <= m, n, positions.length <= 10^4
  • 1 <= m * n <= 10^4
  • positions[i].length == 2
  • 0 <= ri < m
  • 0 <= ci < n

Approach

Union Find pattern

1. Initialize Grid as Water

  • Create parent array of size m * n, all set to -1 (water)
  • -1 means the cell hasn't been turned to land yet
  • Track island count starting at 0

2. Process Each AddLand Operation

  • For position [r, c], compute flat index idx = r * n + c
  • If already land (parent[idx] !== -1), skip and push current count
  • Otherwise, set parent[idx] = idx (new island) and increment count

3. Union with Adjacent Land Cells

  • Check all 4 neighbors (up, down, left, right)
  • If a neighbor is within bounds and is land (parent !== -1), union it with the new cell
  • Each successful union decrements count (two islands merge into one)

4. Record Island Count

  • After processing each position, push current count to the result array

Key Insight

  • Union Find perfectly handles dynamic connectivity — each addLand either creates a new island or merges with existing ones
  • Handling duplicate positions (adding land where land already exists) is important
Time
**O(k · α(m·n))** where k is the number of positions
Space
O(m · n)

Solution Code

Previous
Redundant Connection II
Next
Making a Large Island