305. Number of Islands II

At a Glance

Topic: graphs
Pattern: Union-Find (dynamic connectivity) on a sparse grid
Difficulty: Hard
Companies: Google, Amazon, Bloomberg, LinkedIn, Snap
Frequency: Medium
LeetCode: 305 (Premium)

Start with an m x n all-water grid. For each position in positions, turn it to land and return the island count after each addition (4-directionally connected land cells form one island).

Recognition Cues

Online updates — queries interleaved with structural changes
Count connected components on a growing vertex set—classic DSU
Grid coordinates map to flat ids row * numCols + col

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Loading diagram…

Approaches

BFS/DFS from scratch per query — O(k * m * n) over k operations — too slow.
Union-Find — merge new cell with up to four neighbors if land — amortized ~α(n) per op — optimal.

Optimal Solution

Go

func numIslands2(rows int, cols int, positions [][]int) []int {
	parent := []int{}
	rank := []int{}
	idOf := func(row int, col int) int {
		return row*cols + col
	}
	find := func(node int) int {
		for parent[node] != node {
			parent[node] = parent[parent[node]]
			node = parent[node]
		}
		return node
	}
	union := func(left int, right int) bool {
		leftRoot := find(left)
		rightRoot := find(right)
		if leftRoot == rightRoot {
			return false
		}
		if rank[leftRoot] < rank[rightRoot] {
			leftRoot, rightRoot = rightRoot, leftRoot
		}
		parent[rightRoot] = leftRoot
		if rank[leftRoot] == rank[rightRoot] {
			rank[leftRoot]++
		}
		return true
	}
	land := map[int]bool{}
	answers := make([]int, 0, len(positions))
	componentCount := 0
	directions := [][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
	for _, position := range positions {
		row := position[0]
		col := position[1]
		cellId := idOf(row, col)
		for cellId >= len(parent) {
			parent = append(parent, len(parent))
			rank = append(rank, 0)
		}
		if land[cellId] {
			answers = append(answers, componentCount)
			continue
		}
		land[cellId] = true
		componentCount++
		for _, direction := range directions {
			nextRow := row + direction[0]
			nextCol := col + direction[1]
			if nextRow < 0 || nextRow >= rows || nextCol < 0 || nextCol >= cols {
				continue
			}
			neighborId := idOf(nextRow, nextCol)
			if !land[neighborId] {
				continue
			}
			if union(cellId, neighborId) {
				componentCount--
			}
		}
		answers = append(answers, componentCount)
	}
	return answers
}

JavaScript

function numIslands2(rows, cols, positions) {
  const parent = [];
  const rank = [];
  const land = new Set();
  const idOf = (row, col) => row * cols + col;
  function find(node) {
    if (parent[node] !== node) {
      parent[node] = find(parent[node]);
    }
    return parent[node];
  }
  function union(left, right) {
    let leftRoot = find(left);
    let rightRoot = find(right);
    if (leftRoot === rightRoot) {
      return false;
    }
    if (rank[leftRoot] < rank[rightRoot]) {
      [leftRoot, rightRoot] = [rightRoot, leftRoot];
    }
    parent[rightRoot] = leftRoot;
    if (rank[leftRoot] === rank[rightRoot]) {
      rank[leftRoot] += 1;
    }
    return true;
  }
  function ensureNode(node) {
    while (parent.length <= node) {
      const index = parent.length;
      parent.push(index);
      rank.push(0);
    }
  }
  const answers = [];
  let componentCount = 0;
  const directions = [
    [1, 0],
    [-1, 0],
    [0, 1],
    [0, -1],
  ];
  for (const position of positions) {
    const row = position[0];
    const col = position[1];
    const cellId = idOf(row, col);
    ensureNode(cellId);
    if (land.has(cellId)) {
      answers.push(componentCount);
      continue;
    }
    land.add(cellId);
    componentCount += 1;
    for (const direction of directions) {
      const nextRow = row + direction[0];
      const nextCol = col + direction[1];
      if (nextRow < 0 || nextRow >= rows || nextCol < 0 || nextCol >= cols) {
        continue;
      }
      const neighborId = idOf(nextRow, nextCol);
      if (!land.has(neighborId)) {
        continue;
      }
      ensureNode(neighborId);
      if (union(cellId, neighborId)) {
        componentCount -= 1;
      }
    }
    answers.push(componentCount);
  }
  return answers;
}

Walkthrough

2x2, positions (0,0), (1,1), (1,0): after first land count 1; second disjoint count 2; third touches (1,1) merges one pair → count 1.

Invariant: componentCount equals number of DSU roots among activated land cells after unions.

Edge Cases

Duplicate position — count unchanged
Single cell grid — always 1 after first add
Snake additions — union chains decrement count correctly

Pitfalls

Lazy DSU sizing — ensure parent length covers max flat id
Forgetting to increment count before unions on new land
Using grid-wide BFS each time — time limit on large m*n

Variants

Removals — dynamic connectivity harder; need Euler tour trees / LCT (rare in interviews).
8-connectivity — add diagonal neighbor ids to union loop.
3D volume — id mapping z * rows * cols + row * cols + col.

Mind-Map Tags

#union-find #dynamic-connectivity #grid-dsu #online-query #component-count