Union Find (Disjoint Set) · Medium

Redundant Connection

O(N α(N)) · O(N)

Step 1: Setup & Initialization - Redundant Connection

Join node parent sets until an edge connects two already-unified nodes.

Array Elements & Pointers
10
[0]
20
[1]
30
[2]
40
[3]
50
[4]
Live Variables & Invariants
status:Initialized
pattern:Redundant Connection
Step 1 / 3
33%
Solution Code
1
function findRedundantConnection(edges: number[][]): number[] {
2
  const parent = Array.from({ length: edges.length + 1 }, (_, i) => i);
3
  function find(i: number): number {
4
    if (parent[i] === i) return i;
5
    return (parent[i] = find(parent[i]));
6
  }
7
  for (const [u, v] of edges) {
8
    const pu = find(u), pv = find(v);
9
    if (pu === pv) return [u, v];
10
    parent[pu] = pv;
11
  }
12
  return [];
13
}
LeetCode IDE Console

Test Cases

2 cases from Blind 75 & NeetCode 150

Ask for a hint whenever you get stuck.