Redundant Connection

Medium Problem 111 of 151 Java and Python

Problem

A tree with n nodes (labelled 1 to n) had one extra edge added. The result is given as edges, in order.

Return an edge that can be removed so the graph becomes a tree again. If there are several answers, return the one that appears last in the input.

Example 1

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

Example 2

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

Constraints

3 ≤ n ≤ 1000
No repeated edges; the graph is connected.

Explanation

Add the edges one by one. The first edge whose two ends are already connected closes the cycle, so it is redundant. Because the graph has exactly one cycle, that edge is also the last cycle edge in the input order.

Union-Find answers "already connected?" in near-constant time.

Approach 1 · Naive

DFS before adding each edge

Time O(n²)
Space O(n)

Before adding edge (u, v), DFS from u over the edges added so far. If v is reachable, this edge is redundant.

Keep an adjacency list of edges added so far.
For each edge, if v is reachable from u, return it; otherwise add it.

Java

import java.util.*;

class Solution {
    public int[] findRedundantConnection(int[][] edges) {
        int n = edges.length;
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }
        for (int[] e : edges) {
            if (reachable(graph, e[0], e[1], new boolean[n + 1])) {
                return e;
            }
            graph.get(e[0]).add(e[1]);
            graph.get(e[1]).add(e[0]);
        }
        return new int[0];
    }

    private boolean reachable(List<List<Integer>> graph, int from, int to, boolean[] seen) {
        if (from == to) {
            return true;
        }
        seen[from] = true;
        for (int next : graph.get(from)) {
            if (!seen[next] && reachable(graph, next, to, seen)) {
                return true;
            }
        }
        return false;
    }
}

Python

from collections import defaultdict

class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        graph = defaultdict(list)

        def reachable(start, target):
            seen, stack = {start}, [start]
            while stack:
                node = stack.pop()
                if node == target:
                    return True
                for nxt in graph[node]:
                    if nxt not in seen:
                        seen.add(nxt)
                        stack.append(nxt)
            return False

        for u, v in edges:
            if reachable(u, v):
                return [u, v]
            graph[u].append(v)
            graph[v].append(u)
        return []

Approach 2 · Optimal

Union-Find

Time O(n · α(n))
Space O(n)

Union the two ends of each edge. If they already share a root, return this edge.

parent[i] = i for 1…n.
For each edge: if find(u) == find(v), return it; otherwise union them.

Java

class Solution {
    public int[] findRedundantConnection(int[][] edges) {
        int[] parent = new int[edges.length + 1];
        for (int i = 0; i < parent.length; i++) {
            parent[i] = i;
        }
        for (int[] e : edges) {
            int a = find(parent, e[0]);
            int b = find(parent, e[1]);
            if (a == b) {
                return e;
            }
            parent[a] = b;
        }
        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;
    }
}

Python

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

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

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

Complexity compared

Approach	Time	Space
Naive DFS before adding each edge	O(n²)	O(n)
Optimal Union-Find	O(n · α(n))	O(n)

Key takeaways

Union-Find detects cycles in an undirected graph as edges arrive; for directed graphs use DFS colours or topological sort.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem