Redundant Connection II - Solution & Explanation
Problem Statement
In this problem, a rooted tree is a directed graph such that, there is exactly one node (the root) for which all other nodes are descendants of this node, plus every node has exactly one parent, except for the root node which has no parents.
The given input is a directed graph that started as a rooted tree with n nodes (with distinct values from 1 to n), with one additional directed edge added. The added edge has two different vertices chosen from 1 to n, and was not an edge that already existed.
The resulting graph is given as a 2D-array of edges. Each element of edges is a pair [ui, vi] that represents a directed edge connecting nodes ui and vi, where ui is a parent of child vi.
Return an edge that can be removed so that the resulting graph is a rooted tree of n nodes. If there are multiple answers, return the answer that occurs last in the given 2D-array.
Example 1:
Input: edges = [[1,2],[1,3],[2,3]] Output: [2,3]
Example 2:
Input: edges = [[1,2],[2,3],[3,4],[4,1],[1,5]] Output: [4,1]
Constraints:
n == edges.length3 <= n <= 1000edges[i].length == 21 <= ui, vi <= nui != vi
Approach Overview
Problem Overview: You are given a directed graph that was originally a rooted tree with n nodes, but one extra edge was added. That extra edge creates either a node with two parents, a cycle, or both. The task is to identify and return the redundant edge that should be removed so the graph becomes a valid rooted tree again.
Approach 1: Union-Find with Parent Check (O(n) time, O(n) space)
This approach combines Union Find with an explicit parent tracking step. While iterating through edges, you first check if a node already has a parent. If it does, you record two candidate edges: the earlier parent edge and the later conflicting one. After that, run union-find to detect cycles while skipping the second candidate edge temporarily. If a cycle still forms, the earlier edge is the redundant one; otherwise the later edge is the answer. Union-Find operations like find and union with path compression keep the total complexity near linear, roughly O(n α(n)). This method directly handles the two tricky scenarios: nodes with two parents and pure cycles.
Approach 2: Graph Traversal & Cycle Detection (O(n) time, O(n) space)
This method treats the graph as a directed structure and uses traversal techniques from Depth-First Search or Breadth-First Search. First, track incoming edges to detect if any node receives two parents. If such a node exists, temporarily remove one candidate edge and run cycle detection using DFS. The traversal checks whether a back-edge appears, which indicates a cycle in the graph. If removing the later edge resolves the cycle, it is redundant; otherwise the earlier edge must be removed. This approach mirrors how you would manually validate a directed tree: ensure every node except the root has exactly one parent and verify there are no cycles.
Recommended for interviews: The Union-Find with parent check approach is the expected solution. It cleanly handles both constraints of the problem—detecting a node with two parents and identifying cycles—while keeping the complexity near linear. Explaining the three possible cases (two parents, cycle, or both) shows strong graph reasoning. A traversal-based solution demonstrates understanding of cycle detection, but Union-Find typically leads to simpler and more reliable implementation under interview pressure.
Approach 1: Union-Find with Parent Check
This approach uses a Union-Find (Disjoint Set Union, DSU) structure to detect cycles and check for nodes with two parents. The goal is to handle two situations: a node having two parents, and a cycle existing in the graph. We iterate through the edges to identify a node with two parents and mark the offending edge. Then, we use the Union-Find structure to track cycles and find the redundant connection based on the identified edges.
The implementation uses a Union-Find data structure to manage connectivity among nodes and track potential redundant connections by checking parent-child relationships and detecting cycles. First, it checks whether any node has two parents. If found, it temporarily removes that edge and continues to apply Union-Find to check for any cycles. If a cycle exists without finding a node with two parents, the wrong edge is part of the cycle. Otherwise, it'll be the edge removed previously.
Complexity
Time Complexity: O(n), where n is the number of edges.
Space Complexity: O(n), for storing the parent and rank arrays.
Approach 2: Graph Traversal & Cycle Detection
In this method, we focus on identifying two scenarios: an edge creating a cycle in the graph and a node with two parents. With graph traversal, primarily cross-check with parent pointers and DFS for cycle confirmation, fine-tuning insights to pinpoint a last array occurrence redundant connection.
Utilizing DFS, this C code ensures settings target node connections and traces for potential overlapping cycles, using indications to determine redundancy. Understanding traversal in view of directed graph properties is fundamental to isolating missteps.
Complexity
Time Complexity: O(n^2) with recursive verification.
Space Complexity: O(n), memoizing visited nodes.
Approach 3: Union-Find
According to the problem description, for a rooted tree, the in-degree of the root node is 0, and the in-degree of other nodes is 1. After adding an edge to the tree, there can be the following three scenarios:
-
The added edge points to a non-root node, and the in-degree of that node becomes
2. In this case, there is no directed cycle in the graph:plaintext 1 / \ v v 2-->3 -
The added edge points to a non-root node, and the in-degree of that node becomes
2. In this case, there is a directed cycle in the graph:plaintext 1 | v 2 <--> 3 -
The added edge points to the root node, and the in-degree of the root node becomes
1. In this case, there is a directed cycle in the graph, but there are no nodes with an in-degree of2.plaintext 1 /^ v \ 2-->3
Therefore, we first calculate the in-degree of each node. If there exists a node with an in-degree of 2, we identify the two edges corresponding to that node, denoted as dup[0] and dup[1]. If deleting dup[1] results in the remaining edges not forming a tree, then dup[0] is the edge that needs to be deleted; otherwise, dup[1] is the edge that needs to be deleted.
If there are no nodes with an in-degree of 2, we traverse the array edges. For each edge (u, v), we use the union-find data structure to maintain connectivity between nodes. If u and v are already connected, it indicates that there is a directed cycle in the graph, and the current edge is the one that needs to be deleted.
The time complexity is O(n log n), and the space complexity is O(n), where n is the number of edges.
Code
Python
Java
C++
Go
TypeScript
JavaScript
Approach 4: Union-Find (Template Approach)
Here is a template approach using Union-Find for your reference.
The time complexity is O(n \alpha(n)), and the space complexity is O(n). Here, n is the number of edges, and \alpha(n) is the inverse Ackermann function, which can be considered a very small constant.
Code
Python
Java
C++
Go
TypeScript
JavaScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Union-Find with Parent Check | Time Complexity: O(n), where n is the number of edges. Space Complexity: O(n), for storing the parent and rank arrays. |
| Graph Traversal & Cycle Detection | Time Complexity: O(n^2) with recursive verification. Space Complexity: O(n), memoizing visited nodes. |
| Union-Find | — |
| Union-Find (Template Approach) | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Union-Find with Parent Check | O(n α(n)) ~ O(n) | O(n) | Best general solution. Handles both two-parent conflict and cycle detection efficiently. |
| Graph Traversal & Cycle Detection | O(n) | O(n) | Useful when reasoning about directed graphs using DFS/BFS or when Union-Find is not preferred. |
Video Solution
Huahua LeetCode 685. Redundant Connection II - Job Hunting EP83 • Hua Hua • 11,116 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Redundant Connection II easy or hard?
Redundant Connection II Python/Java solution
How to solve Redundant Connection II in O(n)?
What is the best approach for Redundant Connection II?
Is Redundant Connection II asked at Google/Amazon/Meta?
What data structure is used in Redundant Connection II?
What is the time complexity of Redundant Connection II?
Ready to solve this problem?
Practice Redundant Connection II with our built-in code editor and test cases.
Practice on FleetCode