684. Redundant Connection (Medium)

Problem

A tree on n nodes can be represented by n - 1 edges. You’re given an array of n edges such that, with one edge added, the resulting graph has exactly one cycle. Return the added edge. If multiple answers, return the one that appears last in the input.

Example

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

LeetCode 684 · Link · Medium

Try it yourself

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Brute force, for each edge, test if removing it makes the graph a tree

Swift

final class Solution {
    func findRedundantConnection(_ edges: [[Int]]) -> [Int] {
        let n = edges.count
        for removed in edges.indices.reversed() {
            var graph = Array(repeating: [Int](), count: n + 1)
            for index in edges.indices where index != removed {
                let edge = edges[index]; graph[edge[0]].append(edge[1]); graph[edge[1]].append(edge[0])
            }
            var seen = Set<Int>(), stack = [1]
            while let node = stack.popLast() { if seen.insert(node).inserted { stack.append(contentsOf: graph[node]) } }
            if seen.count == n { return edges[removed] }
        }
        return []
    }
}

Remove each edge in turn; run a DFS/BFS on the rest; test for connectivity and acyclicity.

Complexity

Time: $O(V²)$ , driven by V iterations each triggering an $O(V)$ tree-check call.
Space: $O(V)$ for the adjacency list and DFS stack.

Approach 2: DFS to find the cycle, pick the last edge on it

Swift

final class Solution {
    func findRedundantConnection(_ edges: [[Int]]) -> [Int] {
        let n = edges.count
        var graph = Array(repeating: [Int](), count: n + 1)
        for edge in edges { graph[edge[0]].append(edge[1]); graph[edge[1]].append(edge[0]) }
        func connected(_ start: Int, _ target: Int, _ skipped: [Int]) -> Bool {
            var seen = Set<Int>(), stack = [start]
            while let node = stack.popLast() {
                if node == target { return true }
                if seen.insert(node).inserted {
                    for next in graph[node] where !((node == skipped[0] && next == skipped[1]) || (node == skipped[1] && next == skipped[0])) { stack.append(next) }
                }
            }
            return false
        }
        for edge in edges.reversed() where connected(edge[0], edge[1], edge) { return edge }
        return []
    }
}

Build the full graph; run a DFS that finds a back edge, walk the parent chain to collect all edges on the cycle, then iterate the input edges in reverse and return the first one whose index is in the cycle.

Complexity

Time: $O(V + E)$ .
Space: $O(V + E)$ for the graph and recursion stack.

Approach 3: Union-Find (canonical)

Process edges in order. For each (u, v): if u and v are already in the same component, this edge creates a cycle, return it. Otherwise, union them.

def find_redundant_connection(edges):
    n = len(edges)                              # L1: n edges
    parent = list(range(n + 1))                 # L2: O(n) init, node i is its own root

    def find(x):                                # L3: path-halving find
        while parent[x] != x:                  # L4: walk to root
            parent[x] = parent[parent[x]]      # L5: path halving (compress by 2)
            x = parent[x]                      # L6: move up
        return x

    def union(a, b):                            # L7: union two components
        ra, rb = find(a), find(b)              # L8: find both roots
        if ra == rb:                            # L9: same component = cycle
            return False
        parent[ra] = rb                         # L10: merge
        return True

    for u, v in edges:                          # L11: process each edge
        if not union(u, v):                     # L12: cycle detected
            return [u, v]
    return []

function findRedundantConnection(edges: number[][]): number[] {
    const n = edges.length;                             // L1: n edges
    const parent = Array.from({ length: n + 1 }, (_, i) => i);  // L2: O(n) init

    function find(x: number): number {                  // L3: path-halving find
        while (parent[x] !== x) {                       // L4: walk to root
            parent[x] = parent[parent[x]];              // L5: path halving
            x = parent[x];                             // L6: move up
        }
        return x;
    }

    function union(a: number, b: number): boolean {     // L7: union two components
        const ra = find(a), rb = find(b);               // L8: find both roots
        if (ra === rb) return false;                    // L9: same component = cycle
        parent[ra] = rb;                                // L10: merge
        return true;
    }

    for (const [u, v] of edges) {                       // L11: process each edge
        if (!union(u, v)) return [u, v];               // L12: cycle detected
    }
    return [];
}

