Redundant Connection

MediumUnion-Find (DSU)NeetCode 150MidOpen on LeetCodeUpdated Nov 11, 2026

You're given an undirected graph that started as a tree on n nodes labeled 1 to n, then gained one extra edge between two different nodes that weren't already directly connected. The array edges holds all n edges, where edges[i] = [a, b] connects a and b. Return an edge whose removal leaves a tree on all n nodes. If more than one edge would work, return the one that appears last in edges.

Examples

edges = [[1,2],[1,3],[2,3]] returns [2,3]

Any side of the triangle could go; [2,3] is listed last.

The three edges form a triangle, and removing any one of them leaves a tree. [2,3] is the last of them in the list.

edges = [[1,2],[2,3],[3,4],[1,4],[1,5]] returns [1,4]

Nodes 1 to 4 form the loop. [1,4] is the loop edge that appears last.

The loop runs 1, 2, 3, 4 and back to 1, so any of [1,2], [2,3], [3,4] and [1,4] could go, and [1,4] appears last. Removing [1,5] instead would cut node 5 off.

Constraints

3 <= n <= 1000
edges.length == n

Hints

Hint 1

What's true about the very first edge that connects two nodes already linked through other edges?

Hint 2

A pointer toward the approach

Hint 3

The full approach, step by step

Drill This: Your Approach First

Answer, Then Reveal

In two or three sentences, how would you solve it and what's the complexity?

Skip to Reading

Approach

Add the edges one at a time while tracking which nodes are already connected, grouping them under shared roots. Before adding [a, b], find both roots. If they're equal, a and b are already joined, so this edge closes the cycle and is the answer. Otherwise merge the two groups. The edges before it formed no cycle, so the first edge that closes one is the last cycle edge in the list, which is exactly the tie-break required. O(n log n) time, O(n) space.

Time

O(n log n)

Space

O(n)

Pitfall

The nodes are labeled 1 to n, so the parent array needs n + 1 slots; sizing it to n puts node n out of range. Don't return the first edge on the cycle; the answer is the last one listed, the edge whose endpoints already share a root when you reach it.

Solutions

class Solution {
    public int[] findRedundantConnection(int[][] edges) {
        int n = edges.length;
        int[] parent = new int[n + 1];
        for (int i = 0; i <= n; i++) parent[i] = i;
        for (int[] e : edges) {
            int ra = find(parent, e[0]);
            int rb = find(parent, e[1]);
            if (ra == rb) return e;
            parent[ra] = rb;
        }
        return new int[0];
    }

    private int find(int[] parent, int x) {
        if (parent[x] != x) parent[x] = find(parent, parent[x]);
        return parent[x];
    }
}

class Solution:
    def findRedundantConnection(self, edges):
        parent = list(range(len(edges) + 1))

        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]
            parent[ra] = rb
        return []