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:
list[int> parent
list[int> rank
DSU(n) :
parent.resize(n)
rank.resize(n, 0)
for(i = 0 i < n i += 1) :
parent[i] = i
def find(self, x):
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]
def unite(self, x, y):
    x = find(x)
    y = find(y)
    if(x == y) return False
    if rank[x] < rank[y]:
        parent[x] = y
         else if(rank[x] > rank[y]) :
        parent[y] = x
         else :
        parent[y] = x
        rank[x]++
    return True
class Solution:
def findRedundantConnection(self, edges):
    n = len(edges)
    DSU dsu(n)
    for edge in edges:
        if not dsu.unite(edge[0] - 1, edge[1] - 1):
            return edge
    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:
cycleStart = -1
def dfs(self, src, visited, list[list[pair<int, adjList, parent):
    visited[src] = True
    for p in adjList[src]:
        adj = p.first
        if not visited[adj]:
            parent[adj] = src
            dfs(adj, visited, adjList, parent)
             else if(adj != parent[src] * and  cycleStart == -1) :
            cycleStart = adj
            parent[adj] = src
def findRedundantConnection(self, edges):
    n = len(edges)
    list[bool> visited(n, False)
    list[int> parent(n, -1)
    list[list[pair<int, int>>> adjList(n)
    for edge in edges:
        u = edge[0] - 1
        v = edge[1] - 1
        adjList[u].append(:v, 0)
        adjList[v].append(:u, 0)
    dfs(0, visited, adjList, parent)
    dict[int, int> cycleNode
    node = cycleStart
    do :
    cycleNode[node] = 1
    node = parent[node]
     while node != cycleStart:
    for(i = len(edges) - 1 i >= 0 i -= 1) :
    if(cycleNode[edges[i][0] - 1] * and
    cycleNode[edges[i][1] - 1]) :
    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:
list[int> parent
list[int> rank
DSU(n) :
parent.resize(n)
rank.resize(n, 0)
for(i = 0 i < n i += 1) :
parent[i] = i
# Find with path compression
def find(self, x):
    if parent[x] != x:
        parent[x] = find(parent[x]) # Path compression
    return parent[x]
# Union by rank
def unite(self, x, y):
    x = find(x)
    y = find(y)
    if(x == y) return False # Already in same set
    # Union by rank: attach smaller tree to larger tree
    if rank[x] < rank[y]:
        parent[x] = y
         else if(rank[x] > rank[y]) :
        parent[y] = x
         else :
        parent[y] = x
        rank[x]++
    return True
# Check if two nodes are connected
def connected(self, x, y):
    return find(x) == 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

684. Redundant Connection

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

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