What is the pricing and subscription model for Hi👋SpeedAlgo?

The entire core curriculum of 13 patterns and 225 practice problems is 100% free to access with no credit card required. New accounts get 40 free coins once, the daily claim adds +20 coins once a day, and inviting a friend earns you +25 coins when they complete their first practice step. These are the only ways to earn coins. Each AI coach question costs 1-5 coins, priced by the server according to its size. AI coaching is free with your own Google Gemini, OpenAI or OpenRouter API key (BYOK). Coins also unlock extras for 24 hours: a Recall hint level (1 coin), a Solve solution reveal (2), a LeetCode problem card's solutions (1) and a pattern's extra canonical problems (1). Nothing on the site is sold for money: coins can only be earned, never bought.

What is the refund and cancellation policy?

Hi👋SpeedAlgo sells nothing for money: there are no subscriptions, renewals or charges, so there is nothing to cancel or refund. Nothing on the site is sold for money: coins can only be earned, never bought.

Who creates and maintains the curriculum?

Hi👋SpeedAlgo is developed and maintained by Hi👋WebEnterprise (https://hiwebenterprise.com), an engineering organization focused on developer education, deliberate practice methodologies, and cognitive ergonomics for technical interviews.

How does Hi👋SpeedAlgo prepare candidates for senior and staff SWE interviews?

Rather than rote LeetCode grinding, Hi👋SpeedAlgo uses deliberate practice for each pattern: learn the loop invariant, Big-O proof and edge cases from a side-by-side template and a step-by-step debugger, rebuild the template from memory, then solve a new problem on your own against a graded test suite.

Theory Context•Advanced Data Structures

Builds on Flood Fill, which you haven’t finished yet.

P1MediumMental model~7 min speedrun

Union-Find (Disjoint Set Union)

Unlocks

Kruskal's MST

The problem

Redundant Connection (LC 684)(opens leetcode.com)

What a redundant edge means (assume nothing): a tree with n nodes has exactly n - 1 edges and no cycles. Adding one more edge between two nodes that are already connected creates a cycle, and that extra edge is redundant.

A graph on n nodes, labeled 1 through n, started life as a tree (connected, no cycles) and then gained one extra edge, given as an array edges of n pairs [a_i, b_i].

Identify an edge that can be deleted so what remains is again a tree spanning all n nodes. If more than one edge would work, return whichever one appears last in edges.

Example 1

Input:edges = [[1,2],[1,3],[2,3]]

Output:[2,3]

Edges 1-2 and 1-3 already connect 2 and 3, so 2-3 closes the cycle and can be removed.

Union-Find

dynamic edges / sets ➔ find canonical root ➔ flatten tree & merge ranks

Spot it when: Items join groups over time, and you ask whether two are connected, how many groups there are, or which edge first closes a cycle.

Union-Find

Python

1	from typing import List
2
3	class UnionFind:
4	"""Union-Find with path compression and union by size, run on Redundant Connection.
5	Time: O(N · alpha(N)) for N edges, O(alpha(N)) amortized per call \| Space: O(N)
6	"""
7	def __init__(self, n: int):
8	self.parent = list(range(n))
9	self.size = [1] * n
10	self.num_components = n
11
12	def find(self, x: int) -> int:
13	"""Path compression: points traversed nodes directly to root."""
14	root = x
15
16	# 1. Walk Up To The Root:
17	# parent[root] == root only at the root, so climbing parent links from x always ends there.
18	while root != self.parent[root]:
19	root = self.parent[root]
20
21	# 2. Compress The Path:
22	# Repointing every visited node straight at root shortens the next walk from any of them to one step.
23	while x != root:
24	nxt = self.parent[x]
25	self.parent[x] = root
26	x = nxt
27
28	return root
29
30	def union(self, a: int, b: int) -> bool:
31	"""Union by size: hangs smaller tree under larger."""
32	ra, rb = self.find(a), self.find(b)
33
34	# 1. Detect An Already-Closed Group:
35	# Equal roots mean a and b were already connected before this edge, so this edge closes a cycle.
36	if ra == rb:
37	return False # Already connected / cycle detected!
38
39	# 2. Hang The Smaller Tree Under The Larger:
40	# Attaching the smaller tree to the larger root keeps every tree's height small, which keeps find's walk short.
41	if self.size[ra] < self.size[rb]:
42	ra, rb = rb, ra
43
44	self.parent[rb] = ra
45	self.size[ra] += self.size[rb]
46	self.num_components -= 1
47	return True
48
49	def findRedundantConnection(edges: List[List[int]]) -> List[int]:
50	uf = UnionFind(len(edges) + 1) # Nodes are numbered 1..n
51
52	# 1. Union Each Edge, Stopping At The First Cycle:
53	# union returns False only when its two endpoints are already in the same group, which is exactly the edge that closes the first cycle.
54	for a, b in edges:
55	if not uf.union(a, b):
56	return [a, b] # a and b were already connected: this edge closes the cycle
57	return []

Invariant: Following parent from any item always ends at its group's root, and two items are connected exactly when find returns the same root.

Name each group by the root of its tree: find follows parent links up to the root, and union joins two groups by pointing one root at the other. Two items are connected exactly when find returns the same root for both, so union returns False when ra == rb, which is how an edge that closes a cycle is detected. Path compression in find and hanging the smaller tree under the larger (size) keep every tree shallow. The trap is linking the items instead of their roots: always link rb under ra after both find calls, never self.parent[b] = a.

See it run

Union-Find on Redundant Connection, edges = [[1, 2], [3, 4], [2, 3], [5, 4], [1, 5]]

edge none yetcomponents 5

Each circle is an item. An arrow goes from an item to its parent. An item with no arrow is the root of its group.

root the root of a group that find returned
a the first item of the edge
b the second item of the edge
child root the root that moves under the other root
new link a parent link that was just written

Every item starts as its own group, so parent[x] = x for each x. There are 5 groups.

parent[1] to parent[5]

size[1] to size[5]

1 / 13

Gotchas1 of 4

The trap
Gotcha 1: Writing self.parent[b] = a instead of linking the roots
Mistake
```
self.parent[b] = a
```
Fix
```
self.parent[rb] = ra
```
What happens: b may not be a root. Then self.parent[b] = a moves only b into the other group. The rest of b's old group still points at its old root. A later union of the two groups finds two different roots and returns True. So the edge that closes the cycle is missed.
Example: edges = [[1, 2], [3, 2], [1, 3]]
Mistake: returns []Fix: returns [1, 3]
Gotcha 2: Creating UnionFind(len(edges)) for nodes numbered 1 to n
Mistake
```
uf = UnionFind(len(edges))
```
Fix
```
uf = UnionFind(len(edges) + 1)
```
What happens: Redundant Connection (LC 684) numbers its nodes from 1 to n, and n equals len(edges). UnionFind(len(edges)) creates slots 0 to n - 1 only. The first edge that touches node n raises IndexError.
Example: edges = [[1, 2], [1, 3], [2, 3]]
Mistake: raises IndexErrorFix: returns [2, 3]
Gotcha 3: Passing items that are not small integers to union
Mistake
```
uf.union("a@x.com", "b@x.com")
```
Fix
```
ids = {email: i for i, email in enumerate(emails)}
uf.union(ids["a@x.com"], ids["b@x.com"])
```
What happens: self.parent is a list, so find needs an integer index from 0 to n - 1. An email address or a coordinate pair raises TypeError. Give every item an integer id first, or keep parent in a dict.
Example: emails = ["a@x.com", "b@x.com", "c@x.com"]
Mistake: raises TypeErrorFix: returns True
Gotcha 4: Using union-find to find a cycle in a directed graph
Mistake
```
has_cycle = findRedundantConnection(edges) != []
```
Fix
```
has_cycle = has_directed_cycle(edges)  # Kahn's topological sort
```
What happens: Union-find ignores the direction of an edge. The edges 1 -> 2, 1 -> 3 and 2 -> 3 have no directed cycle. Union-find still joins 2 and 3 through 1, so it reports a cycle at 2 -> 3. Use a DFS with three colours or a topological sort instead, as in Course Schedule (LC 207).
Example: directed edges = [[1, 2], [1, 3], [2, 3]]
Mistake: returns TrueFix: returns False

Not this one if…

Links go one way (a key opens a room, not the reverse) and the whole graph is known up front, as in Keys and Rooms (LC 841). See Flood Fill
Nodes must be split into two sides with every edge crossing between them, as in Is Graph Bipartite? (LC 785): whether two nodes are connected is not the question. See Bipartite Check

Deep Dive

Why the root names the group

Union-Find stores each group as a tree. parent[x] is the next item above x. The root is the one item with parent[root] == root.

Every item in a group reaches the same root when it follows parent. So the root works as the name of the group. Two items are in the same group exactly when find returns the same root for both.

Take Redundant Connection (LC 684) with edges = [[1, 2], [3, 4], [2, 3], [5, 4], [1, 5]]. After the first three edges, parent is [1, 1, 1, 3, 5] for items 1 to 5. Items 1, 2, 3 and 4 share root 1, and item 5 is alone.

Edge [5, 4] joins item 5 to that group. Now find(1) and find(5) both return 1. So the last edge [1, 5] makes union return False, because 1 and 5 were already connected. That edge closes a cycle, and the function returns [1, 5].

This is why the card's invariant says that following parent always ends at the group's root. union keeps it true by changing only one value per merge: the parent of one root.

Why union by size and path compression keep find short

find costs one step per level of the tree. If the trees grow tall, find becomes slow. Without a rule, trees do grow tall. Suppose union always puts the first root under the second root. The calls (1, 2), (2, 3), (3, 4) and (4, 5) then build the chain 1, 2, 3, 4, 5. find(1) takes 4 steps. For N items it takes N - 1 steps.

Union by size fixes the shape. union puts the root with the smaller size under the root with the larger size. A node moves down one level only when its tree joins a tree at least as large. So its tree at least doubles each time that happens. A tree of height h therefore has at least 2^h items, and the height is at most log2(N). For 64 items, the height is at most 6.

Path compression works on the walk itself. In find, the second loop sets parent[x] = root for every item on the path. In the example, find(4) climbs 4, 3, 1. It changes parent[4] from 3 to 1. The next find(4) takes one step.

With both rules, the cost of one call is O(alpha(N)) amortized. alpha is the inverse Ackermann function. It grows so slowly that it is at most 4 for any N that can exist in memory. Amortized means the average over a whole sequence of calls. One call can still take longer than the average.

Link roots, never items

union must change the parent of a root. The line self.parent[rb] = ra does this. The line self.parent[b] = a looks the same, but b may be in the middle of a tree.

Example: edges = [[1, 2], [3, 2], [1, 3]]. Edges 1-2, 3-2 and 1-3 form a triangle, so the answer is [1, 3]. With self.parent[b] = a, the first call sets parent[2] = 1. The second call finds roots 3 and 1, so it sets parent[2] = 3. Item 2 leaves the group of item 1. Now 1 and 3 have different roots, so all three calls return True and the function returns [].

The correct code reaches the root of each item first. The second call links root 1 under root 3 (or the other way round). The group stays whole. The third call finds one root for 1 and 3 and returns False.

What Union-Find can and cannot answer

Each union that returns True merges two groups, so it lowers num_components by one. Starting from n items, num_components is the number of groups at any time.

This is enough for Number of Provinces (LC 547), Accounts Merge (LC 721) and Number of Operations to Make Network Connected (LC 1319). In each of them, links are only added and the question is about groups.

The structure cannot remove an edge. If edges are deleted, a group may split in two, and the trees cannot show that. Read the problem in reverse (add the edges back in the opposite order), or use another method.

The card handles undirected edges. Redundant Connection II (LC 685) uses directed edges, where one item can also have two parents. A plain find is not enough there.

60-Second Pitch

"I treat each group as a tree and name the group by its root. find climbs parent to the root and repoints the path at it. union finds both roots. If they are equal, the edge closes a cycle, so I return it. If they differ, I hang the smaller tree under the larger one with size. Union by size keeps every tree at most log N tall, and path compression flattens the paths I use. Together they cost O(alpha(N)) amortized per call. For N edges that is almost O(N) time, with O(N) space for parent and size."

Common Questions

What is the time and space complexity of findRedundantConnection?: O(N * alpha(N)) time for N edges, which is almost linear, and O(N) space for parent and size. Each edge makes one union call, and each call costs O(alpha(N)) amortized. alpha is at most 4 for any N that fits in memory.
Why do you need both union by size and path compression?: Each rule alone gives a good bound, but not the best one. Union by size alone keeps the height at most log2(N). Path compression alone gives O(log N) amortized. Together they give O(alpha(N)) amortized. Both are only a few lines.
How would you solve Redundant Connection (LC 684) without Union-Find?: Before each edge, run a DFS or BFS to test whether its two ends are already connected. If they are, the edge closes a cycle. This costs O(N) per edge, so O(N^2) in total. Union-Find replaces each search with a call that is almost O(1).
How do you count the groups?: Keep num_components. It starts at n. Each union that returns True lowers it by one, because two groups became one. A call that returns False leaves it unchanged.
Can Union-Find undo a union or delete an edge?: Not with path compression. Compression changes many parent values, and there is no record of how to restore them. If deletions are needed, process the operations in reverse order, so that deletions become additions. Otherwise use another method.

SWE Reasoning

Spot it

Links are added over time, and the question is whether two items are connected, or how many groups exist.
You need the first edge that closes a cycle in an undirected graph.
The input is a list of edges, with no need to know the path between two items.
Links are never removed.
A search from each item (DFS or BFS) would repeat the same work for every query.

The invariant, step by step

UnionFind(n) sets parent[x] = x and size[x] = 1. Every item is the root of its own group.
union(a, b) calls find on both items. find climbs parent until root == parent[root], then repoints the items on the path at root.
If ra == rb, the items are in one group already. union returns False and changes nothing.
Otherwise union swaps ra and rb when size[ra] < size[rb], so that ra is the larger tree.
It writes parent[rb] = ra and adds size[rb] to size[ra]. Only the parent of one root changes.
Every item in the old tree of rb now reaches ra, and every other item still reaches its old root. So following parent still ends at the group's root.

Traps

Linking items instead of roots. self.parent[b] = a moves only b out of its group. The rest of the group keeps the old root. A later union can then miss the cycle.
Comparing items instead of roots. if a == b does not test the groups. Compare ra == rb after both find calls.
No union by size. Trees can become chains, and one find can take N - 1 steps.
Updating size of the wrong root. After the swap, add to size[ra]. The larger tree stays the root, and its size must be right for the next comparison.
Wrong array length. Items are numbered 1 to n in Redundant Connection (LC 684). UnionFind(len(edges) + 1) leaves slot 0 unused. UnionFind(len(edges)) raises IndexError for item n.
Using it with deleted edges. The trees cannot split, so the answer becomes wrong after a deletion.

Practice

Canonical LeetCode:Redundant Connection (LC 684)Number of Provinces (LC 547)Accounts Merge (LC 721)Number of Islands II (LC 305)Most Stones Removed with Same Row or Column (LC 947)The Earliest Moment When Everyone Become Friends (LC 1101)Number of Operations to Make Network Connected (LC 1319)Lexicographically Smallest Equivalent String (LC 1061)Redundant Connection II (LC 685)Graph Valid Tree (LC 261)Number of Connected Components in an Undirected Graph (LC 323)Evaluate Division (LC 399)

Theory Context•Advanced Data Structures

Builds on Flood Fill, which you haven’t finished yet.

P1MediumMental model~7 min speedrun

Union-Find (Disjoint Set Union)

Unlocks

Kruskal's MST

The problem

Redundant Connection (LC 684)(opens leetcode.com)

A graph on n nodes, labeled 1 through n, started life as a tree (connected, no cycles) and then gained one extra edge, given as an array edges of n pairs [a_i, b_i].

Identify an edge that can be deleted so what remains is again a tree spanning all n nodes. If more than one edge would work, return whichever one appears last in edges.

Example 1

Input:edges = [[1,2],[1,3],[2,3]]

Output:[2,3]

Edges 1-2 and 1-3 already connect 2 and 3, so 2-3 closes the cycle and can be removed.

Union-Find

dynamic edges / sets ➔ find canonical root ➔ flatten tree & merge ranks

Spot it when: Items join groups over time, and you ask whether two are connected, how many groups there are, or which edge first closes a cycle.

Union-Find

Python

1	from typing import List
2
3	class UnionFind:
4	"""Union-Find with path compression and union by size, run on Redundant Connection.
5	Time: O(N · alpha(N)) for N edges, O(alpha(N)) amortized per call \| Space: O(N)
6	"""
7	def __init__(self, n: int):
8	self.parent = list(range(n))
9	self.size = [1] * n
10	self.num_components = n
11
12	def find(self, x: int) -> int:
13	"""Path compression: points traversed nodes directly to root."""
14	root = x
15
16	# 1. Walk Up To The Root:
17	# parent[root] == root only at the root, so climbing parent links from x always ends there.
18	while root != self.parent[root]:
19	root = self.parent[root]
20
21	# 2. Compress The Path:
22	# Repointing every visited node straight at root shortens the next walk from any of them to one step.
23	while x != root:
24	nxt = self.parent[x]
25	self.parent[x] = root
26	x = nxt
27
28	return root
29
30	def union(self, a: int, b: int) -> bool:
31	"""Union by size: hangs smaller tree under larger."""
32	ra, rb = self.find(a), self.find(b)
33
34	# 1. Detect An Already-Closed Group:
35	# Equal roots mean a and b were already connected before this edge, so this edge closes a cycle.
36	if ra == rb:
37	return False # Already connected / cycle detected!
38
39	# 2. Hang The Smaller Tree Under The Larger:
40	# Attaching the smaller tree to the larger root keeps every tree's height small, which keeps find's walk short.
41	if self.size[ra] < self.size[rb]:
42	ra, rb = rb, ra
43
44	self.parent[rb] = ra
45	self.size[ra] += self.size[rb]
46	self.num_components -= 1
47	return True
48
49	def findRedundantConnection(edges: List[List[int]]) -> List[int]:
50	uf = UnionFind(len(edges) + 1) # Nodes are numbered 1..n
51
52	# 1. Union Each Edge, Stopping At The First Cycle:
53	# union returns False only when its two endpoints are already in the same group, which is exactly the edge that closes the first cycle.
54	for a, b in edges:
55	if not uf.union(a, b):
56	return [a, b] # a and b were already connected: this edge closes the cycle
57	return []

Invariant: Following parent from any item always ends at its group's root, and two items are connected exactly when find returns the same root.

See it run

Union-Find on Redundant Connection, edges = [[1, 2], [3, 4], [2, 3], [5, 4], [1, 5]]

edge none yetcomponents 5

Each circle is an item. An arrow goes from an item to its parent. An item with no arrow is the root of its group.

root the root of a group that find returned
a the first item of the edge
b the second item of the edge
child root the root that moves under the other root
new link a parent link that was just written

Every item starts as its own group, so parent[x] = x for each x. There are 5 groups.

parent[1] to parent[5]

size[1] to size[5]

1 / 13

Gotchas1 of 4

The trap
Gotcha 1: Writing self.parent[b] = a instead of linking the roots
Mistake
```
self.parent[b] = a
```
Fix
```
self.parent[rb] = ra
```
What happens: b may not be a root. Then self.parent[b] = a moves only b into the other group. The rest of b's old group still points at its old root. A later union of the two groups finds two different roots and returns True. So the edge that closes the cycle is missed.
Example: edges = [[1, 2], [3, 2], [1, 3]]
Mistake: returns []Fix: returns [1, 3]
Gotcha 2: Creating UnionFind(len(edges)) for nodes numbered 1 to n
Mistake
```
uf = UnionFind(len(edges))
```
Fix
```
uf = UnionFind(len(edges) + 1)
```
What happens: Redundant Connection (LC 684) numbers its nodes from 1 to n, and n equals len(edges). UnionFind(len(edges)) creates slots 0 to n - 1 only. The first edge that touches node n raises IndexError.
Example: edges = [[1, 2], [1, 3], [2, 3]]
Mistake: raises IndexErrorFix: returns [2, 3]
Gotcha 3: Passing items that are not small integers to union
Mistake
```
uf.union("a@x.com", "b@x.com")
```
Fix
```
ids = {email: i for i, email in enumerate(emails)}
uf.union(ids["a@x.com"], ids["b@x.com"])
```
What happens: self.parent is a list, so find needs an integer index from 0 to n - 1. An email address or a coordinate pair raises TypeError. Give every item an integer id first, or keep parent in a dict.
Example: emails = ["a@x.com", "b@x.com", "c@x.com"]
Mistake: raises TypeErrorFix: returns True
Gotcha 4: Using union-find to find a cycle in a directed graph
Mistake
```
has_cycle = findRedundantConnection(edges) != []
```
Fix
```
has_cycle = has_directed_cycle(edges)  # Kahn's topological sort
```
What happens: Union-find ignores the direction of an edge. The edges 1 -> 2, 1 -> 3 and 2 -> 3 have no directed cycle. Union-find still joins 2 and 3 through 1, so it reports a cycle at 2 -> 3. Use a DFS with three colours or a topological sort instead, as in Course Schedule (LC 207).
Example: directed edges = [[1, 2], [1, 3], [2, 3]]
Mistake: returns TrueFix: returns False

Not this one if…

Links go one way (a key opens a room, not the reverse) and the whole graph is known up front, as in Keys and Rooms (LC 841). See Flood Fill
Nodes must be split into two sides with every edge crossing between them, as in Is Graph Bipartite? (LC 785): whether two nodes are connected is not the question. See Bipartite Check

Deep Dive

Why the root names the group

Union-Find stores each group as a tree. parent[x] is the next item above x. The root is the one item with parent[root] == root.

Every item in a group reaches the same root when it follows parent. So the root works as the name of the group. Two items are in the same group exactly when find returns the same root for both.

This is why the card's invariant says that following parent always ends at the group's root. union keeps it true by changing only one value per merge: the parent of one root.

Why union by size and path compression keep find short

Link roots, never items

union must change the parent of a root. The line self.parent[rb] = ra does this. The line self.parent[b] = a looks the same, but b may be in the middle of a tree.

What Union-Find can and cannot answer

Each union that returns True merges two groups, so it lowers num_components by one. Starting from n items, num_components is the number of groups at any time.

The card handles undirected edges. Redundant Connection II (LC 685) uses directed edges, where one item can also have two parents. A plain find is not enough there.

60-Second Pitch

Common Questions

What is the time and space complexity of findRedundantConnection?: O(N * alpha(N)) time for N edges, which is almost linear, and O(N) space for parent and size. Each edge makes one union call, and each call costs O(alpha(N)) amortized. alpha is at most 4 for any N that fits in memory.
Why do you need both union by size and path compression?: Each rule alone gives a good bound, but not the best one. Union by size alone keeps the height at most log2(N). Path compression alone gives O(log N) amortized. Together they give O(alpha(N)) amortized. Both are only a few lines.
How would you solve Redundant Connection (LC 684) without Union-Find?: Before each edge, run a DFS or BFS to test whether its two ends are already connected. If they are, the edge closes a cycle. This costs O(N) per edge, so O(N^2) in total. Union-Find replaces each search with a call that is almost O(1).
How do you count the groups?: Keep num_components. It starts at n. Each union that returns True lowers it by one, because two groups became one. A call that returns False leaves it unchanged.
Can Union-Find undo a union or delete an edge?: Not with path compression. Compression changes many parent values, and there is no record of how to restore them. If deletions are needed, process the operations in reverse order, so that deletions become additions. Otherwise use another method.

SWE Reasoning

Spot it

Links are added over time, and the question is whether two items are connected, or how many groups exist.
You need the first edge that closes a cycle in an undirected graph.
The input is a list of edges, with no need to know the path between two items.
Links are never removed.
A search from each item (DFS or BFS) would repeat the same work for every query.

The invariant, step by step

UnionFind(n) sets parent[x] = x and size[x] = 1. Every item is the root of its own group.
union(a, b) calls find on both items. find climbs parent until root == parent[root], then repoints the items on the path at root.
If ra == rb, the items are in one group already. union returns False and changes nothing.
Otherwise union swaps ra and rb when size[ra] < size[rb], so that ra is the larger tree.
It writes parent[rb] = ra and adds size[rb] to size[ra]. Only the parent of one root changes.
Every item in the old tree of rb now reaches ra, and every other item still reaches its old root. So following parent still ends at the group's root.

Traps

Linking items instead of roots. self.parent[b] = a moves only b out of its group. The rest of the group keeps the old root. A later union can then miss the cycle.
Comparing items instead of roots. if a == b does not test the groups. Compare ra == rb after both find calls.
No union by size. Trees can become chains, and one find can take N - 1 steps.
Updating size of the wrong root. After the swap, add to size[ra]. The larger tree stays the root, and its size must be right for the next comparison.
Wrong array length. Items are numbered 1 to n in Redundant Connection (LC 684). UnionFind(len(edges) + 1) leaves slot 0 unused. UnionFind(len(edges)) raises IndexError for item n.
Using it with deleted edges. The trees cannot split, so the answer becomes wrong after a deletion.

Practice

Theory Context•Advanced Data Structures

Builds on Flood Fill, which you haven’t finished yet.

P1MediumMental model~7 min speedrun

Union-Find (Disjoint Set Union)

Unlocks

Kruskal's MST

The problem

Redundant Connection (LC 684)(opens leetcode.com)

A graph on n nodes, labeled 1 through n, started life as a tree (connected, no cycles) and then gained one extra edge, given as an array edges of n pairs [a_i, b_i].

Identify an edge that can be deleted so what remains is again a tree spanning all n nodes. If more than one edge would work, return whichever one appears last in edges.

Example 1

Input:edges = [[1,2],[1,3],[2,3]]

Output:[2,3]

Edges 1-2 and 1-3 already connect 2 and 3, so 2-3 closes the cycle and can be removed.

Union-Find

dynamic edges / sets ➔ find canonical root ➔ flatten tree & merge ranks

Spot it when: Items join groups over time, and you ask whether two are connected, how many groups there are, or which edge first closes a cycle.

Union-Find

Python

1	from typing import List
2
3	class UnionFind:
4	"""Union-Find with path compression and union by size, run on Redundant Connection.
5	Time: O(N · alpha(N)) for N edges, O(alpha(N)) amortized per call \| Space: O(N)
6	"""
7	def __init__(self, n: int):
8	self.parent = list(range(n))
9	self.size = [1] * n
10	self.num_components = n
11
12	def find(self, x: int) -> int:
13	"""Path compression: points traversed nodes directly to root."""
14	root = x
15
16	# 1. Walk Up To The Root:
17	# parent[root] == root only at the root, so climbing parent links from x always ends there.
18	while root != self.parent[root]:
19	root = self.parent[root]
20
21	# 2. Compress The Path:
22	# Repointing every visited node straight at root shortens the next walk from any of them to one step.
23	while x != root:
24	nxt = self.parent[x]
25	self.parent[x] = root
26	x = nxt
27
28	return root
29
30	def union(self, a: int, b: int) -> bool:
31	"""Union by size: hangs smaller tree under larger."""
32	ra, rb = self.find(a), self.find(b)
33
34	# 1. Detect An Already-Closed Group:
35	# Equal roots mean a and b were already connected before this edge, so this edge closes a cycle.
36	if ra == rb:
37	return False # Already connected / cycle detected!
38
39	# 2. Hang The Smaller Tree Under The Larger:
40	# Attaching the smaller tree to the larger root keeps every tree's height small, which keeps find's walk short.
41	if self.size[ra] < self.size[rb]:
42	ra, rb = rb, ra
43
44	self.parent[rb] = ra
45	self.size[ra] += self.size[rb]
46	self.num_components -= 1
47	return True
48
49	def findRedundantConnection(edges: List[List[int]]) -> List[int]:
50	uf = UnionFind(len(edges) + 1) # Nodes are numbered 1..n
51
52	# 1. Union Each Edge, Stopping At The First Cycle:
53	# union returns False only when its two endpoints are already in the same group, which is exactly the edge that closes the first cycle.
54	for a, b in edges:
55	if not uf.union(a, b):
56	return [a, b] # a and b were already connected: this edge closes the cycle
57	return []

Invariant: Following parent from any item always ends at its group's root, and two items are connected exactly when find returns the same root.

See it run

Union-Find on Redundant Connection, edges = [[1, 2], [3, 4], [2, 3], [5, 4], [1, 5]]

edge none yetcomponents 5

Each circle is an item. An arrow goes from an item to its parent. An item with no arrow is the root of its group.

root the root of a group that find returned
a the first item of the edge
b the second item of the edge
child root the root that moves under the other root
new link a parent link that was just written

Every item starts as its own group, so parent[x] = x for each x. There are 5 groups.

parent[1] to parent[5]

size[1] to size[5]

1 / 13

Gotchas1 of 4

The trap
Gotcha 1: Writing self.parent[b] = a instead of linking the roots
Mistake
```
self.parent[b] = a
```
Fix
```
self.parent[rb] = ra
```
What happens: b may not be a root. Then self.parent[b] = a moves only b into the other group. The rest of b's old group still points at its old root. A later union of the two groups finds two different roots and returns True. So the edge that closes the cycle is missed.
Example: edges = [[1, 2], [3, 2], [1, 3]]
Mistake: returns []Fix: returns [1, 3]
Gotcha 2: Creating UnionFind(len(edges)) for nodes numbered 1 to n
Mistake
```
uf = UnionFind(len(edges))
```
Fix
```
uf = UnionFind(len(edges) + 1)
```
What happens: Redundant Connection (LC 684) numbers its nodes from 1 to n, and n equals len(edges). UnionFind(len(edges)) creates slots 0 to n - 1 only. The first edge that touches node n raises IndexError.
Example: edges = [[1, 2], [1, 3], [2, 3]]
Mistake: raises IndexErrorFix: returns [2, 3]
Gotcha 3: Passing items that are not small integers to union
Mistake
```
uf.union("a@x.com", "b@x.com")
```
Fix
```
ids = {email: i for i, email in enumerate(emails)}
uf.union(ids["a@x.com"], ids["b@x.com"])
```
What happens: self.parent is a list, so find needs an integer index from 0 to n - 1. An email address or a coordinate pair raises TypeError. Give every item an integer id first, or keep parent in a dict.
Example: emails = ["a@x.com", "b@x.com", "c@x.com"]
Mistake: raises TypeErrorFix: returns True
Gotcha 4: Using union-find to find a cycle in a directed graph
Mistake
```
has_cycle = findRedundantConnection(edges) != []
```
Fix
```
has_cycle = has_directed_cycle(edges)  # Kahn's topological sort
```
What happens: Union-find ignores the direction of an edge. The edges 1 -> 2, 1 -> 3 and 2 -> 3 have no directed cycle. Union-find still joins 2 and 3 through 1, so it reports a cycle at 2 -> 3. Use a DFS with three colours or a topological sort instead, as in Course Schedule (LC 207).
Example: directed edges = [[1, 2], [1, 3], [2, 3]]
Mistake: returns TrueFix: returns False

Not this one if…

Links go one way (a key opens a room, not the reverse) and the whole graph is known up front, as in Keys and Rooms (LC 841). See Flood Fill
Nodes must be split into two sides with every edge crossing between them, as in Is Graph Bipartite? (LC 785): whether two nodes are connected is not the question. See Bipartite Check

Deep Dive

Why the root names the group

Union-Find stores each group as a tree. parent[x] is the next item above x. The root is the one item with parent[root] == root.

Every item in a group reaches the same root when it follows parent. So the root works as the name of the group. Two items are in the same group exactly when find returns the same root for both.

This is why the card's invariant says that following parent always ends at the group's root. union keeps it true by changing only one value per merge: the parent of one root.

Why union by size and path compression keep find short

Link roots, never items

union must change the parent of a root. The line self.parent[rb] = ra does this. The line self.parent[b] = a looks the same, but b may be in the middle of a tree.

What Union-Find can and cannot answer

Each union that returns True merges two groups, so it lowers num_components by one. Starting from n items, num_components is the number of groups at any time.

The card handles undirected edges. Redundant Connection II (LC 685) uses directed edges, where one item can also have two parents. A plain find is not enough there.

60-Second Pitch

Common Questions

What is the time and space complexity of findRedundantConnection?: O(N * alpha(N)) time for N edges, which is almost linear, and O(N) space for parent and size. Each edge makes one union call, and each call costs O(alpha(N)) amortized. alpha is at most 4 for any N that fits in memory.
Why do you need both union by size and path compression?: Each rule alone gives a good bound, but not the best one. Union by size alone keeps the height at most log2(N). Path compression alone gives O(log N) amortized. Together they give O(alpha(N)) amortized. Both are only a few lines.
How would you solve Redundant Connection (LC 684) without Union-Find?: Before each edge, run a DFS or BFS to test whether its two ends are already connected. If they are, the edge closes a cycle. This costs O(N) per edge, so O(N^2) in total. Union-Find replaces each search with a call that is almost O(1).
How do you count the groups?: Keep num_components. It starts at n. Each union that returns True lowers it by one, because two groups became one. A call that returns False leaves it unchanged.
Can Union-Find undo a union or delete an edge?: Not with path compression. Compression changes many parent values, and there is no record of how to restore them. If deletions are needed, process the operations in reverse order, so that deletions become additions. Otherwise use another method.

SWE Reasoning

Spot it

Links are added over time, and the question is whether two items are connected, or how many groups exist.
You need the first edge that closes a cycle in an undirected graph.
The input is a list of edges, with no need to know the path between two items.
Links are never removed.
A search from each item (DFS or BFS) would repeat the same work for every query.

The invariant, step by step

UnionFind(n) sets parent[x] = x and size[x] = 1. Every item is the root of its own group.
union(a, b) calls find on both items. find climbs parent until root == parent[root], then repoints the items on the path at root.
If ra == rb, the items are in one group already. union returns False and changes nothing.
Otherwise union swaps ra and rb when size[ra] < size[rb], so that ra is the larger tree.
It writes parent[rb] = ra and adds size[rb] to size[ra]. Only the parent of one root changes.
Every item in the old tree of rb now reaches ra, and every other item still reaches its old root. So following parent still ends at the group's root.

Traps

Linking items instead of roots. self.parent[b] = a moves only b out of its group. The rest of the group keeps the old root. A later union can then miss the cycle.
Comparing items instead of roots. if a == b does not test the groups. Compare ra == rb after both find calls.
No union by size. Trees can become chains, and one find can take N - 1 steps.
Updating size of the wrong root. After the swap, add to size[ra]. The larger tree stays the root, and its size must be right for the next comparison.
Wrong array length. Items are numbered 1 to n in Redundant Connection (LC 684). UnionFind(len(edges) + 1) leaves slot 0 unused. UnionFind(len(edges)) raises IndexError for item n.
Using it with deleted edges. The trees cannot split, so the answer becomes wrong after a deletion.

Practice

Theory Context•Advanced Data Structures

Builds on Flood Fill, which you haven’t finished yet.

P1MediumMental model~7 min speedrun

Union-Find (Disjoint Set Union)

Unlocks

Kruskal's MST

The problem

Redundant Connection (LC 684)(opens leetcode.com)

A graph on n nodes, labeled 1 through n, started life as a tree (connected, no cycles) and then gained one extra edge, given as an array edges of n pairs [a_i, b_i].

Identify an edge that can be deleted so what remains is again a tree spanning all n nodes. If more than one edge would work, return whichever one appears last in edges.

Example 1

Input:edges = [[1,2],[1,3],[2,3]]

Output:[2,3]

Edges 1-2 and 1-3 already connect 2 and 3, so 2-3 closes the cycle and can be removed.

Union-Find

dynamic edges / sets ➔ find canonical root ➔ flatten tree & merge ranks

Spot it when: Items join groups over time, and you ask whether two are connected, how many groups there are, or which edge first closes a cycle.

Union-Find

Python

1	from typing import List
2
3	class UnionFind:
4	"""Union-Find with path compression and union by size, run on Redundant Connection.
5	Time: O(N · alpha(N)) for N edges, O(alpha(N)) amortized per call \| Space: O(N)
6	"""
7	def __init__(self, n: int):
8	self.parent = list(range(n))
9	self.size = [1] * n
10	self.num_components = n
11
12	def find(self, x: int) -> int:
13	"""Path compression: points traversed nodes directly to root."""
14	root = x
15
16	# 1. Walk Up To The Root:
17	# parent[root] == root only at the root, so climbing parent links from x always ends there.
18	while root != self.parent[root]:
19	root = self.parent[root]
20
21	# 2. Compress The Path:
22	# Repointing every visited node straight at root shortens the next walk from any of them to one step.
23	while x != root:
24	nxt = self.parent[x]
25	self.parent[x] = root
26	x = nxt
27
28	return root
29
30	def union(self, a: int, b: int) -> bool:
31	"""Union by size: hangs smaller tree under larger."""
32	ra, rb = self.find(a), self.find(b)
33
34	# 1. Detect An Already-Closed Group:
35	# Equal roots mean a and b were already connected before this edge, so this edge closes a cycle.
36	if ra == rb:
37	return False # Already connected / cycle detected!
38
39	# 2. Hang The Smaller Tree Under The Larger:
40	# Attaching the smaller tree to the larger root keeps every tree's height small, which keeps find's walk short.
41	if self.size[ra] < self.size[rb]:
42	ra, rb = rb, ra
43
44	self.parent[rb] = ra
45	self.size[ra] += self.size[rb]
46	self.num_components -= 1
47	return True
48
49	def findRedundantConnection(edges: List[List[int]]) -> List[int]:
50	uf = UnionFind(len(edges) + 1) # Nodes are numbered 1..n
51
52	# 1. Union Each Edge, Stopping At The First Cycle:
53	# union returns False only when its two endpoints are already in the same group, which is exactly the edge that closes the first cycle.
54	for a, b in edges:
55	if not uf.union(a, b):
56	return [a, b] # a and b were already connected: this edge closes the cycle
57	return []

Invariant: Following parent from any item always ends at its group's root, and two items are connected exactly when find returns the same root.

See it run

Union-Find on Redundant Connection, edges = [[1, 2], [3, 4], [2, 3], [5, 4], [1, 5]]

edge none yetcomponents 5

Each circle is an item. An arrow goes from an item to its parent. An item with no arrow is the root of its group.

root the root of a group that find returned
a the first item of the edge
b the second item of the edge
child root the root that moves under the other root
new link a parent link that was just written

Every item starts as its own group, so parent[x] = x for each x. There are 5 groups.

parent[1] to parent[5]

size[1] to size[5]

1 / 13

Gotchas1 of 4

The trap
Gotcha 1: Writing self.parent[b] = a instead of linking the roots
Mistake
```
self.parent[b] = a
```
Fix
```
self.parent[rb] = ra
```
What happens: b may not be a root. Then self.parent[b] = a moves only b into the other group. The rest of b's old group still points at its old root. A later union of the two groups finds two different roots and returns True. So the edge that closes the cycle is missed.
Example: edges = [[1, 2], [3, 2], [1, 3]]
Mistake: returns []Fix: returns [1, 3]
Gotcha 2: Creating UnionFind(len(edges)) for nodes numbered 1 to n
Mistake
```
uf = UnionFind(len(edges))
```
Fix
```
uf = UnionFind(len(edges) + 1)
```
What happens: Redundant Connection (LC 684) numbers its nodes from 1 to n, and n equals len(edges). UnionFind(len(edges)) creates slots 0 to n - 1 only. The first edge that touches node n raises IndexError.
Example: edges = [[1, 2], [1, 3], [2, 3]]
Mistake: raises IndexErrorFix: returns [2, 3]
Gotcha 3: Passing items that are not small integers to union
Mistake
```
uf.union("a@x.com", "b@x.com")
```
Fix
```
ids = {email: i for i, email in enumerate(emails)}
uf.union(ids["a@x.com"], ids["b@x.com"])
```
What happens: self.parent is a list, so find needs an integer index from 0 to n - 1. An email address or a coordinate pair raises TypeError. Give every item an integer id first, or keep parent in a dict.
Example: emails = ["a@x.com", "b@x.com", "c@x.com"]
Mistake: raises TypeErrorFix: returns True
Gotcha 4: Using union-find to find a cycle in a directed graph
Mistake
```
has_cycle = findRedundantConnection(edges) != []
```
Fix
```
has_cycle = has_directed_cycle(edges)  # Kahn's topological sort
```
What happens: Union-find ignores the direction of an edge. The edges 1 -> 2, 1 -> 3 and 2 -> 3 have no directed cycle. Union-find still joins 2 and 3 through 1, so it reports a cycle at 2 -> 3. Use a DFS with three colours or a topological sort instead, as in Course Schedule (LC 207).
Example: directed edges = [[1, 2], [1, 3], [2, 3]]
Mistake: returns TrueFix: returns False

Not this one if…

Links go one way (a key opens a room, not the reverse) and the whole graph is known up front, as in Keys and Rooms (LC 841). See Flood Fill
Nodes must be split into two sides with every edge crossing between them, as in Is Graph Bipartite? (LC 785): whether two nodes are connected is not the question. See Bipartite Check

Deep Dive

Why the root names the group

Union-Find stores each group as a tree. parent[x] is the next item above x. The root is the one item with parent[root] == root.

Every item in a group reaches the same root when it follows parent. So the root works as the name of the group. Two items are in the same group exactly when find returns the same root for both.

This is why the card's invariant says that following parent always ends at the group's root. union keeps it true by changing only one value per merge: the parent of one root.

Why union by size and path compression keep find short

Link roots, never items

union must change the parent of a root. The line self.parent[rb] = ra does this. The line self.parent[b] = a looks the same, but b may be in the middle of a tree.

What Union-Find can and cannot answer

Each union that returns True merges two groups, so it lowers num_components by one. Starting from n items, num_components is the number of groups at any time.

The card handles undirected edges. Redundant Connection II (LC 685) uses directed edges, where one item can also have two parents. A plain find is not enough there.

60-Second Pitch

Common Questions

What is the time and space complexity of findRedundantConnection?: O(N * alpha(N)) time for N edges, which is almost linear, and O(N) space for parent and size. Each edge makes one union call, and each call costs O(alpha(N)) amortized. alpha is at most 4 for any N that fits in memory.
Why do you need both union by size and path compression?: Each rule alone gives a good bound, but not the best one. Union by size alone keeps the height at most log2(N). Path compression alone gives O(log N) amortized. Together they give O(alpha(N)) amortized. Both are only a few lines.
How would you solve Redundant Connection (LC 684) without Union-Find?: Before each edge, run a DFS or BFS to test whether its two ends are already connected. If they are, the edge closes a cycle. This costs O(N) per edge, so O(N^2) in total. Union-Find replaces each search with a call that is almost O(1).
How do you count the groups?: Keep num_components. It starts at n. Each union that returns True lowers it by one, because two groups became one. A call that returns False leaves it unchanged.
Can Union-Find undo a union or delete an edge?: Not with path compression. Compression changes many parent values, and there is no record of how to restore them. If deletions are needed, process the operations in reverse order, so that deletions become additions. Otherwise use another method.

SWE Reasoning

Spot it

Links are added over time, and the question is whether two items are connected, or how many groups exist.
You need the first edge that closes a cycle in an undirected graph.
The input is a list of edges, with no need to know the path between two items.
Links are never removed.
A search from each item (DFS or BFS) would repeat the same work for every query.

The invariant, step by step

UnionFind(n) sets parent[x] = x and size[x] = 1. Every item is the root of its own group.
union(a, b) calls find on both items. find climbs parent until root == parent[root], then repoints the items on the path at root.
If ra == rb, the items are in one group already. union returns False and changes nothing.
Otherwise union swaps ra and rb when size[ra] < size[rb], so that ra is the larger tree.
It writes parent[rb] = ra and adds size[rb] to size[ra]. Only the parent of one root changes.
Every item in the old tree of rb now reaches ra, and every other item still reaches its old root. So following parent still ends at the group's root.

Traps

Linking items instead of roots. self.parent[b] = a moves only b out of its group. The rest of the group keeps the old root. A later union can then miss the cycle.
Comparing items instead of roots. if a == b does not test the groups. Compare ra == rb after both find calls.
No union by size. Trees can become chains, and one find can take N - 1 steps.
Updating size of the wrong root. After the swap, add to size[ra]. The larger tree stays the root, and its size must be right for the next comparison.
Wrong array length. Items are numbered 1 to n in Redundant Connection (LC 684). UnionFind(len(edges) + 1) leaves slot 0 unused. UnionFind(len(edges)) raises IndexError for item n.
Using it with deleted edges. The trees cannot split, so the answer becomes wrong after a deletion.