struct UnionFind {
    var parent: [Int]
    var rank: [Int]
    init(_ count: Int) { parent = Array(0..<count); rank = Array(repeating: 0, count: count) }
    mutating func find(_ value: Int) -> Int {
        if parent[value] != value { parent[value] = find(parent[value]) }
        return parent[value]
    }
    mutating func union(_ left: Int, _ right: Int) -> Bool {
        var a = find(left), b = find(right)
        if a == b { return false }
        if rank[a] < rank[b] { swap(&a, &b) }
        parent[b] = a
        if rank[a] == rank[b] { rank[a] += 1 }
        return true
    }
}

final class Solution {
    func findRedundantConnection(_ edges: [[Int]]) -> [Int] {
        var unionFind = UnionFind(edges.count + 1)
        for edge in edges where !unionFind.union(edge[0], edge[1]) { return edge }
        return []
    }
}

Where the time goes, line by line

Variables: V = number of vertices = len(edges), E = len(edges).

Line	Per-call cost	Times executed	Contribution
L2 (init parent)	$O(V)$	1	$O(V)$
L4-L6 (find, path-halving)	$O(α(V)$ ) amortized	2 per edge = 2V	$O(V · α(V)$ )
L9 (same-component test)	$O(1)$	V	$O(V)$
L10 (merge)	$O(1)$	up to V - 1	$O(V)$
L11-L12 (edge loop + union)	$O(α(V)$ ) per edge	V	$O(V · α(V)$ ) ← dominates

Complexity

Time: $O(V · α(V)$ ) ≈ $O(V)$ , driven by L11-L12 (V union operations each costing $O(α(V)$ ) amortized).
Space: $O(V)$ for the parent array.

Why this works

If the graph has exactly one cycle, then exactly one edge causes a “same-component” event when processed in order. All edges preceding it form a forest; this edge closes a cycle. Since input is a tree plus one edge, that closing edge is the answer.

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

Summary

Approach	Time	Space
Per-edge removal + tree check	$O(V²)$	$O(V)$
Cycle-finding DFS	$O(V)$	$O(V)$
Union-Find	$O(V · α(V)$ )	$O(V)$

Union-Find is the canonical solution and the template for any incremental connectivity problem.

# Quick smoke tests, paste into a REPL or save as test_684.py and run.
# Uses the canonical implementation (Approach 3, Union-Find).

def find_redundant_connection(edges):
    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

    def union(a, b):
        ra, rb = find(a), find(b)
        if ra == rb:
            return False
        parent[ra] = rb
        return True

    for u, v in edges:
        if not union(u, v):
            return [u, v]
    return []

def _run_tests():
    # LeetCode example 1
    assert find_redundant_connection([[1,2],[1,3],[2,3]]) == [2, 3]

    # LeetCode example 2
    assert find_redundant_connection([[1,2],[2,3],[3,4],[1,4],[1,5]]) == [1, 4]

    # Smallest possible cycle (two nodes, two edges between them)
    assert find_redundant_connection([[1,2],[1,2]]) == [1, 2]

    # Last edge is redundant
    assert find_redundant_connection([[1,2],[2,3],[1,3]]) == [1, 3]

    # Longer chain with cycle at end
    assert find_redundant_connection([[1,2],[2,3],[3,4],[4,5],[3,5]]) == [3, 5]

    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

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

    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 {
        const ra = find(a), rb = find(b);
        if (ra === rb) return false;
        parent[ra] = rb;
        return true;
    }

    for (const [u, v] of edges) if (!union(u, v)) return [u, v];
    return [];
}

console.assert(JSON.stringify(findRedundantConnection([[1,2],[1,3],[2,3]])) === JSON.stringify([2,3]));
console.assert(JSON.stringify(findRedundantConnection([[1,2],[2,3],[3,4],[1,4],[1,5]])) === JSON.stringify([1,4]));
console.assert(JSON.stringify(findRedundantConnection([[1,2],[1,2]])) === JSON.stringify([1,2]));
console.assert(JSON.stringify(findRedundantConnection([[1,2],[2,3],[1,3]])) === JSON.stringify([1,3]));
console.assert(JSON.stringify(findRedundantConnection([[1,2],[2,3],[3,4],[4,5],[3,5]])) === JSON.stringify([3,5]));
console.log("all tests pass");

Graphs, union-find for cycle detection in undirected graphs

Cycle Detection, repeated-state tactics for finding loops in linked lists, graphs, arrays, and numeric processes.
Union Find, disjoint-set tactics for tracking connected components as edges arrive.

684. Redundant Connection (Medium)

Problem

Try it yourself

Approach 1: Brute force, for each edge, test if removing it makes the graph a tree

Approach 2: DFS to find the cycle, pick the last edge on it

Approach 3: Union-Find (canonical)

Why this works

Summary

Test cases

Related data structures

Related concepts