Union-Find (Disjoint Set)

The one question it answers, and why BFS isn't good enough

You already know how to find connected components with BFS or DFS: one sweep, O(V + E). That works when the graph is fixed. Union-Find exists for the other case — when edges keep arriving and you have to answer "are u and v connected?" interleaved with "now connect u and v." Re-running DFS after every edge is O(E) per query; union-find answers both operations in effectively O(1), amortized, forever.

The representation is a forest: every element points at a parent, and the root of each tree is that set's canonical name. Two elements are in the same set exactly when they reach the same root. That's the entire data structure — an array of integers.

The naive version, so you can see what breaks

class NaiveDSU {
  constructor(n) {
    this.parent = Array.from({ length: n }, (_, i) => i); // everyone starts as their own root
  }

  find(x) {
    while (this.parent[x] !== x) x = this.parent[x]; // walk up to the root
    return x;
  }

  union(a, b) {
    const ra = this.find(a), rb = this.find(b);
    if (ra === rb) return false;  // already together — the return value is the useful part
    this.parent[ra] = rb;         // hang one root under the other, arbitrarily
    return true;
  }
}

This is correct and it is also a trap: union(0,1), union(1,2), union(2,3), … builds a single chain of length n, and every find then costs O(n). The two optimizations below exist purely to make the trees short — they do not change what the structure means.

The two optimizations that change the complexity class

Path compression — while walking to the root, re-point everything you passed directly at the root. You already paid to walk the path; flattening it is free.

// recursive, two-pass: the clean version to write on a whiteboard
find(x) {
  if (this.parent[x] !== x) {
    this.parent[x] = this.find(this.parent[x]); // re-parent on the way back down
  }
  return this.parent[x];
}

// iterative, no stack depth risk — prefer this for n in the hundreds of thousands
find(x) {
  let root = x;
  while (this.parent[root] !== root) root = this.parent[root];
  while (this.parent[x] !== root) {        // second pass: hook every node on the path to root
    const next = this.parent[x];
    this.parent[x] = root;
    x = next;
  }
  return root;
}

Union by size (or rank) — when merging, always hang the smaller tree under the larger root. A node's depth only increases when its tree is absorbed by one at least as big, so a node can be pushed down at most log n times before its tree contains all n elements. That alone caps height at O(log n), even with no path compression at all.

union(a, b) {
  let ra = this.find(a), rb = this.find(b);
  if (ra === rb) return false;
  if (this.size[ra] < this.size[rb]) [ra, rb] = [rb, ra]; // ra is now the LARGER root
  this.parent[rb] = ra;
  this.size[ra] += this.size[rb];
  return true;
}

The production DSU — memorize this one

class DSU {
  constructor(n) {
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.size = new Array(n).fill(1);
    this.components = n; // every successful union drops this by exactly one
  }

  find(x) {
    let root = x;
    while (this.parent[root] !== root) root = this.parent[root];
    while (this.parent[x] !== root) {
      const next = this.parent[x];
      this.parent[x] = root;
      x = next;
    }
    return root;
  }

  union(a, b) {
    let ra = this.find(a), rb = this.find(b);
    if (ra === rb) return false;                       // false === "these were already connected"
    if (this.size[ra] < this.size[rb]) [ra, rb] = [rb, ra];
    this.parent[rb] = ra;
    this.size[ra] += this.size[rb];
    this.components--;
    return true;
  }

  connected(a, b) { return this.find(a) === this.find(b); }
  setSize(x) { return this.size[this.find(x)]; }        // size is only meaningful at a root
}

Dry run: union(0,1), union(1,2), union(3,4), union(2,3), then find(4) — the demo above

Step 4's internal find(2) and find(3) calls rewrite nothing — 2 already points straight at root 0 from step 2's compression, and 3 is still its own root — so union by size alone is doing the shrinking there. Step 5 is the only line that triggers path compression: find(4) walks 4 → 3 → 0 to locate the root, then its second pass re-points parent[4] straight at 0, exactly the flattening the demo above shows.

Three details earn their keep in interviews: union returning a boolean (that single value solves cycle detection and Redundant Connection), the components counter (solves "number of provinces" with no extra pass), and setSize going through find first (reading size[x] on a non-root is stale garbage).

Why the combination is nearly O(1) — the intuition

With both optimizations, m operations on n elements cost O(m · α(n)), where α is the inverse Ackermann function. You don't need the proof, you need the shape of the argument and a number.

• Union by size alone caps tree height at log n: a node only gets deeper when its tree is swallowed by one at least as large, so its containing set at least doubles each time — that can happen at most log₂ n times.
• Path compression alone means each expensive walk permanently destroys the structure that made it expensive. You cannot pay for the same long path twice; the cost amortizes across the sequence of operations, not per operation.
• Together, the trees flatten faster than they can grow. The rigorous bound is α(n), the inverse of a function that grows so violently that α(n) ≤ 4 for any n you can physically store — n = 2⁶⁵⁵³⁶ still gives α = 5.

Number of connected components — the counter does the work

// LeetCode "Number of Connected Components in an Undirected Graph" / "Number of Provinces"
function countComponents(n, edges) {
  const dsu = new DSU(n);
  for (const [u, v] of edges) dsu.union(u, v);
  return dsu.components;
}

// Same idea on an adjacency MATRIX (Number of Provinces) — only scan the upper triangle
function findCircleNum(isConnected) {
  const n = isConnected.length;
  const dsu = new DSU(n);
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      if (isConnected[i][j] === 1) dsu.union(i, j);
    }
  }
  return dsu.components;
}

A grid problem like "Number of Islands" can be done this way too — map cell (r, c) to index r * cols + c and union each land cell with its right and down neighbours only (left/up are covered by the other cell's turn). BFS is simpler there and equally fast; reach for DSU on grids when the islands change, as in "Number of Islands II," where each added land cell is one union and the running count is free.

Cycle detection and Redundant Connection

In an undirected graph, an edge (u, v) closes a cycle exactly when u and v are already in the same set. That is precisely the case where union returns false — so cycle detection is one if.

// Does this undirected edge list contain a cycle?
function hasCycle(n, edges) {
  const dsu = new DSU(n);
  for (const [u, v] of edges) {
    if (!dsu.union(u, v)) return true; // both endpoints already connected → this edge closes a loop
  }
  return false;
}

// Redundant Connection: n nodes, n edges, 1-indexed. Return the LAST edge that creates a cycle.
function findRedundantConnection(edges) {
  const dsu = new DSU(edges.length + 1); // +1 because nodes are 1-indexed; slot 0 is unused
  for (const [u, v] of edges) {
    if (!dsu.union(u, v)) return [u, v]; // edges are given in order, so the first failure IS the last-added cycle edge
  }
  return [];
}

// Bonus: "Graph Valid Tree" — a tree is exactly (n-1 edges) + (no cycle)
function validTree(n, edges) {
  if (edges.length !== n - 1) return false;
  const dsu = new DSU(n);
  for (const [u, v] of edges) if (!dsu.union(u, v)) return false;
  return true; // n-1 edges and no cycle forces connectivity — no need to check it separately
}

Accounts Merge — union-find on things that aren't integers

DSU indexes integers, so the real work in most "merge these groups" problems is the mapping layer: assign each distinct string an integer id, union, then bucket by root. This is the pattern for Accounts Merge, "Sentence Similarity II," "Synonymous Sentences," and every merge-duplicates question.

// accounts[i] = [name, email1, email2, ...]. Merge accounts sharing any email.
function accountsMerge(accounts) {
  const emailToId = new Map();
  const emailToName = new Map();
  let nextId = 0;

  for (const account of accounts) {
    const name = account[0];
    for (let i = 1; i < account.length; i++) {
      const email = account[i];
      if (!emailToId.has(email)) emailToId.set(email, nextId++);
      emailToName.set(email, name);
    }
  }

  const dsu = new DSU(nextId);
  for (const account of accounts) {
    const firstId = emailToId.get(account[1]);
    for (let i = 2; i < account.length; i++) {
      dsu.union(firstId, emailToId.get(account[i])); // chain every email to the account's first email
    }
  }

  const groups = new Map(); // root id → list of emails
  for (const [email, id] of emailToId) {
    const root = dsu.find(id);
    if (!groups.has(root)) groups.set(root, []);
    groups.get(root).push(email);
  }

  const result = [];
  for (const emails of groups.values()) {
    emails.sort();
    result.push([emailToName.get(emails[0]), ...emails]); // any email in the group maps to the same name
  }
  return result;
}

Complexity is O(E · α + E log E), where E is the total number of emails — the sort at the end dominates, which is worth saying out loud because it shows you costed the whole solution, not just the clever part.

Number of Islands II: when land keeps appearing

The grid section above promised this one. "An m × n grid starts as all water. Positions are turned into land one at a time; after each one, report the number of islands." Re-running a flood fill after every position costs O(m · n) each time. With union-find, each new land cell is one insertion plus at most four unions.

The counter logic is the part to get exactly right. When a cell becomes land, it starts as a new island, so add 1. Then look at its four neighbours. Every neighbour that is already land and was in a different set gets merged with this cell, so the number of islands drops by one per successful merge. That is the same "union returned true" signal as before. Note that the chapter's components counter is no help here, because it counts every water cell as a separate component; keep your own islands counter.

function numIslands2(m, n, positions) {
  const dsu = new DSU(m * n);
  const isLand = new Uint8Array(m * n);
  const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
  let islands = 0;
  const answer = [];

  for (const [r, c] of positions) {
    const id = r * n + c;
    if (!isLand[id]) {          // a repeated position changes nothing
      isLand[id] = 1;
      islands++;                // a new island, until a neighbour says otherwise
      for (const [dr, dc] of dirs) {
        const nr = r + dr, nc = c + dc;
        if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
        const neighbour = nr * n + nc;
        if (isLand[neighbour] && dsu.union(id, neighbour)) islands--; // joined two different islands
      }
    }
    answer.push(islands);
  }
  return answer;
}

Dry run: a 3 × 3 grid and positions (0,0), (0,2), (1,1), (0,1), (0,1)

One cell joined three islands and the counter went from 3 to 1, because the +1 for the new cell and three successful unions net to -2. Time is O(m · n + k · α(m · n)) for k positions: building the structure is linear in the grid, each position is constant amortized.

Most Stones Removed: make the rows and columns the elements

"Stones sit on integer grid points. A stone may be removed if another stone shares its row or its column. What is the largest number of stones you can remove?" The obvious elements to union are the stones, which needs pairwise checks. A better choice: make every row and every column an element, and treat each stone as the thing that connects its row to its column.

Now ask what a connected group looks like. All stones in one group are linked by shared lines, so you can remove them one at a time, always taking a stone that still shares a line with another one, until a single stone is left. (Take the stones in the reverse of the order a search would discover them from some starting stone, and each removed stone still has a neighbour left.) You can never remove the last stone of a group, since it shares no line with any other stone, and groups cannot help each other because they share no row or column. So each group leaves exactly one stone, and the answer is stones - groups.

function removeStones(stones) {
  const rowId = new Map(), colId = new Map();
  let next = 0;
  const links = [];

  for (const [r, c] of stones) {
    if (!rowId.has(r)) rowId.set(r, next++); // a row and a column are two different elements
    if (!colId.has(c)) colId.set(c, next++);
    links.push([rowId.get(r), colId.get(c)]);
  }

  const dsu = new DSU(next);
  for (const [a, b] of links) dsu.union(a, b); // a stone joins its row to its column

  return stones.length - dsu.components;       // one stone must stay in every group
}

Dry run: stones (0,0), (0,2), (1,1), (2,0), (2,2)

Two groups remain, so the answer is 5 - 2 = 3. The count of sets works as the number of groups only because every row and column in the table was created by some stone; an element that no stone touches would be a set of its own and inflate the count. Time is O(S · α) for S stones. The same "make the lines the elements" idea solves any problem where objects are linked through shared attributes.

Smallest String With Swaps: connected positions can be sorted

"Given a string and pairs of indices, you may swap the characters at the two indices of any pair, any number of times. Return the lexicographically smallest string you can reach." Think of the indices as nodes and the pairs as edges. Along a chain of swaps you can move any character to any other position in the same connected group (repeated adjacent swaps do it, the way bubble sort moves values), and a swap never moves a character out of its group. So inside a group, any arrangement is reachable. The smallest string puts the smallest letter in the earliest position of the group, the next smallest in the next position, and so on.

function smallestStringWithSwaps(s, pairs) {
  const n = s.length;
  const dsu = new DSU(n);
  for (const [a, b] of pairs) dsu.union(a, b);

  const groups = new Map(); // root -> indices in this group, collected in increasing order
  for (let i = 0; i < n; i++) {
    const root = dsu.find(i);
    if (!groups.has(root)) groups.set(root, []);
    groups.get(root).push(i);
  }

  const out = new Array(n);
  for (const indices of groups.values()) {
    const letters = indices.map((i) => s[i]).sort(); // smallest letters first
    indices.forEach((position, k) => { out[position] = letters[k]; }); // earliest positions get them
  }
  return out.join("");
}

Walk through "dcab" with pairs [[0,3],[1,2]]. The groups are positions {0, 3} holding d and b, and positions {1, 2} holding c and a. Sort each group's letters (b, d and a, c) and write them back in increasing position order: positions 0 and 3 get b and d, positions 1 and 2 get a and c. The result is "bacd". Adding the pair [0,2] merges the two groups into one, and the result becomes "abcd". Time is O((n + P) · α + n log n) for P pairs; the sort inside groups is the dominant term.

Largest Component Size by Common Factor: union through shared primes

"Two numbers are connected if they share a common factor greater than 1. Return the size of the largest connected group in an array." Checking every pair with gcd is O(N²). The way out is the same trick as for stones: introduce intermediate elements. Two numbers share a factor greater than 1 exactly when they share a prime factor, so for every prime factor p of a number, connect the number to p. Numbers that share a prime end up in the same set through that prime, with no pairwise comparison.

The code keeps a map from prime to the index of the first number that had it. The next number with that prime unions with that index. Finding a number's prime factors by trial division takes at most √x tries, and what remains after dividing out every factor up to √x is itself a prime.

function largestComponentSize(nums) {
  const dsu = new DSU(nums.length);
  const owner = new Map(); // prime -> index of the first number that has it

  function link(index, prime) {
    if (owner.has(prime)) dsu.union(index, owner.get(prime));
    else owner.set(prime, index);
  }

  for (let i = 0; i < nums.length; i++) {
    let x = nums[i];
    for (let p = 2; p * p <= x; p++) {
      if (x % p !== 0) continue;
      link(i, p);
      while (x % p === 0) x /= p;
    }
    if (x > 1) link(i, x); // what is left over is one prime larger than the square root
  }

  let best = 0;
  for (let i = 0; i < nums.length; i++) best = Math.max(best, dsu.setSize(i));
  return best;
}

Dry run: [4, 6, 15, 35]

All four numbers end in one set, so the answer is 4, although 4 and 35 share no factor directly: the chain 4 - 6 - 15 - 35 does it. Time is O(N · √M + N · α) where M is the largest value, and the trial division is the cost that matters. For values up to 10⁵ that is a few hundred steps per number.

Weighted union-find: Evaluate Division

"You are given equations like a / b = 2.0 and b / c = 3.0. Answer queries such as a / c, returning -1 when the answer cannot be determined." Plain union-find only records whether two variables are related. Here the relation has a size, so store it: for every element x keep ratio[x] = value(x) / value(parent of x). The root of a set is the yardstick, and every other variable is a multiple of its root.

Find with compression. When find re-points x directly at the root, the stored ratio must change too. After the recursive find(p) on x's parent, ratio[p] equals value(p) / value(root), and ratio[x] = value(x) / value(p) was already stored. Multiplying the two gives value(x) / value(root), which is the new ratio for the new parent.

Union. To record a / b = v, find the roots ra and rb. After the finds, value(a) = ratio[a] · value(ra) and value(b) = ratio[b] · value(rb). Setting value(a) = v · value(b) and solving for value(ra) / value(rb) gives v · ratio[b] / ratio[a]. Store that as ratio[ra] and hang ra under rb. The code hangs the smaller set under the larger one, as in the main DSU; when it is rb that goes underneath, the stored ratio is the reciprocal.

class RatioDSU {
  constructor() {
    this.parent = new Map();
    this.ratio = new Map(); // ratio.get(x) = value(x) / value(parent of x)
    this.size = new Map();
  }

  add(x) {
    if (!this.parent.has(x)) {
      this.parent.set(x, x);
      this.ratio.set(x, 1);
      this.size.set(x, 1);
    }
  }

  has(x) { return this.parent.has(x); }

  find(x) {
    const p = this.parent.get(x);
    if (p === x) return x;
    const root = this.find(p); // after this, ratio.get(p) is value(p) / value(root)
    this.ratio.set(x, this.ratio.get(x) * this.ratio.get(p));
    this.parent.set(x, root);
    return root;
  }

  union(a, b, value) { // the equation a / b = value
    const ra = this.find(a), rb = this.find(b);
    if (ra === rb) return;
    const r = (value * this.ratio.get(b)) / this.ratio.get(a); // value(ra) / value(rb)
    if (this.size.get(ra) <= this.size.get(rb)) {
      this.parent.set(ra, rb);
      this.ratio.set(ra, r);
      this.size.set(rb, this.size.get(rb) + this.size.get(ra));
    } else {
      this.parent.set(rb, ra);
      this.ratio.set(rb, 1 / r); // the smaller set hangs under the larger, so the ratio flips
      this.size.set(ra, this.size.get(ra) + this.size.get(rb));
    }
  }
}

function calcEquation(equations, values, queries) {
  const dsu = new RatioDSU();
  equations.forEach(([a, b], i) => {
    dsu.add(a);
    dsu.add(b);
    dsu.union(a, b, values[i]);
  });

  return queries.map(([a, b]) => {
    if (!dsu.has(a) || !dsu.has(b)) return -1;
    if (dsu.find(a) !== dsu.find(b)) return -1; // also leaves both ratios relative to the same root
    return dsu.ratio.get(a) / dsu.ratio.get(b);
  });
}

Dry run: a / b = 2, b / c = 3, then three queries

Compare this with the alternative, a DFS from the numerator to the denominator for every query. The DFS costs O(V + E) per query; the weighted DSU answers each query in near-constant amortized time after the equations are loaded. Union by size is kept here for a practical reason: the recursive find follows the whole chain, and without the size rule a long run of unions can build a chain tens of thousands deep and overflow the call stack.

Parity union-find: Possible Bipartition

"Split n people into two groups so that no pair who dislike each other are in the same group." This is two-colouring a graph, which BFS does. The union-find version generalizes: the relation stored between two elements is not "same set" but "same side" or "other side", one bit. Keep parity[x] as the bit between x and its parent, exactly as the ratio was kept in the previous section, with XOR where the ratio used multiplication.

Union (demand opposite sides). After finding the roots, the side of a relative to its root is parity[a], and likewise for b. If the roots are the same, the demand is satisfied exactly when parity[a] !== parity[b]; if not, the data contradicts the demand and the answer is false. If the roots differ, attach one root under the other (the smaller set under the larger) with parity[root] = parity[a] ^ parity[b] ^ 1, the value that makes a and b land on opposite sides; the bit is the same whichever root goes underneath.

class ParityDSU {
  constructor(n) {
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.size = new Array(n).fill(1);
    this.parity = new Array(n).fill(0); // parity[x] = 0 if x is on the same side as its parent, 1 if on the other
  }

  find(x) {
    if (this.parent[x] === x) return x;
    const p = this.parent[x];
    const root = this.find(p);
    this.parity[x] ^= this.parity[p]; // parity[p] is now relative to the root
    this.parent[x] = root;
    return root;
  }

  separate(a, b) { // demand that a and b are on different sides; false if that contradicts what is known
    const ra = this.find(a), rb = this.find(b);
    if (ra === rb) return this.parity[a] !== this.parity[b];
    const link = this.parity[a] ^ this.parity[b] ^ 1; // the parity between the two roots
    const [small, big] = this.size[ra] <= this.size[rb] ? [ra, rb] : [rb, ra];
    this.parent[small] = big;
    this.parity[small] = link; // the same bit whichever root goes underneath
    this.size[big] += this.size[small];
    return true;
  }
}

function possibleBipartition(n, dislikes) {
  const dsu = new ParityDSU(n + 1); // people are numbered from 1
  for (const [a, b] of dislikes) {
    if (!dsu.separate(a, b)) return false;
  }
  return true;
}

Dry run: dislikes [[1,2],[2,3],[3,1]], three people who all dislike each other

Person 1 is on the opposite side of 2, and 2 on the opposite side of 3, so 1 and 3 are on the same side, yet they dislike each other. The same three-person triangle is the shortest odd cycle. Time is near-linear in the number of dislikes, the same as a BFS colouring.

Why bother, when BFS works? Because the parity DSU is online: it accepts constraints one at a time and tells you at the exact moment the system becomes contradictory, and it composes with other DSU features. Problems such as "Is Graph Bipartite" in a streaming setting, or "Satisfiability of Equality Equations" in its generalized form (equal, not equal, and "differs by a fixed amount"), are all this one idea. The ratio version and the parity version are both instances of storing a group element on each edge to the parent.

Redundant Connection II: directed union-find, carefully

The earlier warning stands: plain union-find ignores direction. But there is a directed version of Redundant Connection that it can still solve, once you remove the ambiguity first. "A rooted tree has n nodes with edges pointing from parent to child. One extra directed edge was added. Given the n edges, return the one to remove so the rest is a rooted tree; if there are several answers, return the one that appears last in the input."

Adding one edge to a rooted tree can break the structure in two ways, and they can happen at once:

• A node with two parents. The new edge points at a node that already had a parent. One of those two edges must go.
• A cycle. The new edge points back at an ancestor, creating a loop. Then some edge on the loop must go.

So the algorithm has three steps. First scan the edges and record whether some node receives two edges; call the earlier one first and the later one second. Then rebuild the graph with second skipped, running union-find on it. In this reduced graph every node has at most one parent, so a loop shows up as a union that fails, and the undirected check is now legitimate. Finally decide:

function findRedundantDirectedConnection(edges) {
  const n = edges.length;
  const parentOf = new Array(n + 1).fill(0);
  let first = null, second = null; // two edges that enter the same node, if there are any

  for (const [u, v] of edges) {
    if (parentOf[v] !== 0) {
      first = [parentOf[v], v]; // the edge that got there earlier
      second = [u, v];          // the one that arrived later
    } else {
      parentOf[v] = u;
    }
  }

  const dsu = new DSU(n + 1);
  for (const [u, v] of edges) {
    if (second && u === second[0] && v === second[1]) continue; // try the graph without the later edge
    if (!dsu.union(u, v)) return first ? first : [u, v];         // a cycle is left: the earlier edge is guilty
  }
  return second; // no cycle without it, so removing the later of the two parent edges works
}

Dry run: the three situations

Offline union-find: play time backwards (Bricks Falling When Hit)

Union-find can only merge. So when a problem deletes things, the trick is to run the timeline in reverse, where deletions become insertions. "A grid of bricks: a brick is stable if it touches the top row or touches a stable brick. You are given a list of hits; each hit removes one brick (if present) and then every brick that is no longer stable falls. For each hit, report how many bricks fall, not counting the one that was hit." Assume the starting grid is stable.

Forward, each hit can disconnect an unknown number of bricks from the top, and union-find cannot undo a union. In reverse, you start from the grid after all hits and add the bricks back one at a time, last hit first. Add a virtual node ROOF, joined to every brick in row 0. The number of bricks that were stable at any moment is the size of the ROOF's set minus one. Restoring the brick of hit i connects it, and perhaps a whole group hanging off it, to the rest. The growth of the ROOF's set measures exactly the bricks that would have fallen when that brick was hit. The restored brick is counted in the growth too, so subtract 1.

function hitBricks(grid, hits) {
  const R = grid.length, C = grid[0].length;
  const ROOF = R * C;
  const g = grid.map((row) => row.slice());

  const removed = hits.map(([r, c]) => {
    const wasBrick = g[r][c] === 1;
    g[r][c] = 0;
    return wasBrick;
  });

  const dsu = new DSU(R * C + 1);
  const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];

  function attach(r, c) {
    const id = r * C + c;
    if (r === 0) dsu.union(id, ROOF);
    for (const [dr, dc] of dirs) {
      const nr = r + dr, nc = c + dc;
      if (nr >= 0 && nr < R && nc >= 0 && nc < C && g[nr][nc] === 1) dsu.union(id, nr * C + nc);
    }
  }

  for (let r = 0; r < R; r++) {
    for (let c = 0; c < C; c++) if (g[r][c] === 1) attach(r, c); // the grid after every hit
  }

  const answer = new Array(hits.length).fill(0);
  for (let i = hits.length - 1; i >= 0; i--) { // play time backwards
    if (!removed[i]) continue;
    const [r, c] = hits[i];
    const before = dsu.setSize(ROOF);
    g[r][c] = 1;
    attach(r, c);
    const after = dsu.setSize(ROOF);
    answer[i] = Math.max(0, after - before - 1); // the restored brick itself is not one that fell
  }
  return answer;
}

