Redundant Connection

Examples

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

1-2 and 1-3 already form a tree connecting all three nodes; adding 2-3 on top closes a cycle, and it's the last edge added.

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

1-2-3-4 is a path, and 1-4 closes it into a cycle. 1-5 is added afterward but doesn't touch the cycle.

Constraints

• n == edges.length

• 3 <= n <= 1000

• Each edges[i] = [ai, bi] with 1 <= ai, bi <= n and ai != bi

• No repeated edges appear in the input.

Approach

Process the edges in the order they were added, using a Union-Find structure that starts with every node in its own separate group. For each edge [a, b]: if a and b are already in the same group, then this edge connects two nodes that could already reach each other - adding it is exactly what creates the cycle, so it's the answer. Since we're scanning in the original order and stop at the first such edge, that's automatically the last edge (relative to the tree that existed before it) that closes the loop.

If a and b are in different groups, merge those groups and move on - this edge is a genuine tree edge.

A more brute-force alternative: for each edge in order, before adding it, run a DFS/BFS over the edges added so far to check if its two endpoints are already reachable from each other. This answers the same question, just recomputed from scratch every time instead of incrementally.

Solutions

Brute Force - Reachability Check Per Edge

Build up the graph edge by edge. Before adding each new edge, run a DFS to check whether its two endpoints can already reach each other using only the edges added so far. The first edge where that's true is the one that closes the cycle.

function findRedundantConnection(edges) {
  const n = edges.length;
  const graph = Array.from({ length: n + 1 }, () => []);

  function canReach(start, target, visited) {
    if (start === target) return true;
    visited.add(start);
    for (const neighbor of graph[start]) {
      if (!visited.has(neighbor) && canReach(neighbor, target, visited)) {
        return true;
      }
    }
    return false;
  }

  for (const [a, b] of edges) {
    if (graph[a].length > 0 || graph[b].length > 0) {
      if (canReach(a, b, new Set())) return [a, b];
    }
    graph[a].push(b);
    graph[b].push(a);
  }

  return [];
}

Time: O(n²) - up to n edges, each requiring an O(n) reachability search · Space: O(n)

Optimal - Union-Find

Keep every node in its own group at the start. For each edge, try to union its two endpoints' groups. If they're already in the same group, this edge is redundant - return it immediately.

function findRedundantConnection(edges) {
  const n = edges.length;
  const parent = Array.from({ length: n + 1 }, (_, i) => i);

  function find(x) {
    if (parent[x] !== x) {
      parent[x] = find(parent[x]); // path compression
    }
    return parent[x];
  }

  for (const [a, b] of edges) {
    const rootA = find(a);
    const rootB = find(b);

    if (rootA === rootB) return [a, b]; // already connected - this edge closes the cycle

    parent[rootA] = rootB; // union
  }

  return [];
}

Time: O(n × α(n)) - nearly O(n), where α is the inverse Ackermann function · Space: O(n)