Start with a tree of n nodes and n − 1 edges, then add one extra edge. Return the edge that can be removed to make it a tree again. If several would work, return the one that appears last in the input.
A tree with n nodes has exactly n − 1 edges and no cycles. Adding one edge creates exactly one cycle, and the redundant edge is any edge on that cycle.
Process the edges in order. For each one, ask:
Are these two nodes already connected?
If not, this edge joins two separate groups — keep it. If they already are, this edge closes a cycle, and since you are processing in order, it is the last edge that could have done so. Return it.
"Are these two connected, given edges arriving one at a time" is precisely what union-find answers.
Each group has a representative. find(x) walks up to x's representative; union(a, b) makes one representative point at the other, merging the groups.
Two nodes are in the same group exactly when find(a) == find(b).
Two optimisations make it effectively constant time, and both are one line:
Path compression — while walking up in find, point each node directly at the representative, so the next walk is instant.
Union by size — always attach the smaller tree under the larger one, so the trees stay shallow.
With both, each operation costs O(\alpha(n)), where \alpha is the inverse Ackermann function. It is below 5 for any input that fits in the universe, so treat it as constant — and say it that way rather than claiming exactly O(1).
class Solution: def findRedundantConnection(self, edges: List[List[int]]) -> List[int]: n = len(edges) parent = list(range(n + 1)) # (1) nodes are 1-indexed size = [1] * (n + 1) # (2) def find(x: int) -> int: # (3) while parent[x] != x: # (4) parent[x] = parent[parent[x]] # (5) path compression x = parent[x] return x # (6) def union(a: int, b: int) -> bool: # (7) ra, rb = find(a), find(b) if ra == rb: # (8) return False # already connected → a cycle if size[ra] < size[rb]: # (9) ra, rb = rb, ra # attach smaller under larger parent[rb] = ra # (10) size[ra] += size[rb] return True for a, b in edges: # (11) if not union(a, b): # (12) return [a, b] return []
ts
function findRedundantConnection(edges: number[][]): number[] { const n = edges.length; const parent = Array.from({ length: n + 1 }, (_, i) => i); // (1) const size = new Array(n + 1).fill(1); // (2) function find(x: number): number { // (3) while (parent[x] !== x) { // (4) parent[x] = parent[parent[x]]; // (5) x = parent[x]; } return x; // (6) } function union(a: number, b: number): boolean { // (7) let ra = find(a), rb = find(b); if (ra === rb) return false; // (8) if (size[ra] < size[rb]) [ra, rb] = [rb, ra]; // (9) parent[rb] = ra; // (10) size[ra] += size[rb]; return true; } for (const [a, b] of edges) { // (11) if (!union(a, b)) return [a, b]; // (12) } return [];}
parent[x] = parent[parent[x]] is path halving, a one-line version of path compression that points each node at its grandparent as you climb. It is nearly as effective as the full two-pass version and much shorter.
union returns False when the nodes were already connected, which is exactly the cycle signal. Returning a boolean from union rather than checking find separately keeps the loop to one line.
Processing edges in input order is what satisfies "return the last one that could be removed". The first edge that closes a cycle is the last removable one, because every earlier edge was needed to build up the components.
n + 1 slots because nodes are numbered from 1. Off-by-one here is a silent index error.
(1) parent[x] is the node that x points to. Each group of connected nodes forms a little tree, and the node at the top of the tree, which points to itself, is the group's root. At the start, every node points to itself, so every node is its own group. The list has n + 1 slots because the nodes are numbered from 1, not 0.
(2) size[r] is how many nodes are in the group whose root is r.
(3) find(x) returns the root of x's group. Two nodes are in the same group exactly when they have the same root.
(4) Climb until we reach a node that points to itself.
(5) On the way, make each node point to its grandparent. This shortcut is called path compression. It makes the trees flatter every time find runs, so later climbs are shorter.
(6) The root.
(7) union(a, b) joins the groups of a and b. It returns False if they were already in the same group.
(8) Same root, so a and b are already connected. Adding an edge between them would close a loop. That is the edge the problem asks for.
(9) Put the smaller group under the bigger one. This keeps the trees short. Together with line (5), it makes each find almost constant time.
(10) Join the two groups, and add the smaller group's size to the bigger one's.
(11) Add the edges one by one, in the order given.
(12) The first edge that joins two already-connected nodes is the extra edge. Because we go in order, it is also the last such edge in the list, which is what the problem wants when several answers are possible.
Imagine people showing up to a party. Every person is initially their own "boss". When edge [1,2] arrives, person 1 and person 2 become friends. We assign one to be the "boss" of the friend group. (Let's say 1 is the boss of 2). When [1,3] arrives, we check: Who is 1's boss? (1). Who is 3's boss? (3). They have different bosses, meaning they weren't in the same friend group. Now they merge. 3 accepts 1 as the boss. When [2,3] arrives, we check: Who is 2's boss? (1). Who is 3's boss? (1). They already have the same boss! This means they are already in the same friend group. Making them friends doesn't connect anyone new; it just creates a redundant connection (a circle).
The extra edge closes a loop of three, like edges 1–2, 2–3, 1–3. The third edge finds 1 and 3 already joined.
Several edges could be removed. The problem wants the one that appears last. Adding edges in order and returning the first that closes a loop gives exactly that, because every earlier edge was needed to build the tree.
O(n \cdot \alpha(n)), effectively O(n). O(n) space. To break it down: we process each of the N edges exactly once. For each edge, we do a find and possibly a union. Thanks to path compression and union by size, the find operation climbs a maximally flattened tree. The inverse Ackermann function \alpha(n) is a mathematical function that grows so slowly it is \le 5 for any realistic input size. Thus, each edge takes effectively O(1) time, yielding O(N) overall time. The parent and size arrays each take exactly N+1 slots, giving O(N) space.
You could, for each edge, remove it and check whether the graph is still connected — O(n^2). Or DFS from scratch to find the cycle and then pick the last of its edges from the input, which is O(n) but fiddlier.
Union-find is the right tool because the edges arrive one at a time and the question is asked after each one. That is the exact situation it is built for, and it is the distinction worth carrying:
All the edges up front, one query → DFS or BFS is simpler.
Number of Connected Components — union everything, then count the distinct representatives. 4.20.11.
Graph Valid Tree — connected and exactly n − 1 edges. 4.20.12.
Kruskal's minimum spanning tree — sort the edges by weight and add each one whose endpoints are not already connected. That "already connected?" check is this union returning False. 4.21.
Accounts Merge, Number of Islands II, Most Stones Removed — all union-find.
Redundant Connection II (LeetCode 685) is the directed version, and it is much harder. The extra edge may create a node with two parents, a cycle, or both, and the three cases need separate handling. Know that it exists.
"Why union-find rather than DFS?" Edges arrive one at a time and connectivity is queried after each.
"What is the complexity of union-find?"O(\alpha(n)) amortized with both optimisations, effectively constant. Say "effectively", not "exactly".
"What are the two optimisations and what does each fix?" Path compression flattens the tree during find; union by size stops a tall tree forming during union. Without both, the worst case is O(n) per operation.
"Why does returning the first cycle-closing edge give the last removable one?" Every earlier edge was needed to build the components, so the first one to close a cycle is the last one that can be dropped.
"What if the graph were directed?" A different problem — Redundant Connection II, with three cases.
One thing to volunteer: state the tree fact first. "A tree has n − 1 edges and no cycle, so one extra edge creates exactly one cycle, and any edge on it is removable." That framing makes the union-find choice obvious.