Redundant Connection
Problem
Given a list of edges representing an undirected graph that started as a tree with one extra edge added, return the edge that can be removed to restore the tree structure.
- 3 ≤ edges.length ≤ 1000
- edges[i].length == 2
- 1 ≤ ui, vi ≤ edges.length
- ui != vi
Example
edges = [[1,2],[1,3],[2,3]][2,3]The graph initially was a tree with edges [1,2] and [1,3]. Adding the edge [2,3] creates a cycle. The algorithm uses Union-Find to detect this cycle. It processes edges in order: union(1,2) succeeds, union(1,3) succeeds, but union(2,3) fails because 2 and 3 are already connected, indicating the edge [2,3] is redundant and should be returned.
Approach
Straightforward Solution
A brute-force approach would check for cycles after adding each edge using DFS or BFS, resulting in O(n^2) time complexity, which is inefficient for large inputs.
Core Observation
A tree with n nodes has exactly n-1 edges and no cycles. Adding one extra edge creates exactly one cycle. Detecting this cycle is equivalent to finding the first edge that connects two nodes already in the same connected component.
Path to Optimal
PreviewThe key recognition signals are 'detect cycle in undirected graph' and 'return redundant edge'. These indicate the Union-Find (Disjoint Set Union) pattern because it efficiently tracks connected components and detects cycles in near O(1) amortized time per union/find operation…
Full step-by-step walkthrough on Pro →
Optimal Approach
PreviewInitialize Union-Find data structures with each node as its own parent and rank 1. For each edge, perform find operations to get the root parents of both nodes…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
O(n α(n))
Each union and find operation runs in nearly constant amortized time due to path compression and union by rank optimizations, and all edges are processed once.
Space
O(n)
The parent and rank arrays each store one entry per node, scaling linearly with the number of nodes.
Pattern Spotlight
Union Find (Cycle Detection in Undirected Graph)
When detecting cycles in an undirected graph incrementally, use Union Find to track connected components; the first edge that connects two nodes already in the same set is the redundant edge creating a cycle.
Solution
| 1 | class Solution:
|
| 2 | def findRedundantConnection(self, edges: list[list[int]]) -> list[int]:
|
| 3 | par = [i for i in range(len(edges) + 1)]
|
| 4 | rank = [1] * (len(edges) + 1)
|
| 5 |
|
| 6 | def find(n):
|
| 7 | p = par[n]
|
| 8 | while p != par[p]:
|
| 9 | par[p] = par[par[p]]
|
| 10 | p = par[p]
|
| 11 | return p
|
| 12 |
|
| 13 | def union(n1, n2):
|
| 14 | p1, p2 = find(n1), find(n2)
|
| 15 |
|
| 16 | if p1 == p2:
|
| 17 | return False
|
| 18 |
|
| 19 | if rank[p1] > rank[p2]:
|
| 20 | par[p2] = p1
|
| 21 | rank[p1] += rank[p2]
|
| 22 | else:
|
| 23 | par[p1] = p2
|
| 24 | rank[p2] += rank[p1]
|
| 25 | return True
|
| 26 |
|
| 27 | for n1, n2 in edges:
|
| 28 | if not union(n1, n2):
|
| 29 | return [n1, n2] |
Step-by-Step Solution
Initialize Union-Find Parent and Rank Arrays
| 3 | par = [i for i in range(len(edges) + 1)]
|
| 4 | rank = [1] * (len(edges) + 1)
|
Objective
To set up the data structures that track the connected components and their sizes for efficient union and find operations.
Key Insight
Initializing each node as its own parent represents that initially, all nodes are separate components. The rank array tracks the size or depth of each component, enabling union by rank to keep the tree shallow, which optimizes find operations. This setup is foundational for efficient cycle detection.
Interview Quick-Check
Core Logic
Parent array maps each node to its representative parent; rank array helps keep the union trees balanced.
Common Pitfalls & Bugs
Incorrect initialization of parent or rank arrays can cause incorrect cycle detection or inefficient unions.
Implement Find with Path Compression to Identify Root Parent
To efficiently find the root parent of a node, compressing paths to speed up future queries.
Implement Union by Rank to Merge Sets and Detect Cycles
To merge two disjoint sets efficiently and detect if adding an edge creates a cycle.
Iterate Over Edges to Detect and Return the Redundant Connection
To process each edge, performing union operations and returning the first edge that creates a cycle.
3 more steps with full analysis available on Pro.
Line Analysis
This solution has 2 Critical lines interviewers watch for.
par = [i for i in range(len(edges) + 1)]Initialize the parent array where each node is its own parent.
This initialization represents that initially, each node is a separate connected component, which is essential for Union-Find to correctly track connectivity.
rank = [1] * (len(edges) + 1)Initialize the rank array with 1 for each node.
Rank tracks the size or depth of each component, enabling union by rank to keep trees balanced and optimize find operations.
Full line-by-line criticality + rationale for all 23 lines available on Pro.
Test Your Understanding
Why does detecting that two nodes share the same root parent in Union Find indicate a cycle?
See the answer with Pro.
Related Problems
Union Find pattern
Don't just read it. Drill it.
Reconstruct Redundant Connection from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Redundant Connection drill