Redundant Connection LeetCode 684 Guide

LeetCode 684 Redundant Connection gives you a tree of n nodes labeled 1 to n. One extra edge is added, creating exactly one cycle in what would otherwise be a tree. Your task is to return that extra edge — the one that can be removed to restore the graph to a valid tree.

The key constraint is the tiebreaker rule: if there are multiple valid answers (edges whose removal would restore a tree), return the edge that appears last in the input. This means you must process edges in the order given and return the final one that completes a cycle.

Understanding the structure is half the battle. A valid tree on n nodes has exactly n-1 edges and is fully connected with no cycles. This problem gives you exactly n edges connecting n nodes — so there is exactly one extra edge, and finding it is a cycle detection problem.

A tree on n nodes has exactly n-1 edges connecting all n nodes with no cycles. When you add the nth edge, it must connect two nodes that are already reachable from each other — otherwise the graph would remain acyclic. That means the extra edge connects two nodes that already belong to the same connected component.

Union-Find (Disjoint Set Union) is built precisely for this scenario. It tracks connected components dynamically: find(x) returns the root of x's component; union(x, y) merges the components of x and y. If you call union(u, v) and find(u) already equals find(v), then u and v are already connected — the edge [u, v] is the redundant connection.

The elegance here is efficiency: with path compression and union by rank, find and union both run in near O(1) amortized time (technically O(α(n)) where α is the inverse Ackermann function, which is effectively constant for all practical n). You process all n edges in one pass.

Initialize the parent array so every node is its own root: parent[i] = i for all i from 0 to n. Since nodes are 1-indexed, allocate size n+1 to avoid off-by-one errors. Also initialize a rank array (all zeros) to guide union operations toward balanced trees.

The find function uses path compression: after finding the root, update every node along the path to point directly to the root. This flattens the tree structure and makes future find calls near O(1). A recursive implementation is clean: find(x) = x if parent[x] == x, else parent[x] = find(parent[x]).

The union function merges two components by rank. Compare rank[rootX] and rank[rootY]: attach the lower-rank root under the higher-rank root. If ranks are equal, pick either and increment the winner's rank. This keeps trees shallow and ensures find stays fast.

Iterate through the edges array in order. For each edge [u, v], call find(u) and find(v). If they return the same root, u and v are already connected — this edge creates a cycle. Return [u, v] immediately (or continue to find the last such edge for the tiebreaker).

If find(u) != find(v), the two endpoints are in different components. Call union(u, v) to merge them and continue to the next edge. This progressively builds the spanning tree one edge at a time.

For this problem, since there is exactly one redundant edge, the first time find(u) == find(v) will be the answer. The input guarantees exactly one cycle, so you can safely return immediately. The tiebreaker (return the last valid answer) only matters in variants with multiple redundant edges.

A DFS/BFS approach is also valid but significantly slower. For each edge [u, v], temporarily exclude that edge and check if u and v are still connected via DFS or BFS through the remaining edges. If they are, this edge is redundant. If not, include it and move to the next edge.

The time complexity of the DFS approach is O(n²) in the worst case: for each of the n edges, you run a DFS that can visit all n nodes. For n up to 1000 (the problem constraint), this is feasible, but it is far less elegant and harder to implement correctly.

The DFS alternative is worth knowing as a fallback, but Union-Find is the canonical solution for this problem class. Cycle detection in undirected graphs via Union-Find is a fundamental pattern that appears in Kruskal's MST algorithm, detecting cycles in dependency graphs, and many other contexts.

The Python implementation uses a UnionFind class with find (path-compressed) and union (rank-based) methods. The main function iterates over edges: for each [u, v], if find(u) == find(v), return [u, v]; otherwise union(u, v). The class is initialized with n+1 slots to handle 1-indexed nodes.

In Java, the same logic applies. Use an int[] parent and int[] rank, both of size n+1. The find method is iterative with path compression (or recursive). The union method checks ranks and updates accordingly. The main loop mirrors Python: iterate edges, check for cycle via find, return the edge on detection.

Time complexity is O(n * α(n)) — effectively O(n) for all practical purposes. Space complexity is O(n) for the parent and rank arrays. Both Python and Java solutions are single-pass over the edge list with no auxiliary graph structure needed.

Number of Islands II (LC 305) is Union-Find in dynamic form: islands are added one at a time, and after each addition you return the current island count. Each land cell is its own component initially; union merges adjacent land cells. It is Union-Find applied to a 2D grid with incremental updates.

Accounts Merge (LC 721) groups email accounts that share at least one email address. Each account starts as its own component; emails shared between accounts trigger a union. After processing all accounts, find groups all emails by their root component. Classic Union-Find on a string-keyed disjoint set.

Minimum Spanning Tree algorithms (Kruskal's) use Union-Find as their core data structure. Sort edges by weight; for each edge, union the two endpoints if they are in different components (skip if already connected — that edge would form a cycle). The Union-Find family spans cycle detection, component merging, and dynamic connectivity.