LeetCode · #684

Redundant Connection Solution

Given a graph that was a tree plus one extra edge, find and return that redundant edge — the one that creates a cycle.

01
Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #684

🏗️

Pattern

Graph — Union-Find cycle detection

In an undirected graph with n nodes (labeled 1..n) and n edges (exactly one extra), find the last edge that, when removed, makes the graph a tree (connected acyclic). If multiple answers exist, return the one appearing last in the input.

Example
Input: edges = [[1,2],[1,3],[2,3]] Output: [2,3] // Adding [2,3] creates a cycle 1-2-3-1. Removing it leaves a tree.
Constraints
• n == edges.length • 1 ≤ n ≤ 1000 • edges[i].length == 2, 1 ≤ u, v ≤ n, u ≠ v • No repeated edges
02
Section Two · Approach 1

DFS Cycle Detection — O(n²)

Add edges one by one to an adjacency list. Before adding edge [u, v], run a DFS/BFS to check if u and v are already connected. If yes, this edge creates a cycle — return it. Otherwise, add it and proceed.

Why it works

If u and v are connected before adding [u,v], adding the edge creates a cycle. Since the problem guarantees exactly one redundant edge and we process edges left-to-right, the first such edge is our answer. Processing order also satisfies the "last in input" requirement since there's only one redundant edge.

