Redundant Connection — Union Find Cycle Detection

Problem Statement#

LeetCode 684 — Redundant Connection (Medium)

In this problem, a tree is an undirected graph that is connected and has no cycles.

You are given a graph that started as a tree with n nodes labeled from 1 to n, with one additional edge added. The added edge has two different vertices chosen from 1 to n, and was not an edge that already existed. The graph is represented as an array edges of length n where edges[i] = [a, b] indicates that there is an edge between nodes a and b in the graph.

Return an edge that can be removed so that the resulting graph is a tree of n nodes. If there are multiple answers, return the answer that occurs last in the input.

Constraints:

• n == edges.length
• 3 <= n <= 1000
• edges[i].length == 2, 1 <= a, b <= n, a != b
• No repeated edges, the graph is connected.

Example 1:

edges = [[1,2],[1,3],[2,3]]
Output: [2,3]

Example 2:

edges = [[1,2],[2,3],[3,4],[1,4],[1,5]]
Output: [1,4]

Why This Problem Matters#

Redundant Connection is the interview poster child for Union Find. Amazon, Google, and Meta all rotate it because it can be solved in five lines using DSU and demonstrates a deep understanding of how Union Find detects cycles. The harder follow-up — LC 685 — Redundant Connection II — generalizes to directed graphs and is a staff-level question.

The problem hits three checkpoints:

1. Cycle detection in undirected graphs. The first edge whose endpoints already share a Union Find root must be the cycle-closing edge.
2. Tie-breaking by input order. "Return the last redundant edge" forces you to process edges in the given order; the first redundant one you encounter while scanning is automatically the last in input order, because tree edges are always non-redundant.
3. Why the structure forces a unique cycle. A tree has n - 1 edges; adding one more creates exactly one cycle. The edge that closes that cycle is the redundant one.

The Core Insight#

Process edges in order. For each edge [a, b]:

• If find(a) == find(b), the edge connects two already-merged components, so it must close a cycle. Return this edge immediately.
• Otherwise, union(a, b) merges the components and continue.

Because we have exactly n edges and a tree only needs n - 1, exactly one edge closes the cycle. Scanning in input order guarantees we catch it the moment it appears, and since tree edges never cause a cycle, that hit is also the last redundant edge in the input — satisfying the tie-break rule.

This insight collapses the problem from "find any redundant edge in a graph" into "process edges and return the first cycle-closing one." Five-line solution.

Visual Dry Run#

edges = [[1,2],[2,3],[3,4],[1,4],[1,5]]. Run Union Find:

parent = [0, 1, 2, 3, 4, 5]   (1-indexed; parent[0] unused)
 
Edge [1, 2]: find(1)=1, find(2)=2 -> different. Union.
parent = [0, 1, 1, 3, 4, 5]
 
Edge [2, 3]: find(2)=1, find(3)=3 -> different. Union.
parent = [0, 1, 1, 1, 4, 5]
 
Edge [3, 4]: find(3)=1, find(4)=4 -> different. Union.
parent = [0, 1, 1, 1, 1, 5]
 
Edge [1, 4]: find(1)=1, find(4)=1 -> SAME ROOT.
Return [1, 4].

Note that [1, 5] was never processed; we exit the moment the first cycle-closer appears. That is fine because there is exactly one redundant edge by problem definition.

Solution (Optimal)#

Python (Union Find with path compression and union by rank)#

class Solution:
    def findRedundantConnection(self, edges: list[list[int]]) -> list[int]:
        n = len(edges)
        parent = list(range(n + 1))                  # 1-indexed nodes
        rank = [0] * (n + 1)
 
        def find(x: int) -> int:
            while parent[x] != x:
                parent[x] = parent[parent[x]]        # path compression (halving)
                x = parent[x]
            return x
 
        def union(a: int, b: int) -> bool:
            ra, rb = find(a), find(b)
            if ra == rb:
                return False                          # cycle: do not merge
            # Union by rank
            if rank[ra] < rank[rb]:
                parent[ra] = rb
            elif rank[ra] > rank[rb]:
                parent[rb] = ra
            else:
                parent[rb] = ra
                rank[ra] += 1
            return True
 
        for a, b in edges:
            if not union(a, b):
                return [a, b]                         # first cycle-closer wins
 
        return []                                     # unreachable per problem spec