Dry run: grid [[1,0,0,0],[1,1,1,0]], hits [[1,0]]

The two bricks (1,1) and (1,2) were only held up by the hit brick, so they fall, and the answer is [2]. Time is O((R · C + H) · α) for H hits. A hit that lands on an empty cell contributes 0 and must not be restored, which is why the code records removed[i] at the time of the forward pass rather than looking at the grid later.

The reverse-time idea is general. Whenever a problem says "remove" and asks something that union-find answers, ask whether the removals can be replayed backwards as additions. A network that loses its links one at a time, with a question about connectivity after each failure, has this shape. If the removals cannot be reversed, the rollback structure in the next section is the tool.

The advanced aside: union-find with rollback

DSU has no split — you cannot un-merge two sets in general. But you can undo unions in reverse order if you keep a journal, which is enough for divide-and-conquer over time ("offline dynamic connectivity": each edge exists during an interval of queries, so you add it going down a segment-tree recursion and roll it back coming up).

class RollbackDSU {
  constructor(n) {
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.size = new Array(n).fill(1);
    this.history = []; // journal of [childRoot, parentRoot] merges
  }

  find(x) {
    while (this.parent[x] !== x) x = this.parent[x]; // NO path compression — it isn't undoable
    return x;
  }

  union(a, b) {
    let ra = this.find(a), rb = this.find(b);
    if (ra === rb) { this.history.push(null); return false; } // record a no-op so undo() stays aligned
    if (this.size[ra] < this.size[rb]) [ra, rb] = [rb, ra];
    this.parent[rb] = ra;
    this.size[ra] += this.size[rb];
    this.history.push([rb, ra]);
    return true;
  }

