LeetCode 684 - Redundant Connection

LeetCode Problem 684

Difficulty: 🟡 Medium
Topics: Depth-First Search, Breadth-First Search, Union-Find, Graph Theory

Solution

Problem Understanding

The problem is asking us to identify a redundant edge in a graph that started as a tree. A tree is a connected graph with n nodes and exactly n-1 edges, meaning it has no cycles. The input graph has n nodes and n edges, so by definition, it contains exactly one cycle. The extra edge is the one creating this cycle, and our task is to identify it.

The input is an array of edges, where each edge is represented as a pair [ai, bi] of connected nodes. The expected output is a single edge from this array, specifically the edge that, if removed, restores the tree property (connected and acyclic). If multiple edges could be removed, the one appearing last in the input array should be returned.

Constraints clarify that n is at most 1000, which rules out extremely inefficient brute-force approaches. Each node is labeled from 1 to n, edges are unique, and the graph is always connected. These guarantees simplify the problem: we do not need to check for disconnected components or repeated edges.

Edge cases to note include a minimal tree with 3 nodes (smallest possible cycle), an edge connecting nodes with high indices, and cycles involving multiple nodes where the last edge in input must be returned. These could trip up naive DFS implementations if not careful about the “last edge” requirement.

Approaches

A brute-force approach would attempt to remove each edge in turn and check if the remaining graph is a tree. This could be done by performing a DFS or BFS to check connectivity and cycles after removing each edge. While correct, this method is slow: for n edges, checking connectivity via DFS is O(n) for each removal, leading to O(n^2) overall time complexity. Given the upper bound n = 1000, this can be inefficient.

The key insight is that a cycle forms when two nodes in the same connected component are joined. Union-Find (Disjoint Set Union) is a data structure designed to efficiently track connected components and detect cycles. As we iterate over edges, if the two nodes of an edge are already connected, adding this edge would form a cycle, making it the redundant connection. This approach leverages the graph's acyclic nature and is efficient.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^2)	O(n)	Remove each edge, then check connectivity using DFS/BFS
Union-Find (Optimal)	O(n α(n))	O(n)	Track connected components efficiently, α(n) is inverse Ackermann function

Algorithm Walkthrough

1. Initialize a Union-Find (Disjoint Set Union) structure for all n nodes. Each node starts as its own parent, representing a separate component.
2. Iterate over each edge [u, v] in the input array.
3. For each edge, use the Union-Find find operation to determine the root (representative) of both nodes u and v.
4. If the roots are the same, the nodes are already connected. Adding this edge would create a cycle, so it is the redundant connection. Return [u, v].
5. If the roots are different, union the two components using the Union-Find union operation, connecting their components without forming a cycle.
6. Continue until all edges are processed. By problem guarantees, exactly one edge will cause a cycle, and it will be detected.

Why it works: Union-Find maintains the invariant that nodes in the same component share the same root. A cycle is detected precisely when an edge connects two nodes with the same root, ensuring we return the last edge causing a cycle as required.

Python Solution

from typing import List

class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        parent = list(range(len(edges) + 1))
        
        def find(x: int) -> int:
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]
        
        def union(x: int, y: int) -> bool:
            root_x, root_y = find(x), find(y)
            if root_x == root_y:
                return False
            parent[root_y] = root_x
            return True
        
        for u, v in edges:
            if not union(u, v):
                return [u, v]

The implementation initializes a parent array representing each node's root. The find function performs path compression for efficiency. The union function connects two components and returns False if they were already connected, signaling a cycle. The main loop iterates over edges and immediately returns the first edge causing a cycle, which corresponds to the last edge in the input creating the cycle.

Go Solution

func findRedundantConnection(edges [][]int) []int {
    parent := make([]int, len(edges)+1)
    for i := range parent {
        parent[i] = i
    }

    var find func(int) int
    find = func(x int) int {
        if parent[x] != x {
            parent[x] = find(parent[x])
        }
        return parent[x]
    }

    union := func(x, y int) bool {
        rootX, rootY := find(x), find(y)
        if rootX == rootY {
            return false
        }
        parent[rootY] = rootX
        return true
    }

    for _, edge := range edges {
        if !union(edge[0], edge[1]) {
            return edge
        }
    }
    return nil
}

In Go, we similarly maintain a parent slice for Union-Find. The find function recursively compresses paths, and union merges components or returns false when a cycle is detected. The solution directly mirrors the Python logic, handling slice indexing and function closures idiomatically.

Worked Examples

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

Edge	find(1)	find(2)	Union?	Parent array after union
[1,2]	1	2	Yes	[0,1,1,3]
[1,3]	1	3	Yes	[0,1,1,1]
[2,3]	1	1	No	Cycle detected, return [2,3]

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

Edge	find(u)	find(v)	Union?	Parent array after union
[1,2]	1	2	Yes	[0,1,1,3,4,5]
[2,3]	1	3	Yes	[0,1,1,1,4,5]
[3,4]	1	4	Yes	[0,1,1,1,1,5]
[1,4]	1	1	No	Cycle detected, return [1,4]
[1,5]	Not reached

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n α(n))	Each find is nearly O(1) due to path compression; iterating edges is O(n)
Space	O(n)	Parent array stores component representatives for n nodes

The Union-Find structure with path compression ensures almost constant-time union and find operations. Space scales linearly with the number of nodes, which is small enough given constraints.

Test Cases

# Provided examples
assert Solution().findRedundantConnection([[1,2],[1,3],[2,3]]) == [2,3]  # simple 3-node cycle
assert Solution().findRedundantConnection([[1,2],[2,3],[3,4],[1,4],[1,5]]) == [1,4]  # 4-node cycle

# Minimal cycle
assert Solution().findRedundantConnection([[1,2],[1,3],[2,3]]) == [2,3]  # minimal input n=3

# Last edge is redundant
assert Solution().findRedundantConnection([[1,2],[2,3],[3,4],[4,1]]) == [4,1]

# Larger tree with redundant edge in the middle
edges = [[i,i+1] for i in range(1,1000)] + [[500,1000]]
assert Solution().findRedundantConnection(edges) == [500,1000]

# Redundant edge connects first and last nodes
assert Solution().findRedundantConnection([[1,2],[2,3],[3,4],[4,5],[1,5]]) == [1,5]

Test	Why
Simple 3-node cycle	Validates minimal input
4-node cycle	Checks middle-of-list redundant edge detection
Last edge redundant	Ensures algorithm detects last cycle-causing edge
Large tree with middle redundant edge	Tests performance on upper-bound input
First-last node redundant	Validates correctness with edge indices across the graph

Edge Cases

A key edge case is the smallest possible tree (3 nodes). This could trip up implementations that assume more nodes are present