Union-Find — Redundant Connection
↗ LeetCode: Redundant Connection · Medium · pattern chapter →
Asked atGoogleAmazonMeta
Given an undirected graph that starts as a tree with n nodes and has one extra edge added, return that redundant edge.
Example 1 — edges=[[1,2],[1,3],[2,3]] → [2,3]Example 2 — edges=[[1,2],[2,3],[3,4],[1,4],[1,5]] → [1,4]
Constraints — 3 ≤ n ≤ 1000; edges.length == n. Brute DFS-per-edge to check for a cycle is O(E²) = 10⁶ ops at E=10³. Union-Find incremental cycle detection is O(E·α(V)) = 10³ ops — the edge that closes a component is the answer.
Progressive Hints
Try to solve it yourself first. Reveal hints only when stuck — each hint is progressively more specific.
Interview timer00:00
Practice under interview pressure. Start when you begin reading; stop when you finish. Save best only when you had a full working solution.
Target for interview: Medium = 20-25 min · Hard = 30-40 min · Best time persists on this device only.
Approach 1 — DFS to detect cycle for each edge
Try removing each edge; DFS to check connectivity. O(n²).
Approach 2 — Union-Find (canonical)
Insight. Process edges in order. First edge whose endpoints already share a root would create a cycle — that's the redundant one.
java
int[] findRedundantConnection(int[][] edges) {
int n = edges.length;
int[] parent = new int[n + 1];
for (int i = 0; i <= n; i++) parent[i] = i;
for (int[] e : edges) {
int ra = find(parent, e[0]), rb = find(parent, e[1]);
if (ra == rb) return e;
parent[ra] = rb;
}
return new int[0];
}
int find(int[] p, int x) { return p[x] == x ? x : (p[x] = find(p, p[x])); }Execution Trace
Complexity — Time O(n · α(n)); Space O(n).
Try it yourself
Complexity summary
| Approach | Time | Space | Grade |
|---|---|---|---|
| DFS check per edge | O(n²) | O(n) | baseline |
| Union-Find | O(n · α(n)) | O(n) | canonical |
When to use which
- Undirected cycle detection with edges processed in order → Union-Find.
- Directed variant (LC 685) → more complex — need to handle 2-parent + cycle cases.
- "Return all redundant edges" → skip returning early; collect all matches.
AI Study CompanionBeta
Related problems
Was this page helpful?
📚 Related problems