Redundant Connection

Problem

LeetCode 684 — Redundant Connection

Given n edges that form a tree plus exactly one extra edge, return the redundant edge. If multiple answers exist, return the one that appears last in the input.

Example

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

Approach — Union-Find (DSU)

For each edge (u, v):

• If find(u) == find(v) → they’re already in the same component → this edge creates a cycle → return it.
• Otherwise → union(u, v) and continue.

Why a set-per-node doesn’t work: checking “have I seen both nodes before” is not enough. Both nodes can exist in the tree without being connected to each other yet. What matters is whether they’re already in the same connected component.

Optimizations

• Path compression in find: flatten the tree so every node points directly to its root. Speeds up future lookups.
• Union by rank: always attach the shorter tree under the taller one. Keeps the tree balanced.

Together these give amortized O(α(n)) per operation — effectively O(1).

Complexity

• Time: O(n * α(n)) ≈ O(n) — n edges, near-constant work per edge
• Space: O(n) — parent and rank arrays

Solution

class Solution {
    private int[] parent;
    private int[] rank;

    public int[] findRedundantConnection(int[][] edges) {
        int n = edges.length;
        parent = new int[n + 1];
        rank = new int[n + 1];
        for (int i = 0; i <= n; i++) parent[i] = i;

        for (int[] edge : edges) {
            int pa = find(edge[0]);
            int pb = find(edge[1]);
            if (pa == pb) return edge;
            union(pa, pb);
        }

        return new int[0];
    }

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

    private void union(int a, int b) {
        if (rank[a] < rank[b]) {
            parent[a] = b;
        } else if (rank[a] > rank[b]) {
            parent[b] = a;
        } else {
            parent[b] = a;
            rank[a]++;
        }
    }
}

Why It Teaches You Something

DSU is the right tool whenever you keep merging equivalence classes and asking “are these two in the same class?”. The same skeleton solves: