LeetCode 684 ·
Medium
Redundant Connection
In a graph that is a tree plus one extra edge, return that extra edge.
Try it
Step through the core mechanic. The simulator below runs the union-find shape this problem is built on.
Walk the pattern
No dedicated step-through for this one yet. The shape is Union-Find — its pattern page has the interactive walkthrough, the reference implementation, and a five-problem progression that this problem sits inside.
The approach
Union-Find: process edges, union the endpoints. The first edge whose endpoints already share a root is the one completing a cycle — the redundant edge. Path compression keeps it near O(1) per op.
| Aspect | Value |
|---|---|
| Pattern | Union-Find |
| Recognise it by | The edge that closes a cycle in a tree-plus-one. |
| Time complexity | O(n·α) |
| Space complexity | O(n) |
| Difficulty | Medium |
Who asks it
Companies known to ask this problem, from public LeetCode company-tag aggregations. A signal of where to expect it, not a guarantee.