Redundant Connection

MediumGraphs · Union-Find🧩 Union-Find LeetCode #684 ↗Updated Oct 30, 2026

Problem

A tree on nodes 1..n had one extra edge added, so the undirected graph given as edges (n edges) now contains exactly one cycle. Return an edge whose removal turns the graph back into a tree; if several qualify, return the one that appears last in edges.

Input[[1,2],[1,3],[2,3]]Output[2,3]

Input[[1,2],[2,3],[3,4],[1,4],[1,5]]Output[1,4]

n == edges.length · 3 ≤ n ≤ 1000 · 1 ≤ a_i < b_i ≤ n · distinct edges, connected

Try it yourself

Java

class Solution {
    public int[] findRedundantConnection(int[][] edges) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Add edges in input order: the first edge whose endpoints are already connected closes the only cycle, and it is the latest cycle edge in the input. Union-Find answers “already connected?” in near-constant time.

PatternUnion-Find

Instinct Items get grouped by "connected", "same as" or "shares a" links and you keep asking which group something is in: merge sets with Union-Find.

Memory hack Find your boss, merge the bosses; squash the chain (path compression) and hang the short tree under the tall one (rank).

Open the Union-Find guide →

Approaches

Brute ForceIncremental Graph + DFS Connectivity Check

Time O(n²)Space O(n)

Build the graph edge by edge. Before adding (u, v), run a DFS from u: if v is already reachable, this edge closes the cycle. The cycle only appears once its last edge (in input order) arrives, so the first hit is the answer.

Java

public int[] findRedundantConnection(int[][] edges) {
    int n = edges.length;
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i <= n; i++) adj.add(new ArrayList<>());
    for (int[] e : edges) {
        if (connected(adj, e[0], e[1], new boolean[n + 1])) return e;
        adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]);
    }
    return new int[0];
}
private boolean connected(List<List<Integer>> adj, int u, int target, boolean[] seen) {
    if (u == target) return true;
    seen[u] = true;
    for (int v : adj.get(u))
        if (!seen[v] && connected(adj, v, target, seen)) return true;
    return false;
}

Simple and correct, but one O(n) DFS per edge ⇒ quadratic.

BetterOne DFS: Find the Cycle, Pick Its Last Edge

Time O(n)Space O(n)

DFS once from node 1 recording parents. The first back edge u→v (v visited, not the parent) closes the cycle: walk parents from u to v to mark it, then return the last input edge joining two cycle nodes.

Java

private List<List<Integer>> adj = new ArrayList<>();
private int[] parent; // 0 = unvisited, root gets -1
private int top, bottom;
public int[] findRedundantConnection(int[][] edges) {
    int n = edges.length;
    parent = new int[n + 1];
    for (int i = 0; i <= n; i++) adj.add(new ArrayList<>());
    for (int[] e : edges) { adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]); }
    dfs(1, -1);
    boolean[] onCycle = new boolean[n + 1];
    for (int v = bottom; ; v = parent[v]) { onCycle[v] = true; if (v == top) break; }
    for (int i = n - 1; i >= 0; i--)
        if (onCycle[edges[i][0]] && onCycle[edges[i][1]]) return edges[i];
    return new int[0];
}
private boolean dfs(int u, int p) {
    parent[u] = p;
    for (int v : adj.get(u)) {
        if (v == p) continue;
        if (parent[v] != 0) { top = v; bottom = u; return true; } // back edge
        if (dfs(v, u)) return true;
    }
    return false;
}

Linear, but needs the whole graph up front plus cycle reconstruction.

OptimalUnion-Find (Path Compression + Union by Rank)

Time O(n α(n))Space O(n)

Process edges in order with a DSU. union(u, v) fails exactly when u and v already share a root — i.e. they were connected before this edge — so that edge is the redundant one. No adjacency list, one pass.

Java

private int[] parent, 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[] e : edges)
        if (!union(e[0], e[1])) return e; // already connected -> cycle
    return new int[0];
}
private int find(int x) {
    return parent[x] == x ? x : (parent[x] = find(parent[x])); // path compression
}
private boolean union(int a, int b) {
    int ra = find(a), rb = find(b);
    if (ra == rb) return false;
    if (rank[ra] < rank[rb]) { int t = ra; ra = rb; rb = t; } // union by rank
    parent[rb] = ra;
    if (rank[ra] == rank[rb]) rank[ra]++;
    return true;
}

Near-linear, online, tiny code — the expected interview answer.

At a glance

Level	Approach	Time	Space
Brute Force	Incremental Graph + DFS Connectivity Check	`O(n²)`	`O(n)`
Better	One DFS: Find the Cycle, Pick Its Last Edge	`O(n)`	`O(n)`
Optimal	Union-Find (Path Compression + Union by Rank)	`O(n α(n))`	`O(n)`

Common pitfalls

Returning the first cycle edge in input order instead of the last.
Off-by-one: nodes are 1-indexed, so size the arrays n + 1.
In undirected DFS, treating the edge back to the parent as a cycle.

Interview tips

Note n nodes + n edges + connected ⇒ exactly one cycle.
Explain why the first failing union is the last cycle edge in the input.
Mention α(n) ≤ 4 in practice; the DSU is effectively linear.

Pattern

Union-Find → edges arrive one by one and you must ask “are these already connected?”

My notes saved in this browser