[Medium] 684. Redundant Connection

Problem Statement

In this problem, a tree is an undirected graph that is connected and has no cycles.

You are given a graph that started as a tree with n nodes labeled from 1 to n, with one additional edge added. The added edge has two different vertices chosen from 1 to n, and was not an edge that already existed. The graph is represented as an array edges of length n where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the graph.

Return an edge that can be removed so that the resulting graph is a tree of n nodes. If there are multiple answers, return the answer that occurs last in the input.

Examples

Example 1:

Input: edges = [[1,2],[1,3],[2,3]]
Output: [2,3]
Explanation: The edge [2,3] creates a cycle, so it should be removed.

Example 2:

Input: edges = [[1,2],[2,3],[3,4],[1,4],[1,5]]
Output: [1,4]
Explanation: The edge [1,4] creates a cycle, so it should be removed.

Constraints

n == edges.length
3 <= n <= 1000
edges[i].length == 2
1 <= ai < bi <= edges.length
ai != bi
There are no repeated edges.
The given graph is connected.

Clarification Questions

Before diving into the solution, here are 5 important clarifications and assumptions to discuss during an interview:

Redundant edge definition: What makes an edge redundant? (Assumption: An edge that creates a cycle in an otherwise tree structure - the edge that forms the cycle)
Graph type: Is the graph directed or undirected? (Assumption: Undirected - edges have no direction)
Tree property: What is the base structure? (Assumption: Graph with n nodes and n edges - one extra edge makes it not a tree)
Return format: What should we return if multiple redundant edges exist? (Assumption: Return the last edge in the input array that creates a cycle)
Edge representation: How are edges represented? (Assumption: [ai, bi] where ai and bi are node labels, 1-indexed per constraints)

Interview Deduction Process (20 minutes)

Step 1: Brute-Force Approach (5 minutes)

Initial Thought: “I need to find redundant edge. Let me check each edge to see if removing it breaks connectivity.”

Naive Solution: For each edge, remove it and check if graph remains connected. If removing edge breaks connectivity, it’s not redundant.

Complexity: O(n²) time, O(n) space

Issues:

O(n²) time - inefficient
Repeats connectivity checks
Doesn’t leverage Union-Find
Can be optimized

Step 2: Semi-Optimized Approach (7 minutes)

Insight: “I can use Union-Find. The first edge that connects already-connected components is redundant.”

Improved Solution: Use Union-Find. Process edges in order. If edge connects already-connected components, it’s redundant. Return first such edge.

Complexity: O(n × α(n)) time, O(n) space

Improvements:

Union-Find efficiently checks connectivity
O(n × α(n)) is nearly linear
Handles all cases correctly
Much more efficient

Step 3: Optimized Solution (8 minutes)

Final Optimization: “Union-Find approach is optimal. Can also use DFS for cycle detection.”

Best Solution: Union-Find is optimal. Process edges, when find(u) == find(v), edge is redundant. Alternative: DFS to find cycle, return last edge in cycle.

Complexity: O(n × α(n)) time, O(n) space

Key Realizations:

Union-Find is perfect for connectivity problems
O(n × α(n)) is nearly linear - very efficient
First edge connecting connected components is redundant
DFS alternative exists but Union-Find is cleaner

Solution Approach

This problem requires finding the edge that creates a cycle in an undirected graph. Since the graph started as a tree (connected, no cycles) and one edge was added, there is exactly one cycle. We need to find and return the redundant edge.

Key Insights:

Cycle Detection: The redundant edge is the one that connects two nodes already in the same connected component
Union-Find (DSU): Efficiently detect cycles by checking if two nodes are already connected before adding an edge
DFS Approach: Build graph and use DFS to detect cycles, then find the last edge in the cycle
Last Edge Priority: If multiple edges form cycles, return the one that appears last in the input

Algorithm Options:

DSU Approach: Process edges in order, return first edge that connects already-connected nodes
DFS Approach: Build graph, find cycle, return last edge in cycle that appears in input

Solution 1: Union-Find (DSU) - Recommended

Solution: DSU with Union by Rank

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return False

        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        elif self.rank[x] > self.rank[y]:
            self.parent[y] = x
        else:
            self.parent[y] = x
            self.rank[x] += 1

        return True


class Solution:
    def findRedundantConnection(self, edges):
        n = len(edges)
        dsu = DSU(n + 1)

        for u, v in edges:
            if not dsu.unite(u - 1, v - 1):
                return [u, v]

        return []

Algorithm Explanation:

