Redundant Connection LeetCode 684 Guide

Redundant Connection (LeetCode #684) is one of those rare problems that maps perfectly to a single data structure. You are given a graph that was originally a tree — meaning it had n nodes and n-1 edges with no cycles. Someone added one extra edge, and now there is exactly one cycle. Your job is to find that redundant edge and return it.

This is the textbook use case for Union-Find (also called Disjoint Set Union). The idea is elegant: process each edge one at a time, and the moment you try to connect two nodes that are already in the same component, you have found the edge that creates the cycle. No DFS, no BFS, no adjacency list — just a parent array and two operations.

If you are preparing for coding interviews, this problem appears frequently at companies like Google, Amazon, and Meta. It directly tests whether you understand Union-Find and can implement it correctly under pressure. Let us walk through exactly how to solve it.

The input is a list of edges representing an undirected graph with n nodes labeled 1 through n. The graph was formed by taking a tree and adding one additional edge. A tree with n nodes has exactly n-1 edges and no cycles. Adding one more edge necessarily creates exactly one cycle.

Your task is to return the edge that, if removed, would restore the graph to a valid tree. If there are multiple answers (multiple edges that could be removed to break the cycle), you must return the one that appears last in the input list.

For example, given edges [[1,2],[1,3],[2,3]], the graph forms a triangle. Removing any of the three edges would produce a valid tree, but since [2,3] appears last in the input, that is the answer. This "return the last one" rule is important — it means you process edges in order and the last one that causes a problem is your result.

Union-Find maintains a forest of disjoint sets. Each node starts in its own set (its own component). Two operations drive everything: find(x) returns the root representative of the set containing x, and union(x, y) merges the sets containing x and y into one.

The algorithm for this problem is beautifully simple. Initialize every node as its own parent. Then iterate through the edges in order. For each edge [a, b], call find(a) and find(b). If they return the same root, nodes a and b are already connected — adding this edge would create a cycle, so this is the redundant edge. If they return different roots, call union(a, b) to merge their components and move on.

The time complexity is O(n * alpha(n)) where alpha is the inverse Ackermann function — for all practical purposes, this is O(n). Space complexity is O(n) for the parent and rank arrays. This makes Union-Find dramatically faster than running DFS cycle detection for each edge, which would be O(n^2).

A naive Union-Find implementation works but can degrade to O(n) per find operation if the tree becomes a long chain. Two optimizations make it nearly O(1) amortized: path compression and union by rank.

Path compression flattens the tree during find operations. When you call find(x), you walk up the parent pointers to the root, then set every node along that path to point directly to the root. This means future find calls on any of those nodes return in O(1). The recursive version is clean: find(x) returns x if parent[x] equals x, otherwise sets parent[x] to find(parent[x]) and returns it.

Union by rank keeps trees balanced during union operations. Each node tracks a rank (approximate tree height). When merging two components, attach the shorter tree under the taller one. If ranks are equal, pick either and increment its rank. This prevents the pathological case where repeated unions create a linear chain.

For this problem, the implementation looks like this: create a parent array of size n+1 (since nodes are 1-indexed) where parent[i] = i initially. Create a rank array initialized to zero. For each edge [a, b]: find the roots of a and b. If they are the same, return [a, b]. Otherwise, union by rank.

Let us trace through the example [[1,2],[1,3],[2,3]] to see Union-Find in action. We start with three nodes, each in its own component: parent = [_, 1, 2, 3] (index 0 unused).

Process edge [1,2]: find(1) returns 1, find(2) returns 2. Different roots, so we union them. Node 2 now points to node 1. Parent becomes [_, 1, 1, 3]. Components: {1,2} and {3}.

Process edge [1,3]: find(1) returns 1, find(3) returns 3. Different roots, so we union them. Node 3 now points to node 1. Parent becomes [_, 1, 1, 1]. Components: {1,2,3}.

Process edge [2,3]: find(2) follows parent[2] = 1, returns 1. find(3) follows parent[3] = 1, returns 1. Same root! Both nodes are already in the same component. This edge would create a cycle. Return [2,3].

That is the entire algorithm. Three edges processed, one redundant edge found. The elegance of Union-Find is that you never need to think about the graph structure explicitly — you just track connectivity and let the data structure do the work.

The constraints for LeetCode 684 guarantee exactly one extra edge, so you will always find a redundant connection. However, understanding edge cases helps you handle related problems and avoid bugs in your implementation.

The minimum case is three nodes forming a triangle: [[1,2],[2,3],[1,3]]. Here the last edge [1,3] is redundant. With just three nodes, every edge is part of the single cycle, but the "last in input" rule determines the answer.

When the redundant edge connects nodes that are far apart in the tree, Union-Find still works identically. The find operation with path compression handles chains of any length efficiently. Whether the cycle involves two nodes or twenty, the detection logic is the same: if find(a) equals find(b) before union, the edge is redundant.

A common follow-up is LeetCode 685 (Redundant Connection II), which deals with directed graphs. That problem is significantly harder because you also need to handle the case where a node has two parents. The Union-Find approach still applies but requires additional logic to track in-degree violations.

Redundant Connection is more than a single problem — it is your entry point into an entire family of graph connectivity problems. The Union-Find pattern you learn here applies directly to Number of Islands (LeetCode 200), Accounts Merge (LeetCode 721), and Graph Valid Tree (LeetCode 261). In every case, you are tracking connected components and detecting when a new connection is redundant.

The key insight to internalize is that Union-Find transforms cycle detection from a graph traversal problem into a simple membership check. Instead of running DFS and tracking visited nodes, you ask one question: are these two nodes already in the same set? That mental shift from "search the graph" to "check the sets" is what makes Union-Find problems click.

If you found this walkthrough helpful, practice the pattern with YeetCode flashcards. Spaced repetition is the most effective way to move Union-Find from something you understand to something you can implement under interview pressure in five minutes flat. The difference between knowing a pattern and owning it is deliberate, repeated practice.