  undo() {
    const entry = this.history.pop();
    if (!entry) return;
    const [child, root] = entry;
    this.parent[child] = child;      // exactly one pointer changed, so exactly one is restored
    this.size[root] -= this.size[child];
  }
}

The trade: dropping path compression costs you α and buys back O(log n) per operation from union-by-size alone — a fair price for undo. You almost certainly won't have to write this in an interview, but naming it when asked "what if edges could also be removed?" is exactly the kind of answer that separates candidates.

One more forward reference: the next chapter, Minimum Spanning Tree, is essentially this data structure plus a sort. Kruskal's algorithm is "sort all edges by weight, then add each edge whose union returns true" — the boolean you already have is precisely the "does this edge connect two different components?" test the algorithm needs.

See the chain flatten

Watch what path compression actually rewrites. The find that flattens the chain is doing the work that makes every later find cheap.

Recognizing it in an unseen problem

• The words "connected," "groups," "merge," "same network," "provinces," "friend circles," "accounts belonging to one person." Anything that is an equivalence relation (reflexive, symmetric, transitive) is a union-find problem.
• Edges arrive over time, or the question is asked repeatedly. One BFS answers one snapshot; DSU answers a stream. If you see "after each query, report the number of components," DSU is almost forced.
• Brute force would be: re-run DFS/BFS after every edge — O(E) per edge, O(E²) total. DSU makes it O(E · α).
• Distinguish from BFS/DFS: if the graph is static and you also need paths, distances, or an ordering, use traversal — DSU knows nothing about distance, path, or direction. It only answers "same set?"
• Distinguish from topological sort: DSU is undirected only. Directed dependencies, cycle detection in a DAG, ordering → topological sort.
• Objects linked through a shared attribute (stones that share a row or column, numbers that share a prime) → make the attributes elements too and union each object with its attributes, instead of comparing every pair of objects.
• "Group the positions, then rearrange inside each group" → union to find the groups, then collect by root and sort or fill each group on its own (smallest string with swaps).
• A relation that has a size or a side (a / b = 2.5, "must be on opposite teams") → store a ratio or a parity bit on each edge to the parent, and update it when you compress paths.
• Things are deleted and you need connectivity after each deletion → read the timeline backwards so deletions become unions, as in Bricks Falling When Hit.
• Pitfalls: forgetting find before reading size; sizing the array wrong on 1-indexed inputs; and comparing roots with parent[a] === parent[b] instead of find(a) === find(b) — the second is the only correct test.