DSU Initialization (Lines 8-15):
- parent[i] = i: Each node is its own parent initially
- rank[i] = 0: All trees start with rank 0
Find with Path Compression (Lines 17-22):
- Recursively find root parent
- Path compression: parent[x] = find(parent[x]) flattens tree
- Returns root of the set containing x
Union by Rank (Lines 24-38):
- Find roots of both nodes
- If same root: already connected → return false (cycle detected!)
- If different roots: merge sets using union by rank
- Attach smaller tree to larger tree to keep balanced
Main Solution (Lines 41-51):
- Process edges in order
- Convert 1-based to 0-based indexing: edge[0] - 1, edge[1] - 1
- If unite returns false: nodes already connected → cycle found!
- Return the redundant edge immediately

Example Walkthrough:

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

Initial: parent = [0,1,2], rank = [0,0,0]

Edge [1,2]: unite(0, 1)
- find(0) = 0, find(1) = 1 (different roots)
- rank[0] == rank[1] → parent[1] = 0, rank[0]++
- parent = [0,0,2], rank = [1,0,0]
- Return true (no cycle)

Edge [1,3]: unite(0, 2)
- find(0) = 0, find(2) = 2 (different roots)
- rank[0] > rank[2] → parent[2] = 0
- parent = [0,0,0], rank = [1,0,0]
- Return true (no cycle)

Edge [2,3]: unite(1, 2)
- find(1) = 0, find(2) = 0 (same root!)
- Return false → CYCLE DETECTED!
- Return [2,3]

Solution 2: DFS Cycle Detection

Solution: DFS to Find Cycle

class Solution:
    def __init__(self):
        self.cycleStart = -1

    def dfs(self, src, visited, adjList, parent):
        visited[src] = True

        for adj in adjList[src]:
            if not visited[adj]:
                parent[adj] = src
                self.dfs(adj, visited, adjList, parent)

            elif adj != parent[src] and self.cycleStart == -1:
                self.cycleStart = adj
                parent[adj] = src

    def findRedundantConnection(self, edges):
        n = len(edges)

        visited = [False] * n
        parent = [-1] * n
        adjList = [[] for _ in range(n)]

        for u, v in edges:
            u -= 1
            v -= 1
            adjList[u].append(v)
            adjList[v].append(u)

        self.dfs(0, visited, adjList, parent)

        cycleNode = set()

        node = self.cycleStart
        while node != -1 and node not in cycleNode:
            cycleNode.add(node)
            node = parent[node]

        # find last edge inside cycle
        for i in range(len(edges) - 1, -1, -1):
            u = edges[i][0] - 1
            v = edges[i][1] - 1
            if u in cycleNode and v in cycleNode:
                return edges[i]

        return []

Algorithm Explanation:

Graph Construction (Lines 25-32):
- Build adjacency list from edges
- Convert 1-based to 0-based indexing
- Store bidirectional edges
DFS Cycle Detection (Lines 4-16):
- Perform DFS from node 0
- Track parent for each node
- If visiting an already-visited node that’s not the parent: cycle found!
- Mark cycleStart when cycle detected
Cycle Extraction (Lines 33-38):
- Start from cycleStart
- Follow parent pointers to extract all nodes in cycle
- Store cycle nodes in cycleNode map
Find Last Edge in Cycle (Lines 39-44):
- Iterate edges from end to beginning
- Find first edge where both endpoints are in cycle
- Return that edge (last in input order)

Example Walkthrough:

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

Graph:
1 -- 2
|    |
3 ---|

DFS from node 0:
- Visit 0 (node 1), parent[0] = -1
- Visit 1 (node 2), parent[1] = 0
- Visit 2 (node 3), parent[2] = 1
- From 2, try to visit 0 (node 1)
  - 0 is visited and 0 != parent[2] (1) → CYCLE!
  - cycleStart = 0

Extract cycle:
- Start from 0: cycleNode[0] = 1
- parent[0] = -1? No, wait... parent[0] was set to 2 in cycle detection
- Follow: 0 → 2 → 1 → 0
- cycleNode = {0, 1, 2}

Find last edge in cycle:
- Check edges from end: [2,3] → nodes 1,2 both in cycle → Return [2,3]

DSU Template

Here’s the general template for Union-Find (DSU) with union by rank:

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    # Find with path compression
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    # Union by rank
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return False  # Already in same set

        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        elif self.rank[x] > self.rank[y]:
            self.parent[y] = x
        else:
            self.parent[y] = x
            self.rank[x] += 1

        return True

    # Check if two nodes are connected
    def connected(self, x, y):
        return self.find(x) == self.find(y)

Key Template Components:

