Frontend Beauty
ESC

Type to search the knowledge base.

Redundant Connection

Find the edge that creates a cycle in a near-tree graph — Union-Find returns the last redundant edge.

intermediate3 min read
  • dsa
  • graph
  • interview
  • Google
  • Meta
  • Amazon
  • Microsoft

The problem

Graph with n nodes labeled 1..n and n edges (undirected). Exactly one extra edge makes a cycle. Return that edge. If multiple answers in theory, return the one that appears last in the input.

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

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

Mental model: a tree has n−1 edges. The edge that connects two nodes already in the same component is redundant.

Brute force

For each edge, remove it and check connectivity (DFS/BFS). O(n·(n+e)). Works but heavy.

Optimal: Union-Find (DSU)

Process edges in order. If u and v already share a parent, that edge is the answer. Else union them.

function findRedundantConnection(edges: number[][]): number[] {
  const n = edges.length;
  const parent = Array.from({ length: n + 1 }, (_, i) => i);
  const rank = Array(n + 1).fill(0);

  function find(x: number): number {
    if (parent[x] !== x) parent[x] = find(parent[x]);
    return parent[x];
  }

  function union(a: number, b: number): boolean {
    let pa = find(a);
    let pb = find(b);
    if (pa === pb) return false; // already connected → redundant
    if (rank[pa] < rank[pb]) [pa, pb] = [pb, pa];
    parent[pb] = pa;
    if (rank[pa] === rank[pb]) rank[pa]++;
    return true;
  }

  for (const [u, v] of edges) {
    if (!union(u, v)) return [u, v];
  }
  return [];
}
Time O(n · α(n)) ≈ O(n)
Space O(n)

Edge cases

  • Triangle of 3 nodes
  • Redundant edge late in list
  • Star graph plus one chord
  • Nodes are 1-indexed

Common bugs

  • 0-based parent array without size n+1
  • Returning first cycle edge when input order should decide last in stream (DSU natural order handles LC)
  • Directed graph logic (this problem is undirected)

Interview delivery

  1. Tree + one edge.
  2. Union-Find; first failed union is answer.
  3. Path compression + union by rank.
  4. O(n α(n)).
  5. Mention DFS cycle detection alternative.

Why DSU fits

You process edges as “build a forest.” The first edge whose endpoints already share a root would create a cycle — and the problem asks for that edge in input order. Perfect match for online union checks.

Path compression mental model

find flattens: parent[x] = find(parent[x]). Trees stay shallow; α(n) is inverse Ackermann — effectively constant. Union by rank avoids skinny trees before compression helps.

DFS alternative sketch

Build adjacency list omitting one edge at a time, or run cycle detection while building (color DFS / parent tracking). DSU is shorter for undirected unweighted “which edge is extra.”

Follow-ups

  • Redundant Connection II (directed).
  • Critical connections / bridges (Tarjan).
  • Number of provinces (count components with DSU).

Further reading