Why Union-Find is better
Problem: Running DFS before each edge addition is O(V + E) per edge = O(n²) total. Union-Find with path compression and union-by-rank can check and merge two components in effectively O(1) amortized time — O(n · α(n)) total, where α is the inverse Ackermann function (practically ≤ 4 for any n).
Java — DFS connectivity check per edge
import java.util.*; class Solution { public int[] findRedundantConnection(int[][] edges) { int n = edges.length; List<List<Integer>> adj = new ArrayList<>(); for (int i=0; i<=n; i++) adj.add(new ArrayList<>()); for (int[] e : edges) { if (reachable(adj, e[0], e[1], n)) return e; // cycle! adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]); } return new int[0]; } private boolean reachable(List<List<Integer>> adj, int src, int dst, int n) { boolean[] vis = new boolean[n+1]; Queue<Integer> q = new LinkedList<>(); q.offer(src); vis[src] = true; while (!q.isEmpty()) { int v = q.poll(); if (v == dst) return true; for (int nb : adj.get(v)) if (!vis[nb]) { vis[nb]=true; q.offer(nb); } } return false; } }
Python — DFS connectivity check per edge
class Solution: def findRedundantConnection(self, edges: list[list[int]]) -> list[int]: adj = [set() for _ in range(len(edges)+1)] def reachable(src, dst): vis, stack = {src}, [src] while stack: v = stack.pop() if v == dst: return True for nb in adj[v]: if nb not in vis: vis.add(nb); stack.append(nb) return False for u, v in edges: if reachable(u, v): return [u, v] adj[u].add(v); adj[v].add(u) return []
MetricValue
TimeO(n²) — O(n) DFS per edge
SpaceO(n)
03
Section Three · Approach 2

Union-Find — O(n · α(n))

Maintain a Union-Find (Disjoint Set Union) structure. For each edge [u, v]: if find(u) == find(v), u and v are already in the same component — this edge creates a cycle, return it. Otherwise, union their components and continue.

💡 Mental model: Imagine grouping students into study circles. Each student starts in their own circle (parent = self). When two students collaborate, you merge their circles. If you try to merge two students who are already in the same circle, the collaboration link is redundant — it's the cycle-creating edge. The "who is the circle president?" lookup is find(), and the merging is union(). Path compression keeps the president lookup nearly instantaneous.
Algorithm — Union-Find with path compression + rank
  • Initialize: parent[i] = i, rank[i] = 0 for all nodes.
  • find(x): follow parent links to root; path-compress all nodes along the way to point directly to root.
  • union(x, y): find roots of x and y. If same root → cycle detected → return edge. Otherwise, attach smaller-rank tree under larger-rank root.
  • Process edges left to right; the first cycle-creating edge is the answer.
🎯 When to recognize this pattern:
  • "Is there a cycle in an undirected graph added edge by edge?" or "are two nodes connected?" Union-Find answers both in near-O(1).
  • Also used in: LC 323 (Number of Connected Components), LC 128 (Longest Consecutive Sequence — group consecutive numbers), and Kruskal's minimum spanning tree algorithm.
Why not DFS for Union-Find's use case:
  • DFS checks connectivity for one pair. Union-Find maintains connectivity incrementally as edges arrive.
  • If you need to answer many connectivity queries over a growing graph, Union-Find amortizes the cost across all queries, whereas DFS starts fresh each time.
04
Section Four · Trace

Visual Walkthrough

Trace Union-Find on edges = [[1,2],[1,3],[2,3]].

Redundant Connection — Union-Find (edges: [1,2],[1,3],[2,3])
parent[]: initially each node is its own root. Union merges components. Initial: parent=[_,1,2,3] p[1]=1 p[2]=2 p[3]=3 (3 separate components) Edge [1,2]: find(1)=1, find(2)=2 → different roots. Union: attach 2 under 1. parent[2]=1. parent=[_,1,1,3] Components: {1,2} {3} Edge [1,3]: find(1)=1, find(3)=3 → different roots. Union: attach 3 under 1. parent[3]=1. parent=[_,1,1,1] Components: {1,2,3} Edge [2,3]: find(2): 2→parent[2]=1 (root). find(3): 3→parent[3]=1 (root). find(2)==find(3)==1 → SAME ROOT → cycle detected! return [2, 3] ✓ Path compression in find(): Without: 5→4→3→2→1 (depth=4) After find(5): all point directly to 1 5,4,3,2 all get parent=1 instantly ✓
05
Section Five · Implementation

Code — Java & Python

Java — Union-Find with path compression + rank
class Solution { int[] parent, rank; public int[] findRedundantConnection(int[][] edges) { int n = edges.length; parent = new int[n + 1]; rank = new int[n + 1]; for (int i = 0; i <= n; i++) parent[i] = i; // each node is its own root for (int[] e : edges) { if (find(e[0]) == find(e[1])) return e; // same root → cycle union(e[0], e[1]); } return new int[0]; // unreachable — problem guarantees a redundant edge } private int find(int x) { if (parent[x] != x) parent[x] = find(parent[x]); // path compression return parent[x]; } private void union(int x, int y) { int px = find(x), py = find(y); if (rank[px] < rank[py]) parent[px] = py; // attach smaller under larger else if (rank[px] > rank[py]) parent[py] = px; else { parent[py] = px; rank[px]++; } // equal rank: bump one } }
Python — Union-Find with path compression + rank
class Solution: def findRedundantConnection(self, edges: list[list[int]]) -> list[int]: n = len(edges) parent = list(range(n + 1)) rank = [0] * (n + 1) def find(x: int) -> int: if parent[x] != x: parent[x] = find(parent[x]) # path compression return parent[x] def union(x: int, y: int) -> bool: px, py = find(x), find(y) if px == py: return False # already connected if rank[px] < rank[py]: px, py = py, px parent[py] = px if rank[px] == rank[py]: rank[px] += 1 return True for u, v in edges: if not union(u, v): return [u, v] return []
06
Section Six · Analysis

Complexity Analysis

ApproachTimeSpaceTrade-off
DFS per edgeO(n²)O(n)Simple but slow; rebuilds connectivity info each time
Union-Find (no rank/compression)O(n log n)O(n)Better but still log overhead per operation
Union-Find + path compression + rank ← optimal O(n · α(n)) O(n) Near-constant per operation; fastest possible for this problem
What is α(n)?:
  • The inverse Ackermann function. It grows so slowly that for any practical n (up to 10^80), α(n) ≤ 4.
  • For all intents and purposes, find() and union() are O(1) with both optimizations.
  • Without path compression, find() is O(log n).
  • Without union-by-rank, it degrades to O(n) in the worst case (linear chain).
07
Section Seven · Edge Cases

Edge Cases & Pitfalls

CaseInputWhy It Matters
Minimum case (cycle of 3)[[1,2],[2,3],[1,3]]Three nodes, three edges. Third edge creates cycle. Returns [1,3].
Cycle at the beginning[[1,2],[1,2],[1,3]]Cannot happen — problem states no duplicate edges.
Long chain then cycle[[1,2],[2,3],[3,4],[4,1]]Cycle closes at last edge. Returns [4,1].
Self-loop[1,1]Not possible — constraints say u ≠ v.
Nodes labeled 1..n (not 0..n-1)anyAllocate parent/rank arrays of size n+1; use 1-indexed. Common off-by-one error.
Not compressing path in find()long chainWithout compression, find() is O(height) which degrades to O(n) on chains.
⚠ Common Mistake: Forgetting that nodes are 1-indexed (1..n) and allocating a parent array of size n instead of n+1. This causes an ArrayIndexOutOfBoundsException when accessing parent[n]. Always allocate new int[n+1] and initialize parent[i] = i for i = 0..n (index 0 is unused and harmless).

← Back to Graph problems