Redundant Connection Medium 0 attempts
LeetCode ↗

Redundant Connection

Medium TreeBinary TreeDFS LeetCode

Given an undirected graph that started as a tree with one extra edge, find that extra edge.

Example: edges = [[1,2],[1,3],[2,3]] → Output: [2,3]

Sample Input
—
Sample Output
—
Constraints
  • n == edges.length
  • 3 <= n <= 1000
  • 1 <= edges[i][0] < edges[i][1] <= n
Test Cases
Case 1
Args: [[[1,2],[1,3],[2,3]]] Expected: [2,3]
Topics
TreeBinary TreeDFS

Union-Find

function findRedundantConnection(edges) {
  const parent = Array.from({length: edges.length+1}, (_,i) => i);
  function find(x) { return parent[x] === x ? x : (parent[x] = find(parent[x])); }
  for (const [u, v] of edges) {
    if (find(u) === find(v)) return [u, v];
    parent[find(u)] = find(v);
  }
}

Time: O(n α(n)) | Space: O(n)

Saved in this browser only. Private to you.

JavaScript