28 · Union-Find & Minimum Spanning Trees

#684 Redundant Connection

frequently reported atGoogle Amazon Microsoft

the problem

In plain words

A tree with n nodes (labelled 1..n) had one extra edge added. Given the n edges, return an edge you can remove so the result is a tree again. If there are several answers, return the one that appears last in the input.

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

out [2,3]

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

out [1,4]

n == edges.length
3 ≤ n ≤ 1000
1 ≤ aᵢ < bᵢ ≤ n, no repeated edges
The graph is connected

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternUnion-Find (DSU)

Add edges in order. The first edge whose ends are already connected closes the only cycle — and it is the cycle edge that appears last in the input, exactly what the problem asks for.

solutions

From brute force to optimal

Before adding u–v, DFS to see whether u can already reach v. If yes, u–v is redundant.

Keep an adjacency list of edges added so far.
For each edge: DFS from u looking for v.
Found → return the edge; else add it.

timeO(n²)

n edges, each DFS can visit O(n) nodes and edges.

spaceO(n)

Adjacency list, seen array, recursion stack.

javajava.util.*

1class Solution {2    public int[] findRedundantConnection(int[][] edges) {3        int n = edges.length;4        List<List<Integer>> adj = new ArrayList<>();5        for (int i = 0; i <= n; i++) adj.add(new ArrayList<>());6        for (int[] e : edges) {7            // Before adding u–v: can we already walk from u to v? Then u–v closes a cycle.8            if (reachable(adj, e[0], e[1], new boolean[n + 1])) return e;9            adj.get(e[0]).add(e[1]);10            adj.get(e[1]).add(e[0]);11        }12        return new int[0]; // input guarantees a redundant edge13    }14 15    private boolean reachable(List<List<Integer>> adj, int u, int target, boolean[] seen) {16        if (u == target) return true;17        seen[u] = true;18        for (int v : adj.get(u)) {19            if (!seen[v] && reachable(adj, v, target, seen)) return true;20        }21        return false;22    }23}

Union each edge's endpoints; if they already share a root, that edge is the answer.

parent[i] = i for 1..n.
For each edge: find both roots.
Same root → return the edge; otherwise link them.

timeO(n·α(n))

n near-constant unions.

spaceO(n)

parent and size arrays.

javajava.util.*

1class Solution {2    private int[] parent, size;3 4    private int find(int x) {5        if (parent[x] != x) parent[x] = find(parent[x]);6        return parent[x];7    }8 9    public int[] findRedundantConnection(int[][] edges) {10        int n = edges.length; // a tree on n nodes + one extra edge11        parent = new int[n + 1]; // nodes are 1..n12        size = new int[n + 1];13        for (int i = 1; i <= n; i++) { parent[i] = i; size[i] = 1; }14        for (int[] e : edges) {15            int ra = find(e[0]), rb = find(e[1]);16            if (ra == rb) return e; // already connected → this edge makes the cycle17            if (size[ra] < size[rb]) { int t = ra; ra = rb; rb = t; }18            parent[rb] = ra;19            size[ra] += size[rb];20        }21        return new int[0];22    }23}

sim

Dry run

loading simulation…

javajava.util.*

1class Solution {2    private int[] parent, size;3 4    private int find(int x) {5        if (parent[x] != x) parent[x] = find(parent[x]);6        return parent[x];7    }8 9    public int[] findRedundantConnection(int[][] edges) {10        int n = edges.length; // a tree on n nodes + one extra edge11        parent = new int[n + 1]; // nodes are 1..n12        size = new int[n + 1];13        for (int i = 1; i <= n; i++) { parent[i] = i; size[i] = 1; }14        for (int[] e : edges) {15            int ra = find(e[0]), rb = find(e[1]);16            if (ra == rb) return e; // already connected → this edge makes the cycle17            if (size[ra] < size[rb]) { int t = ra; ra = rb; rb = t; }18            parent[rb] = ra;19            size[ra] += size[rb];20        }21        return new int[0];22    }23}

in the room

How to say it in the interview

talk track

Explain why the first failing union is the last cycle edge in input order: all earlier cycle edges were accepted because the cycle wasn't closed yet.
Mention it's 1-indexed, so the arrays have n + 1 slots.

traps

Sizing parent as n: node n is then out of bounds. Use n + 1 slots.
Linking the two nodes before comparing their roots — after a union the roots always match.
Comparing parent[a] == parent[b] instead of find(a) == find(b): direct parents can differ inside one set.

what they ask next

Follow-ups

Redundant Connection II (LC 685) — directed edges?

Harder: a node may have two parents. Detect the node with in-degree 2, try removing each candidate edge, and use DSU to check for a cycle. Plain undirected DSU is not enough.

before you submit

Edge cases to test

The cycle is closed by the very last edge.
Cycle edges are scattered through the input, not next to each other.
Edges after the cycle (a tail hanging off it) must not change the answer.
Nodes are 1-indexed: index n must be valid.

practise next