Redundant Connection

Redundant Connection

What is this problem about?

The Redundant Connection problem gives you n nodes labeled 1..n and n edges forming a tree plus one extra edge (creating a cycle). Find the redundant edge — the last edge that, if removed, leaves a valid tree. This coding problem uses Union-Find to detect which edge creates the first cycle. The union find, BFS, graph, and DFS interview pattern is the core.

Why is this asked in interviews?

InMobi, Microsoft, Meta, Amazon, TikTok, Google, and Bloomberg ask this as the canonical Union-Find problem. It demonstrates cycle detection in an undirected graph — the first edge that connects two already-connected nodes is the redundant one.

Algorithmic pattern used

Union-Find with cycle detection. Process edges in order. For each edge (u, v): if find(u) == find(v), they're already connected → this edge creates a cycle. Return it. Else, union(u, v) and continue.

Example explanation

edges=[(1,2),(1,3),(2,3)]. Process:

• (1,2): union. Components: {1,2},{3}.
• (1,3): union. Components: {1,2,3}.
• (2,3): find(2)=find(3)=same root. Cycle! Return (2,3).

Common mistakes candidates make

• Returning the first edge processed instead of the cycle-creating edge.
• Not using path compression (slow for large graphs).
• Confusing directed vs undirected (Redundant Connection I is undirected).
• Not handling 1-indexed nodes correctly.

Interview preparation tip

Redundant Connection is the standard Union-Find "cycle detection" problem. Process edges in order, union non-connected nodes, and the first edge creating a cycle is the answer. For undirected graphs, Union-Find is simpler than DFS for cycle detection. Practice both approaches: Union-Find (for undirected) and DFS with visited coloring (for directed). See also Redundant Connection II (directed graphs).