4.20.10 — Redundant Connection

LeetCode 684 · Medium

The problem

Start with a tree of n nodes and n − 1 edges, then add one extra edge. Return the edge that can be removed to make it a tree again. If several would work, return the one that appears last in the input.

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

The pattern

A tree with n nodes has exactly n − 1 edges and no cycles. Adding one edge creates exactly one cycle, and the redundant edge is any edge on that cycle.

Process the edges in order. For each one, ask:

Are these two nodes already connected?

If not, this edge joins two separate groups — keep it. If they already are, this edge closes a cycle, and since you are processing in order, it is the last edge that could have done so. Return it.

"Are these two connected, given edges arriving one at a time" is precisely what union-find answers.

Union-find in three lines of idea

Each group has a representative. find(x) walks up to x's representative; union(a, b) makes one representative point at the other, merging the groups.

Two nodes are in the same group exactly when find(a) == find(b).

Two optimisations make it effectively constant time, and both are one line:

Path compression — while walking up in find, point each node directly at the representative, so the next walk is instant.

Union by size — always attach the smaller tree under the larger one, so the trees stay shallow.

With both, each operation costs O(\alpha(n)), where \alpha is the inverse Ackermann function. It is below 5 for any input that fits in the universe, so treat it as constant — and say it that way rather than claiming exactly O(1).

The solution

Python

class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        n = len(edges)
        parent = list(range(n + 1))          # nodes are 1-indexed
        size = [1] * (n + 1)

        def find(x: int) -> int:
            while parent[x] != x:
                parent[x] = parent[parent[x]]     # path compression
                x = parent[x]
            return x

        def union(a: int, b: int) -> bool:
            ra, rb = find(a), find(b)
            if ra == rb:
                return False                      # already connected → a cycle
            if size[ra] < size[rb]:
                ra, rb = rb, ra                   # attach smaller under larger
            parent[rb] = ra
            size[ra] += size[rb]
            return True

        for a, b in edges:
            if not union(a, b):
                return [a, b]

        return []

TypeScript

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

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

  function union(a: number, b: number): boolean {
    let ra = find(a), rb = find(b);
    if (ra === rb) return false;
    if (size[ra] < size[rb]) [ra, rb] = [rb, ra];
    parent[rb] = ra;
    size[ra] += size[rb];
    return true;
  }

  for (const [a, b] of edges) {
    if (!union(a, b)) return [a, b];
  }

  return [];
}

parent[x] = parent[parent[x]] is path halving, a one-line version of path compression that points each node at its grandparent as you climb. It is nearly as effective as the full two-pass version and much shorter.

union returns False when the nodes were already connected, which is exactly the cycle signal. Returning a boolean from union rather than checking find separately keeps the loop to one line.

Processing edges in input order is what satisfies "return the last one that could be removed". The first edge that closes a cycle is the last removable one, because every earlier edge was needed to build up the components.

n + 1 slots because nodes are numbered from 1. Off-by-one here is a silent index error.

Trace

[[1,2],[1,3],[2,3]]

edge	find(a)	find(b)	action
[1,2]	1	2	different → union, groups {1,2}
[1,3]	1	3	different → union, groups {1,2,3}
[2,3]	1	1	same → cycle → return [2,3]

Complexity

O(n \cdot \alpha(n)), effectively O(n). O(n) space.

Why not DFS?

You could, for each edge, remove it and check whether the graph is still connected — O(n^2). Or DFS from scratch to find the cycle and then pick the last of its edges from the input, which is O(n) but fiddlier.

Union-find is the right tool because the edges arrive one at a time and the question is asked after each one. That is the exact situation it is built for, and it is the distinction worth carrying:

• All the edges up front, one query → DFS or BFS is simpler.
• Edges arriving, connectivity asked repeatedly → union-find.

Where this goes next

• Number of Connected Components — union everything, then count the distinct representatives. 4.20.11.
• Graph Valid Tree — connected and exactly n − 1 edges. 4.20.12.
• Kruskal's minimum spanning tree — sort the edges by weight and add each one whose endpoints are not already connected. That "already connected?" check is this union returning False. 4.21.
• Accounts Merge, Number of Islands II, Most Stones Removed — all union-find.

Redundant Connection II (LeetCode 685) is the directed version, and it is genuinely harder: the extra edge may create a node with two parents, a cycle, or both, and the three cases need separate handling. Worth knowing it exists.

What the interviewer will push on

"Why union-find rather than DFS?" Edges arrive one at a time and connectivity is queried after each.

"What is the complexity of union-find?" O(\alpha(n)) amortized with both optimisations, effectively constant. Say "effectively", not "exactly".

"What are the two optimisations and what does each fix?" Path compression flattens the tree during find; union by size stops a tall tree forming during union. Without both, the worst case is O(n) per operation.

"Why does returning the first cycle-closing edge give the last removable one?" Every earlier edge was needed to build the components, so the first one to close a cycle is the last one that can be dropped.

"What if the graph were directed?" A different problem — Redundant Connection II, with three cases.

One thing to volunteer: state the tree fact first. "A tree has n − 1 edges and no cycle, so one extra edge creates exactly one cycle, and any edge on it is removable." That framing makes the union-find choice obvious.

Next: 4.20.11 Number of Connected Components — union-find in its simplest form.