Redundant Connection II — Solution in Python, Java & C++
Redundant Connection II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Redundant Connection II is a hard coding problem on depth-first search, graph and union find, asked in Amazon, Google and Uber interviews.
- Difficulty: Hard
- Topics: Depth-First Search, Graph, Union Find
- Asked at: Amazon, Google, Uber
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A rooted tree is a directed graph with one root node that every other node descends from; every node except the root has exactly one parent, and the root has none.
The CodeKairo mentorship chart started as a rooted tree on n people labelled 1 to n, with each edge [u, v] meaning u mentors v. Then one extra directed edge was added between two different people; it was not already in the chart. You receive the resulting n edges as edges.
Return an edge whose removal turns the graph back into a rooted tree on all n nodes. If several edges qualify, return the one that appears last in edges.
Example 1
Input: edges = [[1,2],[1,3],[3,2]]
Output: [3,2]
Explanation: Node 2 has two parents; dropping the later edge `[3,2]` leaves the tree rooted at 1.
Example 2
Input: edges = [[2,3],[3,1],[1,4],[4,2]]
Output: [4,2]
Explanation: No node has two parents, but the four edges form a cycle. Removing any cycle edge works; `[4,2]` is the last one listed.
Example 3
Input: edges = [[3,1],[1,2],[2,3],[4,2]]
Output: [1,2]
Explanation: Node 2 has parents 1 and 4, and 3 → 1 → 2 → 3 is a cycle. Only removing `[1,2]` leaves a tree (rooted at 4).
Constraints
n == edges.length3 <= n <= 1000edges[i].length == 21 <= ui, vi <= nui != vithe input is a rooted tree plus one extra edge
Hints for Redundant Connection II
Hint 1
Adding one directed edge to a rooted tree can break it in two ways: some node gets a second parent, or a cycle appears — or both at once.
Hint 2
If a node has two parents, the answer is one of its two incoming edges. Which one? Try leaving the later one out and see whether a cycle remains.
Hint 3
Union-find over the edges (skipping the second incoming edge, if any) detects the cycle. A cycle left over means the first incoming edge was the culprit; no cycle means the second one was; no double parent means the edge that closes the cycle.
How to solve Redundant Connection II
The extra edge either gives some node a second parent, closes a cycle, or does both. Spotting the double parent first narrows the answer to two candidates, and a union-find pass decides between them.
Approach
- Scan the edges, recording each node's first parent. If an edge
[u, v]arrives for avthat already has a parent, remember the earlier edge ascand1and this edge ascand2. - Run union-find over the edges in order, skipping
cand2if it exists. - If some edge
[u, v]joins two nodes already in the same set, a cycle exists: returncand1if there was a double parent, otherwise return[u, v]. - If the pass finishes without a cycle, return
cand2.
Why it works
With a double parent, exactly one of the two incoming edges must go. Skipping cand2: if the remaining graph still has a cycle, cand2 cannot be the fix, so cand1 (which lies on that cycle) is; if no cycle remains, removing cand2 already yields a tree, and since cand2 comes later it is the required answer. Without a double parent, the extra edge points at the root and closes a cycle; removing any cycle edge leaves a tree, and union-find reports exactly the cycle edge that appears last in the list, because the earlier cycle edges only form a path.
Complexity
- Time —
O(n · α(n)) - Space —
O(n)
Pitfalls
- Union-find alone fails when a node has two parents but the cycle is closed by a different edge — the double-parent check must come first.
- When both candidates would produce a tree, the later one (
cand2) must be returned. - Union by undirected connectivity is enough for cycle detection here; no direction-aware traversal is needed.
Reference solution
Python
from typing import List
def findRedundantDirectedConnection(edges: List[List[int]]) -> List[int]:
n = len(edges)
parent = [0] * (n + 1)
cand1 = None
cand2 = None
for u, v in edges:
if parent[v] != 0:
cand1 = [parent[v], v]
cand2 = [u, v]
else:
parent[v] = u
root = list(range(n + 1))
def find(x):
while root[x] != x:
root[x] = root[root[x]]
x = root[x]
return x
for u, v in edges:
if cand2 is not None and u == cand2[0] and v == cand2[1]:
continue
ru, rv = find(u), find(v)
if ru == rv:
return cand1 if cand1 is not None else [u, v]
root[rv] = ru
return cand2Java
public static int[] findRedundantDirectedConnection(int[][] edges) {
int n = edges.length;
int[] parent = new int[n + 1];
int[] root = new int[n + 1];
for (int k = 0; k <= n; k++) root[k] = k;
int[] cand1 = null, cand2 = null;
for (int[] e : edges) {
if (parent[e[1]] != 0) { cand1 = new int[]{parent[e[1]], e[1]}; cand2 = new int[]{e[0], e[1]}; }
else parent[e[1]] = e[0];
}
for (int[] e : edges) {
if (cand2 != null && e[0] == cand2[0] && e[1] == cand2[1]) continue;
int ra = rcFind(root, e[0]), rb = rcFind(root, e[1]);
if (ra == rb) return cand1 != null ? cand1 : new int[]{e[0], e[1]};
root[rb] = ra;
}
return cand2;
}
static int rcFind(int[] root, int x) {
while (root[x] != x) { root[x] = root[root[x]]; x = root[x]; }
return x;
}C++
static int rcFind(vector<int>& root, int x) {
while (root[x] != x) { root[x] = root[root[x]]; x = root[x]; }
return x;
}
vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {
int n = edges.size();
vector<int> parent(n + 1, 0), root(n + 1);
for (int k = 0; k <= n; k++) root[k] = k;
vector<int> cand1, cand2;
for (auto& e : edges) {
if (parent[e[1]] != 0) { cand1 = {parent[e[1]], e[1]}; cand2 = {e[0], e[1]}; }
else parent[e[1]] = e[0];
}
for (auto& e : edges) {
if (!cand2.empty() && e[0] == cand2[0] && e[1] == cand2[1]) continue;
int ra = rcFind(root, e[0]), rb = rcFind(root, e[1]);
if (ra == rb) return !cand1.empty() ? cand1 : vector<int>{e[0], e[1]};
root[rb] = ra;
}
return cand2;
}JavaScript
var findRedundantDirectedConnection = function(edges) {
var n = edges.length;
var parent = [], root = [];
for (var k = 0; k <= n; k++) { parent.push(0); root.push(k); }
var cand1 = null, cand2 = null;
for (var i = 0; i < n; i++) {
var u = edges[i][0], v = edges[i][1];
if (parent[v] !== 0) { cand1 = [parent[v], v]; cand2 = [u, v]; }
else parent[v] = u;
}
var find = function(x) {
while (root[x] !== x) { root[x] = root[root[x]]; x = root[x]; }
return x;
};
for (var j = 0; j < n; j++) {
var a = edges[j][0], b = edges[j][1];
if (cand2 !== null && a === cand2[0] && b === cand2[1]) continue;
var ra = find(a), rb = find(b);
if (ra === rb) return cand1 !== null ? cand1 : [a, b];
root[rb] = ra;
}
return cand2;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 201 depth-first search problems · the whole catalogue
Learn the technique: Depth-First Search (DFS) · Graph Data Structure