JavaScript (Same idea, idiomatic JS)#

/**
 * @param {number[][]} edges
 * @return {number[]}
 *
 * Process edges in order. The first edge whose endpoints share a root
 * is the redundant one (and also the last redundant one by problem invariant).
 */
var findRedundantConnection = function(edges) {
    const n = edges.length;
    const parent = Array.from({length: n + 1}, (_, i) => i);
    const rank = new Array(n + 1).fill(0);
 
    const find = (x) => {
        while (parent[x] !== x) {
            parent[x] = parent[parent[x]];            // path compression
            x = parent[x];
        }
        return x;
    };
 
    const union = (a, b) => {
        const ra = find(a), rb = find(b);
        if (ra === rb) return false;                  // would create a cycle
        if (rank[ra] < rank[rb]) parent[ra] = rb;
        else if (rank[ra] > rank[rb]) parent[rb] = ra;
        else { parent[rb] = ra; rank[ra]++; }
        return true;
    };
 
    for (const [a, b] of edges) {
        if (!union(a, b)) return [a, b];              // first cycle-closer
    }
    return [];
};

Complexity. Time is O(N alpha(N)) where alpha is the inverse Ackermann function — effectively constant. Space is O(N).

Common Mistakes#

1. Off-by-one indexing. Nodes are 1-indexed in this problem. Make sure your parent array sizes are n + 1 (or use 0-based internally with a translation).
2. Returning the wrong edge. Only return the first edge whose endpoints share a root; do not run through all edges and return the last one — by then you might have unioned past extra edges incorrectly.
3. Skipping path compression or union by rank. Without them, the find operation can degenerate to O(N) per call on adversarial inputs.
4. Doing BFS / DFS instead of Union Find. It works but is verbose. Add edges one at a time, BFS to check whether a already reaches b. If yes, return the edge. This is O(N times E), about 1,000 times slower.
5. Misreading the tie-break. Some candidates assume "any redundant edge" suffices. The spec says return the one that appears last; Union Find naturally returns it first scanned, which equals last redundant by the problem invariant.

Interview Tips#

• Lead with Union Find. Saying "this is a textbook Union Find cycle detection problem" earns immediate buy-in.
• Trace through Example 2. Walking the union sequence is more convincing than just citing the algorithm.
• Mention the alpha(N) bound. "Operations are essentially O(1) amortized" demonstrates depth.
• Discuss the directed variant (LC 685). Saying "the directed version is harder because you also have to consider in-degree-2 nodes" plants the seed of seniority.

Follow-up Questions#

1. Directed graphs (LC 685). A node could have two parents instead of forming a cycle. You need a two-pass algorithm: detect the conflict edge and the cycle edge separately.
2. Multiple redundant edges. Run Union Find but collect every cycle-closing edge into a list.
3. Find the minimum-cost edge to remove (weighted graph). Track the maximum-weight edge along the path from a to b for each cycle-closing edge.
4. Edge insertions and deletions online. Vanilla Union Find does not support deletion. Use link-cut trees or offline processing.
5. Find the cycle itself, not just the edge. Run BFS / DFS once you detect the cycle-closing edge to recover the path.

Key Takeaways#

• Redundant Connection is the canonical Union Find cycle-detection problem.
• Process edges in order; the first edge whose endpoints share a root is the answer.
• Always implement Union Find with path compression and union by rank for near-O(1) operations.
• The problem guarantees exactly one redundant edge — no need to keep scanning after you find it.
• The directed variant (LC 685) is a strict generalization; mention it for seniority points.
• The five-line Union Find solution is one of the cleanest interview answers you can deliver.