Redundant Connection

35 min · findRedundantConnection()

A road network began as a perfect tree. Then one extra road was added, and now exactly one loop exists. Which road should you undo?

You're given edges, an ordered list of undirected connections. The graph uses nodes labeled 1 through n, where n == edges.length. Before one extra edge was added, the graph was a tree.

Return an edge whose removal restores a tree. A redundant edge is one you can remove without disconnecting the graph. Every edge on the single cycle — a route that leaves a node and returns to it without reusing an edge — qualifies. When several do, return the one that appears last in edges. Preserve that edge's endpoint order.

Constraints

3 <= n <= 1_000
edges.length == n
Every edge contains two labels in the range 1..n.
There are no self-loops and no duplicate undirected edges.
The graph is a tree plus exactly one extra edge, so it contains exactly one cycle.

Hints

Try every removal

Work backward through edges. Remove one candidate, then test whether the remaining n - 1 edges connect all n nodes without a cycle.

Replay the construction

Add the edges in their given order. A tree edge always joins two groups that were separate. What changes when you reach the last edge on the cycle?

Ask the roots

Union-find tells you whether two endpoints are already connected. The first edge whose endpoints share a root is the answer.

Follow-up

If a much larger stream could contain several extra edges, how would you report every edge that closes a cycle as it arrives?

Visible cases

Examples

Example 1

ready

Input: edges = [ [ 1, 2 ], [ 1, 3 ], [ 2, 3 ] ]
Expected: [ 2, 3 ]
Why: [2, 3] appears last among the three removable cycle edges

Example 2

ready

Input: edges = [ [ 1, 2 ], [ 2, 3 ], [ 3, 4 ], [ 1, 4 ], [ 1, 5 ] ]
Expected: [ 1, 4 ]
Why: the fourth edge closes the 1-2-3-4 loop

Example 3

ready

Input: edges = [ [ 1, 2 ], [ 2, 3 ], [ 3, 1 ], [ 3, 4 ] ]
Expected: [ 3, 1 ]
Why: the tail to node 4 isn't part of the cycle

Interview signal

Asked at

AmazonGoogle

Remove and validate — test candidates from the end

The direct approach follows the tie-break rule literally. Try removing edges from right to left, rebuild the remaining graph, and use cycle detection plus connectivity to test whether it is a tree. The first candidate that works is the last valid answer.

def find_redundant_connection(edges: list[list[int]]) -> list[int]:
    n = len(edges)
 
    def is_tree_without(skip: int) -> bool:
        graph = [[] for _ in range(n + 1)]
        for i, (a, b) in enumerate(edges):
            if i == skip:
                continue
            graph[a].append(b)
            graph[b].append(a)
 
        seen = {1}
        stack = [(1, 0)]
        while stack:
            node, parent = stack.pop()
            for neighbor in graph[node]:
                if neighbor == parent:
                    continue
                if neighbor in seen:
                    return False
                seen.add(neighbor)
                stack.append((neighbor, node))
        return len(seen) == n
 
    for i in range(n - 1, -1, -1):
        if is_tree_without(i):
            return edges[i]
    return []

Each of n candidates rebuilds and walks a graph of size n.

Time O(n²), space O(n) for one candidate's adjacency list and traversal state.

Union-find — find the edge that closes the cycle

Union-find, also called disjoint-set union, tracks the connected group containing each node. Process the edges in order. If an edge joins different roots, merge them. If its endpoints already share a root, a path between them already exists, so this edge closes the cycle.

def find_redundant_connection(edges: list[list[int]]) -> list[int]:
    n = len(edges)
    parent = list(range(n + 1))
    size = [1] * (n + 1)
 
    def find(node: int) -> int:
        while node != parent[node]:
            parent[node] = parent[parent[node]]
            node = parent[node]
        return node
 
    for a, b in edges:
        root_a = find(a)
        root_b = find(b)
        if root_a == root_b:
            return [a, b]
 
        if size[root_a] < size[root_b]:
            root_a, root_b = root_b, root_a
        parent[root_b] = root_a
        size[root_a] += size[root_b]
 
    return []

Why does the first cycle-closing edge satisfy “last in the input”? Before that edge arrives, the other cycle edges form only a path. The last listed edge on that cycle is the one that finally joins two already-connected endpoints.

Time O(n·α(n)), space O(n) — path compression and union by size make each operation amortized α(n), effectively constant for practical inputs.

This is union-find's signature move: detect the exact moment a new undirected edge adds no new connectivity.

Loading editor

Console

ready to run

Ready to run.

3 cases are queued.

Visible testcase

Case 1

Arguments · JSON arrayedges: int[][]

Expected

[
  2,
  3
]

Run: visible + custom · Submit: full suite