LeetCode 684: Redundant Connection Solution in Python – A Step-by-Step Guide

What Is LeetCode 684: Redundant Connection?

In LeetCode 684: Redundant Connection, you’re given a list edges of integer pairs [u, v], representing undirected connections between nodes numbered 1 to n, where n is the number of nodes. The graph has n edges, forming a tree (n-1 edges) plus one extra edge that creates a cycle. Your task is to find the redundant edge that, when removed, makes the graph a tree (acyclic and connected). Return this edge as an array [u, v] (the one appearing last in the input if multiple exist). For example, with edges = [[1, 2], [1, 3], [2, 3]], removing [2, 3] leaves a tree, so return [2, 3]. This problem tests your ability to detect cycles in an undirected graph efficiently.

Problem Statement

• Input:
• edges: List of lists, where each inner list [u, v] is an undirected edge.
• Output: A list [u, v]—the redundant edge to remove.
• Rules:
• Graph has n nodes and n edges (tree + 1 edge).
• Nodes numbered 1 to n.
• Return edge causing cycle, last in input if multiple options.
• Resulting graph must be a tree (n-1 edges, no cycles).

Constraints

• n == edges.length.
• 3 ≤ n ≤ 1000.
• edges[i].length == 2.
• 1 ≤ edges[i][0], edges[i][1] ≤ n.
• No duplicate edges or self-loops.

Examples

• Input: edges = [[1, 2], [1, 3], [2, 3]]
• Output: [2, 3] (Removes cycle 1-2-3)
• Input: edges = [[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]]
• Output: [1, 4] (Removes cycle 1-2-3-4)
• Input: edges = [[1, 2], [2, 3], [1, 3]]
• Output: [1, 3] (Removes cycle 1-2-3)

These examples set the network—let’s solve it!

Understanding the Problem: Finding the Redundant Edge

To solve LeetCode 684: Redundant Connection in Python, we need to identify the edge in edges that creates a cycle in an undirected graph with n nodes and n edges, returning the last such edge to make the graph a tree (n-1 edges, no cycles). A brute-force approach—building the graph and checking cycles for each edge—would be O(n²), inefficient for n ≤ 1000. Since we’re detecting the first cycle-forming edge in a sequence, Union-Find or DFS can optimize this. We’ll use:

• Best Solution (Union-Find with Path Compression): O(n * α(n)) time, O(n) space—near-linear and optimal.
• Alternative Solution (DFS with Cycle Detection): O(n²) time, O(n) space—intuitive but slower.

Let’s start with the Union-Find solution, breaking it down for beginners.

Best Solution: Union-Find with Path Compression

Why This Is the Best Solution

The Union-Find with path compression approach is the top choice for LeetCode 684 because it’s highly efficient—O(n * α(n)) time with O(n) space, where α(n) is the inverse Ackermann function, nearly constant—and uses a disjoint-set data structure to detect cycles by tracking connected components as edges are added. It fits constraints (n ≤ 1000) perfectly and is intuitive once you see the union-find logic. It’s like connecting nodes and spotting the wire that loops back!

How It Works

Think of this as a network connector:

• Step 1: Initialize Union-Find:
• parent[i] = i: Each node starts as its own set.
• rank[i] = 0: For union by rank optimization.
• Step 2: Find Function:
• find(x): Return root of x’s set with path compression.
• Step 3: Union Function:
• union(u, v): Merge sets of u and v, return False if already connected (cycle).
• Step 4: Process Edges:
• For each edge [u, v]:
• If union(u-1, v-1) returns False, it’s redundant, return [u, v].
• Step 5: Return Result:
• Last edge causing cycle is returned.

It’s like a set merger—connect and detect!

Step-by-Step Example

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

• Step 1: Init:
• parent = [0, 1, 2], rank = [0, 0, 0] (0-based indices).
• Step 2: Process edges:
• [1, 2]:
• find(0) = 0, find(1) = 1.
• union(0, 1): parent[1] = 0, rank[0] = 1.
• parent = [0, 0, 2].
• [1, 3]:
• find(0) = 0, find(2) = 2.
• union(0, 2): parent[2] = 0.
• parent = [0, 0, 0].
• [2, 3]:
• find(1) = 0 (path compression), find(2) = 0.
• union(1, 2): Same root (0), cycle detected, return [2, 3].
• Step 5: Return [2, 3].
• Output: [2, 3].

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained clearly:

