Redundant Connection

MEDIUM✓ CHIP-TIMEDLC #684 — FULL STATEMENT ↗

The drill: A tree of n nodes had exactly one extra edge added to it, turning it into a graph with n nodes and n edges and exactly one cycle. Find that one extra edge — if more than one edge could be removed to restore a tree, return whichever one appears last in the input.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A graph starts life as a valid tree of n nodes, then gains exactly one extra edge — leaving n nodes and n edges total, and exactly one cycle somewhere in the structure. The task is to identify that one extra edge.

Removing the right edge from the cycle restores a valid tree; several edges along that cycle might work equally well for restoring a tree, so the tie is broken by picking whichever edge appears last in the input order.

The answer is that single edge, given as its two endpoint node numbers, exactly as it appeared in the input list.

EX 01

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

→ [2, 3]

A BARE TRIANGLE

EX 02

edges = [[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]]

→ [1, 4]

A SQUARE WITH A HANGING LEAF

EX 03

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

→ [3, 1]

SAME TRIANGLE, EDGES IN A DIFFERENT ORDER

up to a few thousand edges, matching the number of nodes
edges are undirected, listed in the order they were added
exactly one edge is redundant — removing it always restores a tree
when multiple edges could work, the one appearing latest in the input wins

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

A tree on n nodes needs exactly n−1 edges. One extra edge means exactly one cycle exists somewhere, and removing the right single edge from that cycle is enough to make everything a tree again.

HINT 2 THE STRUCTURE

The redundant edge is the one connecting two nodes that were already reachable from each other through earlier edges — everything before it was still building a tree cleanly.

HINT 3 ONE STEP FROM THE ANSWER

Walk the edges in order, union each pair's endpoints, and the moment an edge's two endpoints already share a root, that edge is the answer — it's the one closing the cycle.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE EDGE THAT CLOSES THE LOOPPATTERN · UNION-FIND, ONE PASSedges: (1,2) (1,3) (2,3)

STEP 1

Union-find each edge left to right — the first edge whose endpoints already share a root is the redundant one.

STEP 1 / 5 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/redundant-connection.py — RACE PACE

LANG ▸

PACE ▸

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

        def find(x):
            while parent[x] != x:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x

        for a, b in edges:
            ra, rb = find(a), find(b)
            if ra == rb:
                return [a, b]
            parent[ra] = rb
        return []

TIME O(E·Α(V))SPACE O(V)PYTHON · RACE PACE · 17 LN

class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        n = len(edges)
        all_nodes = set()
        for a, b in edges:
            all_nodes.add(a)
            all_nodes.add(b)

        def is_valid_tree(skip_idx):
            graph = collections.defaultdict(list)
            for i, (a, b) in enumerate(edges):
                if i == skip_idx:
                    continue
                graph[a].append(b)
                graph[b].append(a)

            start = next(iter(all_nodes))
            visited = {start}
            stack = [start]
            while stack:
                node = stack.pop()
                for nxt in graph[node]:
                    if nxt not in visited:
                        visited.add(nxt)
                        stack.append(nxt)
            # connected across every original node, using exactly n - 1 edges —
            # that combination can only be a tree, no separate cycle check needed
            return visited == all_nodes

        for i in range(n - 1, -1, -1):
            if is_valid_tree(i):
                return edges[i]
        return []

TIME O(E·(V+E))SPACE O(V+E)PYTHON · TRAINING PACE · 33 LN

class Solution {
    public int[] findRedundantConnection(int[][] edges) {
        int n = edges.length;
        int[] parent = new int[n + 1];
        for (int i = 0; i <= n; i++) parent[i] = i;

        for (int[] e : edges) {
            int ra = find(parent, e[0]);
            int rb = find(parent, e[1]);
            if (ra == rb) return e;
            parent[ra] = rb;
        }
        return new int[0];
    }

    private int find(int[] parent, int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }
}

TIME O(E·Α(V))SPACE O(V)JAVA · RACE PACE · 23 LN

class Solution {
    private int[][] edges;
    private Set<Integer> allNodes;

    public int[] findRedundantConnection(int[][] edges) {
        this.edges = edges;
        allNodes = new HashSet<>();
        for (int[] e : edges) {
            allNodes.add(e[0]);
            allNodes.add(e[1]);
        }
        for (int i = edges.length - 1; i >= 0; i--) {
            if (isValidTree(i)) return edges[i];
        }
        return new int[0];
    }

    private boolean isValidTree(int skipIdx) {
        Map<Integer, List<Integer>> graph = new HashMap<>();
        for (int i = 0; i < edges.length; i++) {
            if (i == skipIdx) continue;
            int a = edges[i][0], b = edges[i][1];
            graph.computeIfAbsent(a, k -> new ArrayList<>()).add(b);
            graph.computeIfAbsent(b, k -> new ArrayList<>()).add(a);
        }

        int start = allNodes.iterator().next();
        Set<Integer> visited = new HashSet<>();
        visited.add(start);
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(start);
        while (!stack.isEmpty()) {
            int node = stack.pop();
            for (int nxt : graph.getOrDefault(node, Collections.emptyList())) {
                if (visited.add(nxt)) stack.push(nxt);
            }
        }
        // connected across every original node, using exactly n - 1 edges —
        // that combination can only be a tree, no separate cycle check needed
        return visited.equals(allNodes);
    }
}

TIME O(E·(V+E))SPACE O(V+E)JAVA · TRAINING PACE · 42 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED