Skip to content

119 — Redundant Connection

Jump to bottom
rebeloper edited this page Jul 14, 2026 · 4 revisions

119 — Redundant Connection

LeetCode 684 · Medium. A tree with n nodes had one extra edge added, turning it into a graph with exactly one cycle. Given the edge list (in the order they were added), return the edge that, if removed, restores a valid tree. If multiple such edges exist, return the last one appearing in the input.

🍽️ Intuition

A tree with n nodes has exactly n - 1 edges and no cycles. Add one more edge, and by definition you've created exactly one cycle — the "redundant" edge is whichever one closes that loop. The key realization: an edge closes a cycle precisely when it connects two nodes that were already connected to each other before this edge was added. If nodes u and v are already reachable from each other, adding another edge between them can't help connectivity — it can only create a cycle. So the question "which edge is redundant" becomes "process edges in order, and find the first one that connects two nodes already in the same connected component" — which is exactly what Union-Find is built to answer, incrementally, as edges are added one at a time.

🚩 Pattern-Recognition Cue

"Find the edge that creates a cycle, given edges added one at a time" is the cue for Union-Find: process edges in order, and the first union that fails (because both endpoints are already connected) identifies the redundant edge.

🐢 Brute Force

For each edge (checked from the end of the list backward, since the answer must be the last qualifying edge), tentatively remove it and run a fresh traversal to check whether the remaining n - 1 edges still connect all n nodes.

func findRedundantConnectionBruteForce(_ edges: [[Int]]) -> [Int] {
    let n = edges.count

    func isValidTree(excluding excludedIndex: Int) -> Bool {
        var adjacency = Array(repeating: [Int](), count: n + 1)
        for (i, edge) in edges.enumerated() where i != excludedIndex {
            adjacency[edge[0]].append(edge[1])
            adjacency[edge[1]].append(edge[0])
        }
        var visited = Array(repeating: false, count: n + 1)
        var stack = [1]
        visited[1] = true
        var count = 1
        while let node = stack.popLast() {
            for neighbor in adjacency[node] where !visited[neighbor] {
                visited[neighbor] = true
                count += 1
                stack.append(neighbor)
            }
        }
        return count == n   // all n nodes (1...n) reached using n-1 edges
    }

    for i in stride(from: n - 1, through: 0, by: -1) {
        if isValidTree(excluding: i) {
            return edges[i]
        }
    }
    return []
}

Big-O: O(n²) — up to n candidate edges tested, each requiring a fresh O(n) traversal to rebuild and re-check connectivity.

🚀 Optimal

Union-Find with path compression and union by rank: process edges left to right, and the first edge whose two endpoints are already in the same set is the redundant one.

final class UnionFind {
    private var parent: [Int]
    private var rank: [Int]

    init(_ n: Int) {
        parent = Array(0...n)
        rank = Array(repeating: 0, count: n + 1)
    }

    func find(_ x: Int) -> Int {
        if parent[x] != x {
            parent[x] = find(parent[x])   // path compression
        }
        return parent[x]
    }

    // Returns false if x and y were already connected (union rejected).
    func union(_ x: Int, _ y: Int) -> Bool {
        let rootX = find(x), rootY = find(y)
        if rootX == rootY { return false }
        if rank[rootX] < rank[rootY] {
            parent[rootX] = rootY
        } else if rank[rootX] > rank[rootY] {
            parent[rootY] = rootX
        } else {
            parent[rootY] = rootX
            rank[rootX] += 1
        }
        return true
    }
}

func findRedundantConnection(_ edges: [[Int]]) -> [Int] {
    let uf = UnionFind(edges.count)
    for edge in edges {
        if !uf.union(edge[0], edge[1]) {
            return edge
        }
    }
    return []
}

// smoke test
print(findRedundantConnection([[1,2],[1,3],[2,3]]))               // [2, 3]
print(findRedundantConnection([[1,2],[2,3],[3,4],[1,4],[1,5]]))    // [1, 4]

Big-O: O(n · α(n)) time, where α is the inverse Ackermann function (effectively constant) — each union/find call is near-O(1) amortized thanks to path compression and union by rank. O(n) space.

🔑 The Key Insight

The brute force answers "is this edge the redundant one?" by removing it and independently re-verifying full connectivity from scratch — a fresh O(n) traversal per candidate. Union-Find instead answers the equivalent question incrementally and forward: as each edge is added, ask "are these two endpoints already connected?" If a union ever fails, that edge — and no other — is the one that closes a cycle, because every earlier edge was verified to legitimately grow the tree without creating one. There's no need to ever undo or re-check anything; Union-Find's incremental structure makes the answer fall out as a natural byproduct of processing edges in order, rather than something that has to be verified after the fact.

🔗 Related Chapters

  • Union-Find — path compression and union by rank are exactly the two optimizations that make find/union amortized near-O(1), covered in full there.
  • Union-Find Pattern — "process edges one at a time, and the first union that fails reveals the answer" is the canonical Union-Find problem shape.
  • Graphs — the underlying fact that a connected graph with n nodes and n-1 edges is a tree (and one more edge always creates exactly one cycle) is basic graph theory from that chapter.

🧸 Memory Sentence

Redundant Connection is Union-Find catching a cycle in the act — process edges in order, and the first union that fails because both endpoints are already connected is the edge to remove.

✅ Check Your Understanding

  1. Why must the answer always be processed in the same order the edges were added — what would go wrong if findRedundantConnection processed the edges in reverse or sorted order instead?
  2. Walk through find on a chain parent = [0, 1, 1, 2] (nodes 1→2→3, i.e. parent[3] = 2, parent[2] = 1) calling find(3). What does parent look like immediately afterward, and why?
  3. Why does union by rank alone (without path compression) still keep find fast, and what specific scenario does path compression additionally protect against?

⬅️ Previous: Course Schedule II · Next: Number of Connected Components in an Undirected Graph ➡️

Clone this wiki locally