Data Structures:
- parent[i]: Parent of node i (root if parent[i] == i)
- rank[i]: Approximate depth of tree rooted at i
Path Compression:
- Flattens tree during find operation
- Makes future finds faster
Union by Rank:
- Keeps trees balanced
- Attaches smaller tree to larger tree
- Only increases rank when ranks are equal
Time Complexity:
- Nearly O(1) per operation (inverse Ackermann function)
- O(α(n)) where α grows extremely slowly

Complexity Analysis

Solution 1: DSU

Time Complexity: O(n × α(n)) ≈ O(n)

DSU operations: O(α(n)) per operation (nearly constant)
Process n edges: O(n × α(n))
Total: O(n) for practical purposes

Space Complexity: O(n)

Parent array: O(n)
Rank array: O(n)
Total: O(n)

Solution 2: DFS

Time Complexity: O(n)

Graph construction: O(n)
DFS traversal: O(n) - visit each node once
Cycle extraction: O(n) - worst case
Edge search: O(n) - check all edges
Total: O(n)

Space Complexity: O(n)

Adjacency list: O(n)
Visited array: O(n)
Parent array: O(n)
Cycle node map: O(n)
DFS recursion stack: O(n)
Total: O(n)

Key Points

DSU is Optimal: Union-Find is the most efficient approach for cycle detection
Path Compression: Speeds up find operations significantly
Union by Rank: Keeps trees balanced for better performance
1-based to 0-based: Convert node indices when using DSU
Last Edge Priority: Problem asks for last edge in input that creates cycle
Single Cycle: Graph has exactly one cycle (one extra edge in tree)

Comparison: DSU vs DFS

Aspect	DSU	DFS
Time Complexity	O(n × α(n)) ≈ O(n)	O(n)
Space Complexity	O(n)	O(n)
Implementation	Simpler	More complex
Cycle Detection	Direct (during union)	Requires traversal
Edge Order	Natural (process in order)	Need to track and search
Recommended	✅ Yes	⚠️ Works but more complex

Alternative Approaches

Approach 1: DSU (Current Solution 1)

Time: O(n × α(n)) ≈ O(n)
Space: O(n)
Best for: Cycle detection in undirected graphs

Approach 2: DFS (Current Solution 2)

Time: O(n)
Space: O(n)
Use case: When you need to extract full cycle information

Approach 3: BFS Cycle Detection

Time: O(n)
Space: O(n)
Similar to DFS: Can detect cycles but more complex

685. Redundant Connection II - Directed graph version
547. Number of Provinces - Count connected components
721. Accounts Merge - DSU for merging accounts
1319. Number of Operations to Make Network Connected - DSU for connectivity

Robina Li

[Medium] 684. Redundant Connection

[Medium] 684. Redundant Connection

Problem Statement

Examples

Constraints

Clarification Questions

Interview Deduction Process (20 minutes)

Step 1: Brute-Force Approach (5 minutes)

Step 2: Semi-Optimized Approach (7 minutes)

Step 3: Optimized Solution (8 minutes)

Solution Approach

Key Insights:

Algorithm Options:

Solution 1: Union-Find (DSU) - Recommended

Solution: DSU with Union by Rank

Algorithm Explanation:

Example Walkthrough:

Solution 2: DFS Cycle Detection

Solution: DFS to Find Cycle

Algorithm Explanation:

Example Walkthrough:

DSU Template

Key Template Components:

Complexity Analysis

Solution 1: DSU

Solution 2: DFS

Key Points

Comparison: DSU vs DFS

Alternative Approaches

Approach 1: DSU (Current Solution 1)

Approach 2: DFS (Current Solution 2)

Approach 3: BFS Cycle Detection

Tags

Related Posts

Recent Posts

[Medium] 684. Redundant Connection

Problem Statement

Examples

Constraints

Clarification Questions

Interview Deduction Process (20 minutes)

Step 1: Brute-Force Approach (5 minutes)

Step 2: Semi-Optimized Approach (7 minutes)

Step 3: Optimized Solution (8 minutes)

Solution Approach

Key Insights:

Algorithm Options:

Solution 1: Union-Find (DSU) - Recommended

Solution: DSU with Union by Rank

Algorithm Explanation:

Example Walkthrough:

Solution 2: DFS Cycle Detection

Solution: DFS to Find Cycle

Algorithm Explanation:

Example Walkthrough:

DSU Template

Key Template Components:

Complexity Analysis

Solution 1: DSU

Solution 2: DFS

Key Points

Comparison: DSU vs DFS

Alternative Approaches

Approach 1: DSU (Current Solution 1)

Approach 2: DFS (Current Solution 2)

Approach 3: BFS Cycle Detection

Related Problems

Tags

Related Posts

Recent Posts