Redundant Connection (LeetCode 684)

The problem

You start with a tree on nodes 1 to n, then one extra edge is added, so the graph now has exactly one cycle. You get the n edges in order. Return an edge you could remove to get a tree back. If several would work, return the one that appears last in the input.

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

The three edges form a triangle. Removing any one leaves a tree, and [2, 3] comes last.

How to think about it

Start with brute force. Try removing each edge in turn, from last to first, and check whether what’s left is a tree (connected, no cycle) with a DFS. That’s n checks of O(n) each: O(n²). It works, but each check redoes almost all the work of the last one.

The key insight: an edge closes a cycle exactly when its two ends are already connected. Add edges one at a time to an empty graph. While you’re still building a forest, each edge links two separate pieces. The first edge whose endpoints are already in the same piece is the one that creates the cycle. That edge is redundant.

Why the first such edge is also the “last in the input” answer. There is only one cycle. Every earlier edge on that cycle was accepted because, at that moment, its ends weren’t yet connected. The cycle only becomes complete when its last edge arrives. So the first edge you reject is precisely the cycle edge that appears last in the input.

Which pattern is this? Union-find. The tell is “edges arrive one by one; detect the first that connects already-connected nodes”. find tells you each endpoint’s group in near O(1), so the whole check is one pass.

Approach

1. Create parent for nodes 1..n (index 0 is unused).
2. For each edge (a, b), find the roots of a and b.
3. If the roots are equal, a and b are already connected: return [a, b].
4. Otherwise union them by pointing one root at the other.

Solution

def find_redundant(edges):
    parent = list(range(len(edges) + 1))         # nodes are 1..n; n == len(edges)
    def find(x):
        while parent[x] != x: parent[x] = parent[parent[x]]; x = parent[x]
        return x
    for a, b in edges:
        ra, rb = find(a), find(b)
        if ra == rb: return [a, b]               # already connected: this edge closes the cycle
        parent[ra] = rb                          # otherwise merge the two pieces
    return []
# find_redundant([[1,2],[1,3],[2,3]]) -> [2,3]

Dry run

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

A longer one: [[1,2],[2,3],[3,4],[1,4],[1,5]] merges the first three edges, then (1, 4) finds root 4 for both ends and is returned. The edge (1, 5) is never looked at.

Complexity

• Time: O(n·α(n)). One pass over n edges, each with two near-constant find calls thanks to path compression.
• Space: O(n) for parent.

Edge cases and pitfalls

• Node labels start at 1. Size parent as n + 1, or you’ll index out of range on node n.
• Returning the wrong edge when several qualify. Union-find naturally returns the last cycle edge in input order, which is what’s asked. A DFS-based approach has to be careful to match that rule.
• Comparing direct parents instead of roots misses connections that go through intermediate nodes.
• Directed version. Redundant Connection II (LeetCode 685) has directed edges and needs extra handling for a node with two parents. Don’t assume this code solves it.

Related problems

• Graph Valid Tree (LeetCode 261): the same check, answering “is there any cycle”.
• Number of Connected Components (LeetCode 323): the same union-find, counting merges instead.
• Accounts Merge (LeetCode 721): union-find over strings rather than integers.