Part 13 · Lesson 53 · read
Union-Find
Group things fast: connected groups, finding cycles and minimum spanning trees.
On this page
The question: are these two connected?
Lesson 50 counted connected components (separate groups of linked things) by walking through the graph. That works when you get the whole graph at once. But what if the edges (links) arrive one at a time, and after each one someone asks: “are A and B in the same group now?” Running BFS again after every edge would cost O(V + E) per question. Union-Find is a data structure that keeps elements in separate groups, and can quickly tell whether two elements are in the same group and merge two groups. It is also called a disjoint-set union (DSU). It answers the same questions much faster. It has two operations:
- find(x): which group is x in? (It returns one element that stands for the whole group.)
- union(a, b): merge the group of a with the group of b.
“Disjoint” means no element is in two groups at the same time. Two elements are connected exactly when find gives the same answer for both. The structure only ever merges groups. It cannot split them, and that is why it is so cheap.
A parent array and find
For each element, store a parent: parent[i]. Keep following parents upward. You will reach an element whose parent is itself. That element is the root, and it stands for the whole group. Think of each group as a small tree where every arrow points up to the root. It is like a company where every worker points to a boss, and the top boss points to themselves.
// The simplest possible version: parent[i] is the "boss" of i. A root is its own boss.const parent = [0, 1, 2, 3, 4, 5]; // at the start every element is alone in its groupfunction find(x) { while (parent[x] !== x) x = parent[x]; // climb the bosses until we reach a root return x;}function union(a, b) { const rootA = find(a), rootB = find(b); if (rootA !== rootB) parent[rootA] = rootB; // hang one root under the other}union(0, 1);union(2, 3);union(1, 3);console.log(parent); // [ 1, 3, 3, 3, 4, 5 ]console.log(find(0) === find(2)); // true (0 -> 1 -> 3 and 2 -> 3: same root)console.log(find(0) === find(4)); // falsefind climbs up to the root. union finds both roots and hangs one under the other. If the two roots are the same, the elements are already together and nothing happens. Always compare the roots. Two elements in the same group often have different parents.
Why plain union can go wrong
The height of the tree decides how long find takes. If you merge in an unlucky order, the groups can pile up into one long chain. Then find has to walk through all n elements:
// Danger: uniting in an unlucky order builds one long chain.const n = 8;const parent = Array.from({ length: n }, (_, i) => i);function find(x) { let steps = 0; while (parent[x] !== x) { x = parent[x]; steps++; } return steps; // for this demo we return how far we climbed}for (let i = 0; i < n - 1; i++) { // union(i, i + 1) written as "put the root of the big group under the new element" let root = i; while (parent[root] !== root) root = parent[root]; parent[root] = i + 1;}console.log(parent); // [ 1, 2, 3, 4, 5, 6, 7, 7 ]console.log(find(0)); // 7 (one hop per element: find costs O(n))Two small ideas fix this. You can use them one at a time or together.
Path compression
When find walks up a long path, it learns the root of every element on that path. So point each of those elements straight at the root. The first find may be slow, but it flattens the tree, so the next finds are fast. In code this is one extra line:
// Path compression: after finding the root, point every element we passed straight at it.const parent = [1, 2, 3, 4, 5, 6, 7, 7]; // the chain from the previous examplefunction find(x) { if (parent[x] !== x) parent[x] = find(parent[x]); // recurse to the root, then re-point x at it return parent[x];}console.log(find(0)); // 7console.log(parent); // [ 7, 7, 7, 7, 7, 7, 7, 7 ]console.log(find(0)); // 7 (this time it is a single hop)find uses the call stack (the computer's list of unfinished function calls), one entry per step up. With union by size (next section) the tree height stays around log n, so this is safe. If you use compression without union by size on a huge input, write find as a loop. First find the root. Then walk the path a second time to point each element at the root.Union by size
The second idea stops the chain before it starts. When you merge, always hang the smaller group under the root of the bigger group. An element only gets deeper when its group is merged into a group at least as big. So its group at least doubles in size each time. A group can double only log₂ n times, so no element is deeper than about log₂ n. (A similar idea is union by rank. It compares tree heights instead of sizes and gives the same guarantee. Size is easier to keep correct once compression starts making trees shorter.) Here is the version to memorise. It also has a counter for the number of groups:
class UnionFind { constructor(n) { this.parent = Array.from({ length: n }, (_, i) => i); this.size = new Array(n).fill(1); // size[root] = number of elements in that root's group this.count = n; // number of separate groups } find(x) { if (this.parent[x] !== x) this.parent[x] = this.find(this.parent[x]); // path compression return this.parent[x]; } union(a, b) { let ra = this.find(a), rb = this.find(b); if (ra === rb) return false; // already together: nothing to merge if (this.size[ra] < this.size[rb]) [ra, rb] = [rb, ra]; // ra is now the bigger group this.parent[rb] = ra; // small group hangs under the big one this.size[ra] += this.size[rb]; this.count--; return true; } connected(a, b) { return this.find(a) === this.find(b); }}const uf = new UnionFind(6);console.log(uf.union(0, 1), uf.union(2, 3), uf.union(1, 3)); // true true trueconsole.log(uf.connected(0, 2), uf.connected(0, 4)); // true falseconsole.log(uf.union(0, 3), uf.count); // false 3How fast is it, really?
| Heuristics used | Cost | Why |
|---|---|---|
| Neither trick | up to O(n) | one long chain can happen |
| Union by size only | O(log n) | each time an element goes one level deeper, its group at least doubles in size |
| Path compression only | O(log n) amortised | a slow find now and then is paid for by the flattening it causes |
| Both together | O(α(n)) amortised | α(n) is the inverse Ackermann function. It is below 5 for any n that could fit in the universe |
With both tricks, m operations on n elements cost O(m × α(n)) in total.
People often say “union-find is O(1)”. This is a fair shortcut, but it is not exactly true. The exact cost is O(α(n)) amortised per operation. α is the inverse Ackermann function, a function that grows so slowly that α(n) is at most 4 for any n you could ever store. So in practice it acts like a constant, but in maths it is not one. “Amortised” means averaged over a whole series of operations. One find can still be slow, but slow calls flatten the tree so well that the average stays tiny. In interviews, say “nearly constant, formally inverse Ackermann” and you are correct.
Traced: a union-find run
Every element is its own root. There are six groups of one.
▶const parent = [0, 1, 2, 3, 4, 5];2const size = [1, 1, 1, 1, 1, 1];3function find(x) {4 if (parent[x] !== x) parent[x] = find(parent[x]);5 return parent[x];6}7function union(a, b) {8 let ra = find(a), rb = find(b);9 if (ra === rb) return false;10 if (size[ra] < size[rb]) [ra, rb] = [rb, ra];11 parent[rb] = ra;12 size[ra] += size[rb];13 return true;14}15union(0, 1);16union(2, 3);17union(1, 3);18find(3);19union(4, 5);20union(5, 0);21union(3, 1);| parent | [0, 1, 2, 3, 4, 5] |
| size | [1, 1, 1, 1, 1, 1] |
| Call | What we see | What happens | Result |
|---|---|---|---|
| union(0, 1) | 0 and 1 are groups of one | same size, so 1 hangs under 0 | parent = [0, 0, 2, 3, 4, 5] |
| union(2, 3) | same as before | 3 hangs under 2 | parent = [0, 0, 2, 2, 4, 5] |
| union(1, 3) | roots 0 and 2, both of size 2 | same size, so 2 hangs under 0 | parent = [0, 0, 0, 2, 4, 5] |
| find(3) | 3 → 2 → 0 | compress: 3 now points to 0 | parent = [0, 0, 0, 0, 4, 5] |
| union(4, 5) | groups of one | 5 hangs under 4 | parent = [0, 0, 0, 0, 4, 4] |
| union(5, 0) | roots 4 (size 2) and 0 (size 4) | swap, so 4 hangs under 0 | parent = [0, 0, 0, 0, 0, 4] |
| union(3, 1) | roots 0 and 0 | same root: return false | unchanged |
Counting components and redundant edges
Start with count = n groups. Every union that works merges two groups, so it lowers the count by one. After all the edges, count is the number of connected components. A union that fails (same root) means this edge joined two vertices that were already connected. It closes a cycle (a loop). We call it a redundant edge, because removing it would not disconnect anything. This one return value gives you cycle detection in an undirected graph (edges with no direction) for free.
class UnionFind { constructor(n) { this.parent = Array.from({ length: n }, (_, i) => i); this.size = new Array(n).fill(1); this.count = n; } find(x) { if (this.parent[x] !== x) this.parent[x] = this.find(this.parent[x]); return this.parent[x]; } 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]; this.parent[rb] = ra; this.size[ra] += this.size[rb]; this.count--; return true; }}// How many groups are left after adding these edges?function countComponents(n, edges) { const uf = new UnionFind(n); for (const [a, b] of edges) uf.union(a, b); return uf.count;}// Which edges were redundant (they joined two vertices that were already connected)?function redundantEdges(n, edges) { const uf = new UnionFind(n); return edges.filter(([a, b]) => !uf.union(a, b));}console.log(countComponents(6, [[0, 1], [1, 2], [3, 4]])); // 3console.log(redundantEdges(4, [[0, 1], [1, 2], [2, 3], [3, 0], [0, 2]])); // [ [ 3, 0 ], [ 0, 2 ] ]Kruskal's minimum spanning tree
A spanning tree of a connected, weighted, undirected graph is a set of n − 1 edges that links every vertex with no cycle. The minimum spanning tree (MST) is the one with the smallest total weight. Think of laying cable to connect every city for the lowest cost.
Kruskal's algorithm is greedy (lesson 47). Greedy means you always take the best-looking choice right now. Sort all edges by weight. Go through them from the cheapest. Keep an edge if it joins two different groups. Skip it if it would close a cycle. Union-find is exactly the cycle test. Sorting costs O(E log E). The union-find work adds a nearly constant cost per edge. So the total is O(E log E).
// Kruskal's algorithm: take the cheapest edges first, skip any edge that would close a cycle.function kruskal(n, edges) { // edges are [a, b, weight] const parent = Array.from({ length: n }, (_, i) => i); const size = new Array(n).fill(1); function find(x) { if (parent[x] !== x) parent[x] = find(parent[x]); return parent[x]; } const sorted = [...edges].sort((p, q) => p[2] - q[2]); // cheapest first let total = 0; const chosen = []; for (const [a, b, w] of sorted) { let ra = find(a), rb = find(b); if (ra === rb) continue; // this edge would make a cycle: skip it if (size[ra] < size[rb]) [ra, rb] = [rb, ra]; parent[rb] = ra; size[ra] += size[rb]; total += w; chosen.push([a, b, w]); if (chosen.length === n - 1) break; // a tree on n vertices has exactly n - 1 edges } return chosen.length === n - 1 ? { total, chosen } : null; // null: the graph is not connected}const edges = [[0, 1, 4], [0, 2, 3], [1, 2, 1], [1, 3, 2], [2, 3, 4], [3, 4, 2]];console.log(kruskal(5, edges)); // { total: 8, chosen: [ [ 1, 2, 1 ], [ 1, 3, 2 ], [ 3, 4, 2 ], [ 0, 2, 3 ] ] }console.log(kruskal(4, [[0, 1, 5], [2, 3, 1]])); // nullIf you reach the end of the edge list with fewer than n − 1 edges chosen, the graph was not connected. So no spanning tree exists.
Practice questions
Look for these clue words: “connected”, “groups”, “merge”, “same component”, “does this edge create a cycle”, or “connect everything at the lowest cost”.
There are n cities. isConnected[i][j] = 1 means city i and city j are directly connected. This works the same in both directions, and isConnected[i][i] = 1. If a city links to a second city, and the second links to a third, the first and third are also connected. A province is a group of cities connected directly or through other cities, with none connected to a city outside the group. Return the number of provinces.
Hint 1
isConnected[i][j] = 1 is an edge (a link) between cities i and j.Hint 2
Hint 3
Show all 2 solutions with explanations
Read the matrix as a table of links (an adjacency matrix). From a city, visit every city it is directly linked to, and keep going the same way (recursion). Each time you have to start from a new city, that is a new province.
function findCircleNum(isConnected) { const n = isConnected.length; const visited = new Array(n).fill(false); function visit(i) { visited[i] = true; for (let j = 0; j < n; j++) { if (isConnected[i][j] === 1 && !visited[j]) visit(j); } } let provinces = 0; for (let i = 0; i < n; i++) { if (!visited[i]) { provinces++; visit(i); } } return provinces;}console.log(findCircleNum([[1, 1, 0], [1, 1, 0], [0, 0, 1]])); // 2console.log(findCircleNum([[1, 0, 0], [0, 1, 0], [0, 0, 1]])); // 3Each city is visited once, and visiting it reads its whole row. So the time is O(n²), and the input itself has n² cells. The space is O(n) for the visited array and the recursion.
Start with count = n. For every pair i < j with a 1, union them. Each merge that works lowers count by one.
function findCircleNum(isConnected) { const n = isConnected.length; const parent = Array.from({ length: n }, (_, i) => i); const size = new Array(n).fill(1); let count = n; function find(x) { if (parent[x] !== x) parent[x] = find(parent[x]); return parent[x]; } for (let i = 0; i < n; i++) { for (let j = i + 1; j < n; j++) { if (isConnected[i][j] !== 1) continue; let a = find(i), b = find(j); if (a === b) continue; if (size[a] < size[b]) [a, b] = [b, a]; parent[b] = a; size[a] += size[b]; count--; } } return count;}console.log(findCircleNum([[1, 1, 0], [1, 1, 0], [0, 0, 1]])); // 2console.log(findCircleNum([[1, 0, 0], [0, 1, 0], [0, 0, 1]])); // 3The time is still O(n² × α(n)), because we must read every cell of the matrix. Union-find only wins when edges arrive one at a time or as a short list. Here it is no better than DFS, but it shows the pattern you will use again below.
Both are fine and take O(n²). Choose DFS to keep it simple, or union-find if you want to practise the template. (LeetCode 547.)
A graph started as a tree with n vertices labelled 1..n. Then one extra edge was added, which gives edges (n edges in total). Return an edge you can remove so that the result is a tree again. If there are several answers, return the one that comes last in the input.
Hint 1
Hint 2
Hint 3
Show all 2 solutions with explanations
Keep a list of each vertex's neighbours for the edges added so far (an adjacency list). Before adding edge [a, b], search to see if you can already get from a to b. If you can, this edge is the answer.
function findRedundantConnection(edges) { const graph = new Map(); function connected(a, b, seen) { if (a === b) return true; seen.add(a); for (const next of graph.get(a) ?? []) { if (!seen.has(next) && connected(next, b, seen)) return true; } return false; } for (const [a, b] of edges) { if (connected(a, b, new Set())) return [a, b]; if (!graph.has(a)) graph.set(a, []); if (!graph.has(b)) graph.set(b, []); graph.get(a).push(b); graph.get(b).push(a); } return [];}console.log(findRedundantConnection([[1, 2], [1, 3], [2, 3]])); // [ 2, 3 ]console.log(findRedundantConnection([[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]])); // [ 1, 4 ]Each search is O(V + E), and we do one per edge, so the total is O(n²). It is fine for the small limits here, but it wastes work because it forgets what it learned before.
Go through the edges in order. If union(a, b) fails because the roots are the same, return that edge.
function findRedundantConnection(edges) { const parent = Array.from({ length: edges.length + 1 }, (_, i) => i); // vertices are 1..n const size = new Array(edges.length + 1).fill(1); function find(x) { if (parent[x] !== x) parent[x] = find(parent[x]); return parent[x]; } for (const [a, b] of edges) { let ra = find(a), rb = find(b); if (ra === rb) return [a, b]; // already connected: this edge closes the cycle if (size[ra] < size[rb]) [ra, rb] = [rb, ra]; parent[rb] = ra; size[ra] += size[rb]; } return [];}console.log(findRedundantConnection([[1, 2], [1, 3], [2, 3]])); // [ 2, 3 ]console.log(findRedundantConnection([[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]])); // [ 1, 4 ]It needs one pass. The time is O(n × α(n)) and the space is O(n). The first edge that fails is also the one that comes last in the cycle. This matches the rule to return the answer that occurs last in the input, because the cycle is closed exactly when its last edge arrives.
Use union-find. A one-line change to the template turns it into cycle detection. (LeetCode 684.)
accounts[i] is a list. Its first item is a person's name and the rest are their emails. Two accounts belong to the same person if they share any email. (A person may have several accounts, and different people may have the same name.) Merge the accounts. For each person, return their name followed by their emails in sorted order. You can return the accounts in any order.
Hint 1
Hint 2
Hint 3
Show all 2 solutions with explanations
Build a list of neighbours for each email (an adjacency list). Link every email in an account to the account's first email, in both directions. Each group of linked emails is one person. Sort the emails and put the name in front.
function accountsMerge(accounts) { const graph = new Map(); // email -> neighbouring emails const owner = new Map(); // email -> name for (const [name, ...emails] of accounts) { for (const e of emails) { owner.set(e, name); if (!graph.has(e)) graph.set(e, []); if (e !== emails[0]) { graph.get(e).push(emails[0]); graph.get(emails[0]).push(e); } } } const seen = new Set(); const result = []; for (const start of graph.keys()) { if (seen.has(start)) continue; const group = []; const stack = [start]; seen.add(start); while (stack.length) { const e = stack.pop(); group.push(e); for (const next of graph.get(e)) { if (!seen.has(next)) { seen.add(next); stack.push(next); } } } group.sort(); result.push([owner.get(start), ...group]); } return result;}console.log(accountsMerge([["John", "a@x", "b@x"], ["John", "b@x", "c@x"], ["Mary", "m@x"]])); // [ [ 'John', 'a@x', 'b@x', 'c@x' ], [ 'Mary', 'm@x' ] ]console.log(accountsMerge([["Sam", "s@x"], ["Sam", "t@x"]])); // [ [ 'Sam', 's@x' ], [ 'Sam', 't@x' ] ]Let N be the total number of emails. Building the graph and walking through it take O(N). Sorting each group makes the total O(N log N). Here the groups come out in the order we first see them. LeetCode accepts any order of accounts.
Remember which account used each email first. When an email shows up again, union the two accounts. At the end, collect every email under the root of its account.
function accountsMerge(accounts) { const parent = Array.from({ length: accounts.length }, (_, i) => i); function find(x) { if (parent[x] !== x) parent[x] = find(parent[x]); return parent[x]; } const firstSeen = new Map(); // email -> index of the first account that had it accounts.forEach(([, ...emails], i) => { for (const e of emails) { if (firstSeen.has(e)) parent[find(i)] = find(firstSeen.get(e)); // same email: same person else firstSeen.set(e, i); } }); const groups = new Map(); // root account -> set of emails for (const [e, i] of firstSeen) { const root = find(i); if (!groups.has(root)) groups.set(root, []); groups.get(root).push(e); } const result = []; for (const [root, emails] of groups) result.push([accounts[root][0], ...emails.sort()]); return result;}console.log(accountsMerge([["John", "a@x", "b@x"], ["John", "b@x", "c@x"], ["Mary", "m@x"]])); // [ [ 'John', 'a@x', 'b@x', 'c@x' ], [ 'Mary', 'm@x' ] ]console.log(accountsMerge([["Sam", "s@x"], ["Sam", "t@x"]])); // [ [ 'Sam', 's@x' ], [ 'Sam', 't@x' ] ]The groups are accounts, not emails, so the union-find array is small. To keep the code short, the merge step here skips union by size. With path compression alone it is still fast. The total is O(N log N), and most of that is the sorting.
Union-find on the accounts is the usual interview answer. The DFS version is just as correct and easier to think about. (LeetCode 721.)
You are given points, where points[i] = [xi, yi]. The cost of linking two points is their Manhattan distance |xi − xj| + |yi − yj|. Return the lowest total cost to connect all points, so that there is exactly one path between any two points.
Hint 1
Hint 2
Hint 3
Show all 2 solutions with explanations
Make all n(n−1)/2 edges and sort them by cost. Add each edge that joins two different groups. Stop when you have n − 1 edges.
function minCostConnectPoints(points) { const n = points.length; const edges = []; for (let i = 0; i < n; i++) { for (let j = i + 1; j < n; j++) { const d = Math.abs(points[i][0] - points[j][0]) + Math.abs(points[i][1] - points[j][1]); edges.push([d, i, j]); } } edges.sort((p, q) => p[0] - q[0]); const parent = Array.from({ length: n }, (_, i) => i); const size = new Array(n).fill(1); function find(x) { if (parent[x] !== x) parent[x] = find(parent[x]); return parent[x]; } let total = 0, used = 0; for (const [d, i, j] of edges) { let a = find(i), b = find(j); if (a === b) continue; if (size[a] < size[b]) [a, b] = [b, a]; parent[b] = a; size[a] += size[b]; total += d; if (++used === n - 1) break; } return total;}console.log(minCostConnectPoints([[0, 0], [2, 2], [3, 10], [5, 2], [7, 0]])); // 20console.log(minCostConnectPoints([[3, 12], [-2, 5], [-4, 1]])); // 18console.log(minCostConnectPoints([[0, 0]])); // 0There are E = n(n−1)/2 edges, so sorting takes O(n² log n) time. The edge list takes O(n²) space.
For each point that is not in the tree yet, keep its cheapest distance to the tree so far. Again and again, pick the cheapest outside point and add its cost. Then update the distances of the other points.
function minCostConnectPoints(points) { const n = points.length; const dist = new Array(n).fill(Infinity); // cheapest known link from the tree to each point const inTree = new Array(n).fill(false); dist[0] = 0; let total = 0; for (let step = 0; step < n; step++) { let best = -1; for (let i = 0; i < n; i++) { if (!inTree[i] && (best === -1 || dist[i] < dist[best])) best = i; } inTree[best] = true; total += dist[best]; for (let i = 0; i < n; i++) { if (inTree[i]) continue; const d = Math.abs(points[best][0] - points[i][0]) + Math.abs(points[best][1] - points[i][1]); if (d < dist[i]) dist[i] = d; } } return total;}console.log(minCostConnectPoints([[0, 0], [2, 2], [3, 10], [5, 2], [7, 0]])); // 20console.log(minCostConnectPoints([[3, 12], [-2, 5], [-4, 1]])); // 18console.log(minCostConnectPoints([[0, 0]])); // 0Prim's algorithm is the other well-known MST method. It grows one tree outwards instead of merging many small ones. With a plain array scan, the time is O(n²) and the space is only O(n). This beats Kruskal on this graph, where every pair of points has an edge.
Kruskal is what this lesson taught, and it is a fine answer. Prim with an array is leaner when the graph is dense (almost every pair has an edge). (LeetCode 1584.)
You have a graph of n vertices labelled 0 to n − 1 and a list edges where edges[i] = [a, b] is an undirected edge (a link with no direction). Return the number of connected components (separate groups).
Hint 1
Hint 2
Show all 2 solutions with explanations
Build the adjacency list (each vertex's list of neighbours). Then start a traversal at each vertex you have not seen yet. Each start is one component.
function countComponents(n, edges) { const graph = Array.from({ length: n }, () => []); for (const [a, b] of edges) { graph[a].push(b); graph[b].push(a); } const visited = new Array(n).fill(false); let count = 0; for (let s = 0; s < n; s++) { if (visited[s]) continue; count++; visited[s] = true; const queue = [s]; let head = 0; while (head < queue.length) { const v = queue[head++]; for (const next of graph[v]) { if (!visited[next]) { visited[next] = true; queue.push(next); } } } } return count;}console.log(countComponents(5, [[0, 1], [1, 2], [3, 4]])); // 2console.log(countComponents(5, [[0, 1], [1, 2], [2, 3], [3, 4]])); // 1The time and space are both O(V + E).
Start the counter at n. Subtract one for every edge whose union works.
function countComponents(n, edges) { const parent = Array.from({ length: n }, (_, i) => i); const size = new Array(n).fill(1); function find(x) { if (parent[x] !== x) parent[x] = find(parent[x]); return parent[x]; } let count = n; for (const [x, y] of edges) { let a = find(x), b = find(y); if (a === b) continue; if (size[a] < size[b]) [a, b] = [b, a]; parent[b] = a; size[a] += size[b]; count--; } return count;}console.log(countComponents(5, [[0, 1], [1, 2], [3, 4]])); // 2console.log(countComponents(5, [[0, 1], [1, 2], [2, 3], [3, 4]])); // 1console.log(countComponents(3, [])); // 3The time is O(n + E × α(n)) and the space is O(n). You do not need to build an adjacency list.
Union-find does not need to build the graph, and it reads the edge list only once. BFS or DFS is just as correct. This is a premium (paid) problem on LeetCode (323, "Number of Connected Components in an Undirected Graph"), so the statement is copied here.
You are given an array of strings equations. Each one looks like "xi==yi" or "xi!=yi", where xi and yi are lowercase letters that stand for whole-number variables. Return true if you can give the variables whole-number values so that every equation is true. Otherwise return false.
Hint 1
== or !=, then a letter.Hint 2
== must have the same value. That is a group.Hint 3
== first. After that, no != may connect two letters from the same group.Show all 2 solutions with explanations
Build a graph with an edge for every ==. For each !=, search to see if its two letters are connected in that graph. If they are, the equations contradict each other.
function equationsPossible(equations) { const graph = Array.from({ length: 26 }, () => []); const code = (ch) => ch.charCodeAt(0) - 97; for (const eq of equations) { if (eq[1] === "=") { graph[code(eq[0])].push(code(eq[3])); graph[code(eq[3])].push(code(eq[0])); } } function connected(a, b) { const seen = new Array(26).fill(false); const stack = [a]; seen[a] = true; while (stack.length) { const v = stack.pop(); if (v === b) return true; for (const next of graph[v]) { if (!seen[next]) { seen[next] = true; stack.push(next); } } } return false; } for (const eq of equations) { if (eq[1] === "!" && connected(code(eq[0]), code(eq[3]))) return false; } return true;}console.log(equationsPossible(["a==b", "b!=a"])); // falseconsole.log(equationsPossible(["a==b", "b==c", "a==c"])); // trueconsole.log(equationsPossible(["a==b", "b!=c", "c==a"])); // falseEach != costs a search over at most 26 vertices and the equality edges. So the worst case is O(E × (26 + E)). It works, but every check starts from nothing.
First pass: union the two letters of every ==. Second pass: for every !=, if both letters have the same root, return false. If no != fails, return true.
function equationsPossible(equations) { const parent = Array.from({ length: 26 }, (_, i) => i); function find(x) { if (parent[x] !== x) parent[x] = find(parent[x]); return parent[x]; } const code = (ch) => ch.charCodeAt(0) - 97; for (const eq of equations) { if (eq[1] === "=") parent[find(code(eq[0]))] = find(code(eq[3])); } for (const eq of equations) { if (eq[1] === "!" && find(code(eq[0])) === find(code(eq[3]))) return false; } return true;}console.log(equationsPossible(["a==b", "b!=a"])); // falseconsole.log(equationsPossible(["a==b", "b==c", "a==c"])); // trueconsole.log(equationsPossible(["a==b", "b!=c", "c==a"])); // falseconsole.log(equationsPossible(["a!=a"])); // falseThe time is O(E × α(26)), which is basically O(E). The order matters. Apply all the equalities before you check any inequality. Otherwise a later == could make an earlier check wrong. A pair like a!=a fails at once, because a letter always has the same root as itself.
Use union-find: two simple loops over an array of 26 items. (LeetCode 990.)
There are n computers numbered 0 to n − 1 and a list of network cables connections, where connections[i] = [a, b] links computers a and b. You can unplug any cable and plug it between two computers that are not directly connected. Return the smallest number of such moves needed to connect all computers. Return −1 if it is impossible.
Hint 1
Hint 2
Hint 3
Show all 2 solutions with explanations
If connections.length < n − 1, return −1. Otherwise count the components with a traversal and return components − 1.
function makeConnected(n, connections) { if (connections.length < n - 1) return -1; const graph = Array.from({ length: n }, () => []); for (const [a, b] of connections) { graph[a].push(b); graph[b].push(a); } const visited = new Array(n).fill(false); function visit(v) { visited[v] = true; for (const next of graph[v]) if (!visited[next]) visit(next); } let components = 0; for (let v = 0; v < n; v++) { if (!visited[v]) { components++; visit(v); } } return components - 1;}console.log(makeConnected(4, [[0, 1], [0, 2], [1, 2]])); // 1console.log(makeConnected(6, [[0, 1], [0, 2], [0, 3], [1, 2], [1, 3]])); // 2console.log(makeConnected(6, [[0, 1], [0, 2], [0, 3], [1, 2]])); // -1The time and space are O(n + E). The early check is the tricky part. With at least n − 1 cables there are always enough spare cables, because a group of c computers needs only c − 1 of its own cables to stay connected.
Do the same check, then union every cable. After the successful unions, count is the number of components. The answer is count − 1.
function makeConnected(n, connections) { if (connections.length < n - 1) return -1; const parent = Array.from({ length: n }, (_, i) => i); const size = new Array(n).fill(1); function find(x) { if (parent[x] !== x) parent[x] = find(parent[x]); return parent[x]; } let components = n; for (const [x, y] of connections) { let a = find(x), b = find(y); if (a === b) continue; // a spare cable: it joins nothing new if (size[a] < size[b]) [a, b] = [b, a]; parent[b] = a; size[a] += size[b]; components--; } return components - 1;}console.log(makeConnected(4, [[0, 1], [0, 2], [1, 2]])); // 1console.log(makeConnected(6, [[0, 1], [0, 2], [0, 3], [1, 2], [1, 3]])); // 2console.log(makeConnected(6, [[0, 1], [0, 2], [0, 3], [1, 2]])); // -1The unions that fail are exactly the spare cables. This joins two ideas from this lesson: redundant edges are what you have to give, and components minus one is what you need. The time is O(n + E × α(n)).
Either way works. Union-find is shorter here and shows the spare-cable idea directly. (LeetCode 1319.)
Make it stick
- Write the parent array,
findandunionfrom memory. - Explain how a chain forms and which two tricks stop it.
- Say what path compression does, and why union by size keeps the depth around log n.
- State the real cost: amortised O(α(n)), nearly constant, but not literally O(1).
- Say how to count components and how to spot a redundant edge.
- Describe Kruskal's algorithm and why it needs union-find.
Revisit schedule: solve two of the questions again tomorrow, again in 3 days, and once more in a week — without looking at the answers. Each time it will feel easier. That is the memory forming.
What's next
That finishes Part 13 (graphs). Lesson 54 starts Part 14, dynamic programming. We begin with the plain recursion from Part 8. You will see that it solves the same small problems again and again. We fix that by saving answers (memoization: remembering the result of each call), and then by filling a table in order (tabulation: building answers from the smallest problem up).
Practise on LeetCode
Real interview problems that use exactly what this lesson teaches. Solve them in JavaScript after the practice questions above.
Published by Jainik · Last updated · How these lessons are made
Keep learning
Part of the study guide
Related series