305. Number of Islands II - Detailed Explanation

Problem Statement

You have an m × n grid initially filled with water. You are given a sequence of positions, each a pair [r, c] where you turn the cell (r,c) into land. After each addition, report the total number of connected islands (4‑directionally adjacent groups of land cells).

Input

• Integers m, n
• positions: list of k pairs [r, c] with 0 ≤ r < m, 0 ≤ c < n

Output

• List of k integers, where the _i_th integer is the number of islands after processing positions[i]

Example

m = 3, n = 3
positions = [[0,0],[0,1],[1,2],[2,1]]
Output → [1,1,2,3]

Constraints

• 1 ≤ m, n ≤ 10⁴
• 1 ≤ positions.length ≤ 10⁴
• Positions may repeat (adding land to an already-land cell has no effect)

Hints

• Brute‑force after each addition, run a full DFS/BFS to count islands, but that’s O(m × n) per query.
• Map each cell (r,c) to a 1D index idx = r*n + c.
• Use a Union‑Find structure where each newly added land starts as its own set (increment count), then union with any adjacent lands (decrement count on each successful union).

Brute Force Approach

1. Maintain a grid of water/land.
2. After each addition, run a full DFS/BFS from every unvisited land cell to count connected components.

• Time: O(k × m × n) in worst case
• Space: O(m × n)

Optimized Union‑Find Approach

1. Initialization

   • parent array of size m*n, initialized to -1 (water)
   • rank (or size) array of size m*n, all zeros
   • count = 0

2. addLand(r, c)

   • Compute idx = r*n + c.
   • If parent[idx] != -1, it’s already land → append current count and return.
   • Set parent[idx] = idx, rank[idx] = 1, count++.
   • For each of the four neighbors (r+dr, c+dc) within bounds:
     • Let nidx = nr*n + nc. If parent[nidx] != -1, union(idx, nidx). On each successful union, do count--.
   • Append count to the result list.

3. Union & Find

   • find(x) with path compression
   • union(x, y) by rank/size, return true if two roots were distinct

This yields amortized O(α(m × n)) per operation, effectively O(1).

Step‑by‑Step Walkthrough

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

• Start: all water, count=0

1. Add (0,0) → idx=0
   • parent[0]=0, count=1
   • neighbors water → no unions
     → result=[1]
2. Add (0,1) → idx=1
   • parent[1]=1, count=2
   • neighbor left idx=0 is land → union(1,0): roots differ → merge → count=1
     → result=[1,1]
3. Add (1,2) → idx=1*3+2=5
   • parent[5]=5, count=2
   • no adjacent land → result=[1,1,2]
4. Add (2,1) → idx=2*3+1=7
   • parent[7]=7, count=3
   • neighbor up idx=4 water, left idx=6 water, right idx=8 water, down out
     → result=[1,1,2,3]

Complexity Analysis

• Time: O(k × α(m × n)) ≈ O(k)
• Space: O(m × n) for parent and rank arrays

Code Solutions

Python