Redundant Connection (LeetCode 684)
What a redundant edge means (assume nothing): a tree with n nodes has exactly n - 1 edges and no cycles. Adding one more edge between two nodes that are already connected creates a cycle, and that extra edge is redundant.
A graph on n nodes, labeled 1 through n, started life as a tree (connected, no cycles) and then gained one extra edge, given as an array edges of n pairs [ai, bi].
Identify an edge that can be deleted so what remains is again a tree spanning all n nodes. If more than one edge would work, return whichever one appears last in edges.
Worked Examples
edges = [[1,2],[1,3],[2,3]][2,3]1-2 and 1-3 already connect 2 and 3, so 2-3 closes the cycle and can be removed.edges = [[1,2],[2,3],[3,4],[1,4],[1,5]][1,4]1-2, 2-3 and 3-4, the edge 1-4 closes a cycle, so it is the one to remove.⚖️Formal Constraints & Bounds
n == edges.length3 <= n <= 1000edges[i].length == 21 <= ai < bi <= edges.lengthai != biThere are no repeated edges
The given graph is connected
Core Insight
Path compression flattens the tree height during find, achieving near-constant O(alpha(N)) amortized operations.
Real-World Scenario & Production Applications
Kruskal's Minimum Spanning Tree algorithm, social network mutual friend clustering, and circuit board trace connectivity analysis.
Step-by-Step Execution Trace Table
| Step | Edge Processed | find(u) Root | find(v) Root | find(u) == find(v)? | DSU Action | Disjoint Groups |
|---|---|---|---|---|---|---|
| 0 | Initial State | — | — | — | All nodes self-rooted {1:1, 2:2, 3:3} | 3 |
| 1 | [1, 2] | 1 | 2 | No | Merge: parent[2] = 1 | 2 |
| 2 | [1, 3] | 1 | 3 | No | Merge: parent[3] = 1 | 1 |
| 3 | [2, 3] | find(2) = 1 | find(3) = 1 | Yes (1 == 1) | Cycle detected! Return [2, 3] | 1 |
| 1 | def find(i): |
| 2 | if parent[i] != i: |
| 3 | parent[i] = find(parent[i]) # path compression |
| 4 | return parent[i] |
| 5 | def union(i, j): |
| 6 | root_i, root_j = find(i), find(j) |
| 7 | if root_i == root_j: |
| 8 | return False # the edge closes a cycle |
| 9 | attach the root with the lower rank under the other root |
| 10 | return True |
| 11 | return redundant edge when union returns False |
Conceptual Narrative
Checking whether two nodes are already connected by running a full BFS/DFS on every new edge is O(V) per query. Disjoint Set Union (DSU) maintains dynamic connectivity in near-constant O(alpha(V)) time.
🧭 Conceptual Foundation & Pattern Intuition
A tree with vertices has exactly edges and contains no cycles. LC 684 adds exactly one extra edge to an -node tree, creating a single cycle. We are tasked with identifying the edge that induces this cycle. If we process edges sequentially, an edge creates a cycle if and only if and are already connected through previously processed edges. Using BFS/DFS to test reachability before adding each edge would cost overall. Disjoint Set Union (Union-Find) maintains a collection of disjoint sets where each set is represented by a canonical root node. With two critical optimizations:
- Path Compression:
find(x)first climbs to the root, then walks the path again and points every visited node straight at the root (self.parent[x] = root), flattening the tree to depth 1. - Union by Size: When uniting two trees, always attach the root of the smaller tree (by
size) under the root of the larger one. Together, these optimizations guarantee that any sequence of operations on elements executes in time, where for all values in the observable universe.
🏳️ The Analogy: Merging Sports Teams and Spotting a Redundant Alliance
Imagine athletes competing in a tournament. Initially, each athlete is their own team captain. When an alliance is formed between player and player , their two captains meet and one captain agrees to report to the other. Now, whenever an athlete needs authorization, they look up to their team captain. If two athletes and want to form an alliance, but when they trace their captains they discover they already report to the exact same captain, that alliance is redundant: adding it would create a cycle.
🔑 Why It Works
Testing if not uf.union(a, b) answers "does this edge complete a cycle?" in amortized time, immediately isolating the redundant connection.
Omitting path compression: A
findthat only climbs torootand skips the second loop (self.parent[x] = rootfor every node on the way) leaves long chains, so laterfindcalls can cost instead of near-.1-based vertex indexing off-by-one: Graph vertices are labeled from 1 to . Initializing parent array with size causes
IndexErrorwhen accessingparent[N]. Allocate size .Returning arbitrary cycle edge: LC 684 requires returning the edge that occurs last in the input that creates a cycle; returning an earlier cycle edge fails the problem requirement.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"A tree with one extra edge added" and "return an edge that can be removed so the graph is a tree": edges arrive one by one and you ask whether their ends are already connected.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: find(a) == find(b) exactly when a and b are in the same group, so an edge with ra == rb closes a cycle.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Link roots, not items:
self.parent[rb] = raafter bothfindcalls;self.parent[b] = aleaves part ofb's group behind.Nodes are numbered 1..n:
UnionFind(len(edges) + 1), or node n is out of range.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I'd use Union-Find. Each group is named by its root:
findfollowsparentup to the root and then points every node on the way straight at it, andunionlinks the root of the smaller group under the root of the larger, bysize. For Redundant Connection I add the edges in order. The graph was a tree plus one edge, so exactly one cycle exists, and the first edge whose two ends already share a root is the edge that closes it, which is also the last cycle edge in the input. The trap is linking the items instead of their roots, which splits a group. Each call is almostO(1)amortized, so the pass is O(N · alpha(N)) time andO(N)space."
Complexity & Mathematical Proof
O(N · alpha(N)) for N edges, O(alpha(N)) amortized per call
Look at the code: UnionFind(len(edges) + 1) fills parent and size in O(N). The loop then calls union once per edge, at most N times, and each union makes two iterative find calls. Path compression (the second loop in find) plus union by size (size[ra] < size[rb] decides which root goes under) make each call O(alpha(N)) amortized, where alpha is the inverse Ackermann function, at most 4 for any input that fits in memory. Total: O(N + N · alpha(N)) = O(N · alpha(N)).
O(N)
Look at memory allocations: parent and size hold N + 1 entries each, O(N). find and union are loops, so the call stack is O(1). The answer is one edge, O(1).
T(N) = O(N) + N · O(α(N)) = O(N · α(N))
Derivation Progression
self.parent = list(range(n)), self.size = [1] * n ⟹ O(N)
Every node starts as its own group of size 1.
while x != root: self.parent[x] = root
The first loop climbs to root; the second points every node on the way straight at it, so later calls on those nodes take one step.
if self.size[ra] < self.size[rb]: ra, rb = rb, ra ⟹ O(α(N)) amortized
The smaller group's root goes under the larger one, so trees stay shallow; with path compression each call is O(α(N)) amortized.
N · union(a, b) ⟹ O(N · α(N))
The loop stops at the first union that returns False, so it makes at most N calls.
Variable Definitions
Number of edges, len(edges); the graph also has N nodes, labeled 1..N
Inverse Ackermann function (at most 4 for any practical N)
Memory Architecture & Bounds
O(1) Iterative find/union
O(N) parent and size lists
O(1) One edge [a, b]
Boundary Best / Worst Cases
when the cycle closes early (set-up still costs O(N))
Recurrence Tree Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "undirected graph that started as a tree with one additional edge added", "return an edge that can be removed so the graph is a tree". Tree with vertices has exactly edges. An extra edge introduces a cycle. A Senior SWE immediately uses Union-Find with path compression and union by size, adding the edges in input order.
vertices, edges. DSU executes in near-linear time where is the Inverse Ackermann function ().
Online only: the structure answers "already connected?" as edges stream in, but it cannot undo a union, so a graph that also deletes edges needs a different structure. Long chains: a recursive find can hit Python's default recursion limit before compression flattens the chain; the iterative two-loop find never does.
Core Algorithmic State Invariants
- The First Failing Edge Is the Answer
The graph was a tree plus one edge, so it has exactly one cycle. Adding edges in order, the only union that can fail is the one that completes that cycle, and every other cycle edge came before it, so it is the cycle edge that appears last in the input.
Redundant Connection (LeetCode 684)
What a redundant edge means (assume nothing): a tree with n nodes has exactly n - 1 edges and no cycles. Adding one more edge between two nodes that are already connected creates a cycle, and that extra edge is redundant.
A graph on n nodes, labeled 1 through n, started life as a tree (connected, no cycles) and then gained one extra edge, given as an array edges of n pairs [ai, bi].
Identify an edge that can be deleted so what remains is again a tree spanning all n nodes. If more than one edge would work, return whichever one appears last in edges.
Worked Examples
edges = [[1,2],[1,3],[2,3]][2,3]1-2 and 1-3 already connect 2 and 3, so 2-3 closes the cycle and can be removed.edges = [[1,2],[2,3],[3,4],[1,4],[1,5]][1,4]1-2, 2-3 and 3-4, the edge 1-4 closes a cycle, so it is the one to remove.⚖️Formal Constraints & Bounds
n == edges.length3 <= n <= 1000edges[i].length == 21 <= ai < bi <= edges.lengthai != biThere are no repeated edges
The given graph is connected
Core Insight
Path compression flattens the tree height during find, achieving near-constant O(alpha(N)) amortized operations.
Real-World Scenario & Production Applications
Kruskal's Minimum Spanning Tree algorithm, social network mutual friend clustering, and circuit board trace connectivity analysis.
Step-by-Step Execution Trace Table
| Step | Edge Processed | find(u) Root | find(v) Root | find(u) == find(v)? | DSU Action | Disjoint Groups |
|---|---|---|---|---|---|---|
| 0 | Initial State | — | — | — | All nodes self-rooted {1:1, 2:2, 3:3} | 3 |
| 1 | [1, 2] | 1 | 2 | No | Merge: parent[2] = 1 | 2 |
| 2 | [1, 3] | 1 | 3 | No | Merge: parent[3] = 1 | 1 |
| 3 | [2, 3] | find(2) = 1 | find(3) = 1 | Yes (1 == 1) | Cycle detected! Return [2, 3] | 1 |
| 1 | def find(i): |
| 2 | if parent[i] != i: |
| 3 | parent[i] = find(parent[i]) # path compression |
| 4 | return parent[i] |
| 5 | def union(i, j): |
| 6 | root_i, root_j = find(i), find(j) |
| 7 | if root_i == root_j: |
| 8 | return False # the edge closes a cycle |
| 9 | attach the root with the lower rank under the other root |
| 10 | return True |
| 11 | return redundant edge when union returns False |
Conceptual Narrative
Checking whether two nodes are already connected by running a full BFS/DFS on every new edge is O(V) per query. Disjoint Set Union (DSU) maintains dynamic connectivity in near-constant O(alpha(V)) time.
🧭 Conceptual Foundation & Pattern Intuition
A tree with vertices has exactly edges and contains no cycles. LC 684 adds exactly one extra edge to an -node tree, creating a single cycle. We are tasked with identifying the edge that induces this cycle. If we process edges sequentially, an edge creates a cycle if and only if and are already connected through previously processed edges. Using BFS/DFS to test reachability before adding each edge would cost overall. Disjoint Set Union (Union-Find) maintains a collection of disjoint sets where each set is represented by a canonical root node. With two critical optimizations:
- Path Compression:
find(x)first climbs to the root, then walks the path again and points every visited node straight at the root (self.parent[x] = root), flattening the tree to depth 1. - Union by Size: When uniting two trees, always attach the root of the smaller tree (by
size) under the root of the larger one. Together, these optimizations guarantee that any sequence of operations on elements executes in time, where for all values in the observable universe.
🏳️ The Analogy: Merging Sports Teams and Spotting a Redundant Alliance
Imagine athletes competing in a tournament. Initially, each athlete is their own team captain. When an alliance is formed between player and player , their two captains meet and one captain agrees to report to the other. Now, whenever an athlete needs authorization, they look up to their team captain. If two athletes and want to form an alliance, but when they trace their captains they discover they already report to the exact same captain, that alliance is redundant: adding it would create a cycle.
🔑 Why It Works
Testing if not uf.union(a, b) answers "does this edge complete a cycle?" in amortized time, immediately isolating the redundant connection.
Omitting path compression: A
findthat only climbs torootand skips the second loop (self.parent[x] = rootfor every node on the way) leaves long chains, so laterfindcalls can cost instead of near-.1-based vertex indexing off-by-one: Graph vertices are labeled from 1 to . Initializing parent array with size causes
IndexErrorwhen accessingparent[N]. Allocate size .Returning arbitrary cycle edge: LC 684 requires returning the edge that occurs last in the input that creates a cycle; returning an earlier cycle edge fails the problem requirement.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"A tree with one extra edge added" and "return an edge that can be removed so the graph is a tree": edges arrive one by one and you ask whether their ends are already connected.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: find(a) == find(b) exactly when a and b are in the same group, so an edge with ra == rb closes a cycle.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Link roots, not items:
self.parent[rb] = raafter bothfindcalls;self.parent[b] = aleaves part ofb's group behind.Nodes are numbered 1..n:
UnionFind(len(edges) + 1), or node n is out of range.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I'd use Union-Find. Each group is named by its root:
findfollowsparentup to the root and then points every node on the way straight at it, andunionlinks the root of the smaller group under the root of the larger, bysize. For Redundant Connection I add the edges in order. The graph was a tree plus one edge, so exactly one cycle exists, and the first edge whose two ends already share a root is the edge that closes it, which is also the last cycle edge in the input. The trap is linking the items instead of their roots, which splits a group. Each call is almostO(1)amortized, so the pass is O(N · alpha(N)) time andO(N)space."
Complexity & Mathematical Proof
O(N · alpha(N)) for N edges, O(alpha(N)) amortized per call
Look at the code: UnionFind(len(edges) + 1) fills parent and size in O(N). The loop then calls union once per edge, at most N times, and each union makes two iterative find calls. Path compression (the second loop in find) plus union by size (size[ra] < size[rb] decides which root goes under) make each call O(alpha(N)) amortized, where alpha is the inverse Ackermann function, at most 4 for any input that fits in memory. Total: O(N + N · alpha(N)) = O(N · alpha(N)).
O(N)
Look at memory allocations: parent and size hold N + 1 entries each, O(N). find and union are loops, so the call stack is O(1). The answer is one edge, O(1).
T(N) = O(N) + N · O(α(N)) = O(N · α(N))
Derivation Progression
self.parent = list(range(n)), self.size = [1] * n ⟹ O(N)
Every node starts as its own group of size 1.
while x != root: self.parent[x] = root
The first loop climbs to root; the second points every node on the way straight at it, so later calls on those nodes take one step.
if self.size[ra] < self.size[rb]: ra, rb = rb, ra ⟹ O(α(N)) amortized
The smaller group's root goes under the larger one, so trees stay shallow; with path compression each call is O(α(N)) amortized.
N · union(a, b) ⟹ O(N · α(N))
The loop stops at the first union that returns False, so it makes at most N calls.
Variable Definitions
Number of edges, len(edges); the graph also has N nodes, labeled 1..N
Inverse Ackermann function (at most 4 for any practical N)
Memory Architecture & Bounds
O(1) Iterative find/union
O(N) parent and size lists
O(1) One edge [a, b]
Boundary Best / Worst Cases
when the cycle closes early (set-up still costs O(N))
Recurrence Tree Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "undirected graph that started as a tree with one additional edge added", "return an edge that can be removed so the graph is a tree". Tree with vertices has exactly edges. An extra edge introduces a cycle. A Senior SWE immediately uses Union-Find with path compression and union by size, adding the edges in input order.
vertices, edges. DSU executes in near-linear time where is the Inverse Ackermann function ().
Online only: the structure answers "already connected?" as edges stream in, but it cannot undo a union, so a graph that also deletes edges needs a different structure. Long chains: a recursive find can hit Python's default recursion limit before compression flattens the chain; the iterative two-loop find never does.
Core Algorithmic State Invariants
- The First Failing Edge Is the Answer
The graph was a tree plus one edge, so it has exactly one cycle. Adding edges in order, the only union that can fail is the one that completes that cycle, and every other cycle edge came before it, so it is the cycle edge that appears last in the input.