Problem overview
A tree is a connected undirected graph with no cycle. You start with a tree of n nodes numbered 1 to n and one extra edge joins two nodes that weren't directly joined before. The function findRedundantConnection(edges) receives the resulting n edges as pairs [a, b] and returns an edge whose removal leaves a tree. When several edges would work, it returns the one that comes last in edges.
For [[1,2],[1,3],[2,3]] the three edges form the cycle 1 - 2 - 3 - 1. Removing any of them leaves a tree, and [2,3] comes last, so that is the answer. For [[1,2],[2,3],[3,4],[1,4],[1,5]] the cycle is 1 - 2 - 3 - 4 - 1, and [1,4] is its last edge. The edge [1,5] comes after it in the input, but it isn't on the cycle: removing it would cut node 5 off from the others.
Approach: add edges one by one and watch for a cycle
One way is to try the edges from the last one back, remove each and check with a DFS whether the rest is still connected. That costs O(n²). A better idea uses union-find (also called disjoint sets), which keeps track of which nodes are already connected.
Union-find stores each group of connected nodes as a small tree: every node points to a parent, and the root, the one node that is its own parent, names the group. Two nodes are in the same group exactly when they lead to the same root.
Add the edges in the order they are given. For an edge [a, b], find the roots of a and b. If the roots differ, the edge joins two groups, so merge them. If the roots are equal, a and b are already connected through earlier edges, and this edge closes a cycle.
The graph has exactly one cycle, and the edge that closes it is the one that comes last among the cycle's edges, since all the others were added before. That is the edge to return. It is also the right answer when other edges follow it in the input, because those edges are not on the cycle.
Two standard tricks keep the trees shallow: union by size (the smaller tree goes under the larger one) and path halving (while walking up, each node skips to its grandparent). Together they make each operation cost O(α(n)) amortized, where α is the inverse Ackermann function, which stays below 5 for any n a computer can hold.
Step by step
- Store
nasedges.length. A tree ofnnodes hasn - 1edges, and the extra one makesn, so the edge count is also the node count. - Create
parentwithArray.from({length: n + 1}, (_, i) => i), so every node starts as its own parent. Nodes are numbered from 1, so there aren + 1entries and index 0 is unused. - Create
sizeasnew Array(n + 1).fill(1). The entry of a root counts the nodes in its group. - Loop over the edges with
for (const edge of edges), in the given order. - Find the root of
edge[0]withthis.find(parent, edge[0]), in a variablerootAdeclared withlet, since it may be swapped. - Find the root of
edge[1]intorootBthe same way. - Detect the cycle: if
rootA === rootB, returnedge. - Make
rootAthe larger group's root: ifsize[rootA] < size[rootB], swap them with[rootA, rootB] = [rootB, rootA]. - Merge:
parent[rootB] = rootA. - Update the size:
size[rootA] += size[rootB]. The entry ofrootBis never read again. - Return
[]after the loop. The input always has an extra edge, so the loop returns before it ends, but the function must return a value on every path. - Write the helper
find(parent, x)in the class. It returns the root ofx's group. - Walk up while
parent[x] !== x. A loop needs no call stack, however long the walk is. - Halve the path:
parent[x] = parent[parent[x]]. - Move up:
x = parent[x], to the grandparent it now points to. - Return
x, the root.
The solution in JavaScript
class Solution {
findRedundantConnection(edges) {
const n = edges.length;
const parent = Array.from({length: n + 1}, (_, i) => i);
const size = new Array(n + 1).fill(1);
for (const edge of edges) {
let rootA = this.find(parent, edge[0]);
let rootB = this.find(parent, edge[1]);
if (rootA === rootB) {
return edge;
}
if (size[rootA] < size[rootB]) {
[rootA, rootB] = [rootB, rootA];
}
parent[rootB] = rootA;
size[rootA] += size[rootB];
}
return [];
}
find(parent, x) {
while (parent[x] !== x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
}
JavaScript details to watch:
Array.from({length: n + 1}, fn)builds an array from an array-like object that has only a length. The function gets the value (unused, so it is named_) and the index, and what it returns becomes the element.- Destructuring swap.
[rootA, rootB] = [rootB, rootA]builds a temporary array and unpacks it, which swaps the two variables without a third one. That is why they arelet, notconst. - Arrays are shared.
findreceives the sameparentarray, so its changes (path halving) are visible to the caller. - The returned edge is the input's own array.
return edgegives back the pair fromedges, not a copy, which is fine for reading it. - Assigning to the parameter.
x = parent[x]changes only the local variablex, not the caller's value.
Trace on [[1,2],[3,4],[2,3],[4,5],[1,5]]
For each edge, the table shows the two roots after the optional swap (larger group first), then parent and size after the merge. Index 0 is unused.
[1,2] roots 1 2 -> parent [0,1,1,3,4,5] size [1,2,1,1,1,1]
[3,4] roots 3 4 -> parent [0,1,1,3,3,5] size [1,2,1,2,1,1]
[2,3] roots 1 3 -> parent [0,1,1,1,3,5] size [1,4,1,2,1,1]
[4,5] roots 1 5 -> parent [0,1,1,1,1,1] size [1,5,1,2,1,1]
[1,5] roots 1 1 -> same group: cycle
The edge [2,3] joins the groups {1,2} and {3,4} because the nodes were seen already but in different groups. The last edge [1,5] finds both ends under root 1, so it closes the cycle 1 - 2 - 3 - 4 - 5 - 1 and is returned. In the last two rows the entry for node 4 changed to 1 even though no edge merged it directly: finding the root of node 4 halved its path.
Complexity
Time: O(n · α(n)), nearly O(n). Each of the n edges costs two find calls and a constant amount of other work, and with union by size plus path halving each find is O(α(n)) amortized.
Space: O(n) for the parent and size arrays.
Edge cases and common mistakes
- Returning the last edge of the input. For
[[1,2],[2,3],[3,4],[1,4],[1,5]]that gives[1,5], which is not on the cycle. The correct answer is[1,4]. - A cycle through a hub. In
[[1,2],[1,3],[1,4],[3,4]]the answer is[3,4], found when the second path to node 4 appears. - Array size. Nodes start at 1, so the arrays need
n + 1entries. With onlyn, nodenwould have no entry. - Comparing nodes instead of roots. The test is on the roots. Checking
edge[0] === edge[1]never fires, because an edge joins two different nodes. - Skipping union by size. The answer is still correct (the answer for the trace input is unchanged), but the trees can get deeper and the time guarantee weakens.
- The smallest case.
[[1,2],[2,3],[1,3]]gives[1,3]. - A long chain. For 999 edges
[i, i+1]followed by[1,1000], the answer is[1,1000]. The iterativefindhas no recursion to overflow.
Testing
[[1,2],[1,3],[2,3]]gives[2,3].[[1,2],[2,3],[3,4],[1,4],[1,5]]gives[1,4].[[1,2],[3,4],[2,3],[4,5],[1,5]]gives[1,5].[[1,2],[1,3],[1,4],[3,4]]gives[3,4].[[1,2],[2,3],[3,4],[4,5],[2,5]]gives[2,5].