class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        # Step 1: Initialize Union-Find
        n = len(edges)
        parent = list(range(n))  # 0-based indices
        rank = [0] * n

        # Step 2: Find function with path compression
        def find(x: int) -> int:
            if parent[x] != x:
                parent[x] = find(parent[x])  # Path compression
            return parent[x]

        # Step 3: Union function with rank
        def union(u: int, v: int) -> bool:
            root_u = find(u)
            root_v = find(v)
            if root_u == root_v:  # Already connected, cycle
                return False
            # Union by rank
            if rank[root_u] < rank[root_v]:
                parent[root_u] = root_v
            elif rank[root_u] > rank[root_v]:
                parent[root_v] = root_u
            else:
                parent[root_v] = root_u
                rank[root_u] += 1
            return True

        # Step 4: Process edges
        for u, v in edges:
            if not union(u - 1, v - 1):  # Adjust to 0-based
                return [u, v]

        # Step 5: No redundant edge (shouldn’t happen per problem)
        return []

• Lines 4-7: Init: Parent as self, rank as 0.
• Lines 10-13: find: Recursive root finding with path compression.
• Lines 16-28: union: Merge sets, return False if cycle.
• Lines 31-34: Process: Union each edge, return redundant one.
• Time Complexity: O(n * α(n))—near-linear with path compression.
• Space Complexity: O(n)—parent and rank arrays.

This is like a network untangler—merge and spot!

Alternative Solution: DFS with Cycle Detection

Why an Alternative Approach?

The DFS with cycle detection approach builds an adjacency list—O(n²) time, O(n) space. It’s more intuitive, tracing paths to find cycles, but slower due to graph traversal. It’s like walking the network to find where it loops back!

How It Works

Picture this as a path tracer:

• Step 1: Build adjacency list from edges.
• Step 2: DFS for cycle:
• Start at each node, track visited and parent.
• If revisit a node (not parent), cycle found.
• Step 3: Check each edge removal:
• Remove edge, DFS to see if cycle gone.
• Step 4: Return last edge causing cycle.

It’s like a cycle hunter—trace and remove!

Step-by-Step Example

Example: Same as above

• Step 1: Adjacency list:
• 1: [2, 3], 2: [1, 3], 3: [1, 2].
• Step 2: DFS from 1:
• 1→2→3→1 (cycle 1-2-3).
• Step 3: Check removals:
• Remove [1, 2]: 1-3, 2-3, no cycle.
• Remove [1, 3]: 1-2, 2-3, no cycle.
• Remove [2, 3]: 1-2, 1-3, no cycle, last edge, return [2, 3].
• Output: [2, 3].

Code for DFS Approach

class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        # Step 1: Build adjacency list
        n = len(edges)
        adj = [[] for _ in range(n + 1)]  # 1-based nodes
        for u, v in edges:
            adj[u].append(v)
            adj[v].append(u)

        # Step 2: DFS to detect cycle
        def dfs(node: int, parent: int, visited: set) -> bool:
            visited.add(node)
            for neighbor in adj[node]:
                if neighbor != parent:
                    if neighbor in visited or dfs(neighbor, node, visited):
                        return True
            return False

        # Step 3: Check each edge removal
        for i in range(n - 1, -1, -1):  # Check in reverse order
            u, v = edges[i]
            adj[u].remove(v)
            adj[v].remove(u)
            visited = set()
            has_cycle = False
            for start in range(1, n + 1):
                if start not in visited and dfs(start, 0, visited):
                    has_cycle = True
                    break
            if not has_cycle:
                return [u, v]
            adj[u].append(v)
            adj[v].append(u)

        # Step 4: No redundant edge (shouldn’t happen)
        return []

• Lines 4-9: Build: Adjacency list for undirected graph.
• Lines 12-18: dfs: Detect cycle via DFS.
• Lines 21-35: Check: Remove each edge, DFS for cycle, return if tree.
• Time Complexity: O(n²)—n edges, O(n) DFS each.
• Space Complexity: O(n)—adjacency list and visited set.

It’s a path untangler—trace and cut!

Comparing the Two Solutions

• Union-Find (Best):
• Pros: O(n * α(n)) time, O(n) space, near-linear.
• Cons: Union-Find less intuitive.
• DFS (Alternative):
• Pros: O(n²) time, O(n) space, clear cycle detection.
• Cons: Slower, more complex logic.

Union-Find wins for efficiency.

Additional Examples and Edge Cases

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

Union-Find handles these well.

Complexity Breakdown

• Union-Find: Time O(n * α(n)), Space O(n).
• DFS: Time O(n²), Space O(n).

Union-Find is optimal.

Key Takeaways

• Union-Find: Set merging—smart!
• DFS: Cycle tracing—clear!
• Graphs: Untangling is fun.
• Python Tip: Union-Find rocks—see Python Basics.

Final Thoughts: Untangle That Network

LeetCode 684: Redundant Connection in Python is a fun graph challenge. Union-Find with path compression offers speed and elegance, while DFS provides a clear alternative. Want more? Try LeetCode 547: Number of Provinces or LeetCode 261: Graph Valid Tree. Ready to trace? Head to Solve LeetCode 684 on LeetCode and cut that redundant edge today!