Redundant Connection II solution and explanation
Google
9 more videos on this problem
Huahua LeetCode 685. Redundant Connection II - Job Hunting EP83Hua Hua · 12:38 · 11K views
LeetCode 685 - Redundant Connection II - Leetcode Hard problem directed graphInterviewDose · 5:35 · 6K views
LeetCode 685. Redundant Connection II Explanation and Solutionhappygirlzt · 13:14 · 6K views
E02: Redundant Connection II | DSU | LeetCodeCodeNCode · 27:06 · 1K views
LeetCode 685. Redundant Connection II Chinese Versionhappygirlzt · 14:57 · 1K views
685. Redundant Connection II (Leetcode Hard)Programming Live with Larry · 24:27 · 811 views
685. Redundant Connection II | Leetcode Hard | Union Find GraphAmit Choraria · 23:54 · 390 views
LeetCode 685 | Redundant Connection II | OpHaxor SolutionAlgorithms & Programming Interview Prep · 48:11 · 220 views
Redundant Connection II - Leetcode 685 - Union Find - PythonEffective Coder · 23:33 · 203 views
Redundant Connection II | Disjoint Set Union | Graph | LinkedIn Interview Question | LeetCode 685Programming With Niladree - PWN - Bangladesh · 10:13 · 164 views
The problem
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.
class UnionFind:
def __init__(self, size):
self.parent = list(range(size))
self.rank = [1] * size
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
rootX = self.find(x)
rootY = self.find(y)
if rootX != rootY:
if self.rank[rootX] > self.rank[rootY]:
self.parent[rootY] = rootX
elif self.rank[rootX] < self.rank[rootY]:
self.parent[rootX] = rootY
else:
self.parent[rootY] = rootX
self.rank[rootX] += 1
return True
return False
class Solution:
def findRedundantDirectedConnection(self, edges):
n = len(edges)
parent = list(range(n + 1))
can1 = can2 = None
for u, v in edges:
if parent[v] != v:
can1 = [parent[v], v]
can2 = [u, v]
v = 0
else:
parent[v] = u
uf = UnionFind(n + 1)
for u, v in edges:
if v == 0: continue
if not uf.union(u, v):
return can1 if can1 else [u, v]
return can2class UnionFind {
private int[] parent;
private int[] rank;
public UnionFind(int size) {
parent = new int[size];
rank = new int[size];
for (int i = 0; i < size; i++) {
parent[i] = i;
rank[i] = 1;
}
}
public int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
public boolean union(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX == rootY) return false;
if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else {
parent[rootY] = rootX;
rank[rootX]++;
}
return true;
}
}
public class Solution {
public int[] findRedundantDirectedConnection(int[][] edges) {
int n = edges.length;
int[] parent = new int[n + 1];
for (int i = 1; i <= n; i++) {
parent[i] = i;
}
int[] can1 = null;
int[] can2 = null;
for (int[] edge : edges) {
int u = edge[0], v = edge[1];
if (parent[v] != v) {
can1 = new int[] {parent[v], v};
can2 = new int[] {u, v};
edge[1] = 0;
} else {
parent[v] = u;
}
}
UnionFind uf = new UnionFind(n + 1);
for (int[] edge : edges) {
if (edge[1] == 0) continue;
int u = edge[0], v = edge[1];
if (!uf.union(u, v)) return can1 == null ? edge : can1;
}
return can2;
}
}#include <vector>
using namespace std;
class UnionFind {
public:
UnionFind(int size) : parent(size), rank(size, 1) {
for (int i = 0; i < size; ++i) {
parent[i] = i;
}
}
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
bool unionSets(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX == rootY) return false;
if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else {
parent[rootY] = rootX;
rank[rootX]++;
}
return true;
}
private:
vector<int> parent;
vector<int> rank;
};
vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {
int n = edges.size();
vector<int> parent(n + 1);
for (int i = 1; i <= n; ++i) {
parent[i] = i;
}
vector<int> can1, can2;
for (const auto& edge : edges) {
int u = edge[0], v = edge[1];
if (parent[v] != v) {
can1 = {parent[v], v};
can2 = {u, v};
edge[1] = 0;
} else {
parent[v] = u;
}
}
UnionFind uf(n + 1);
for (const auto& edge : edges) {
if (edge[1] == 0) continue;
int u = edge[0], v = edge[1];
if (!uf.unionSets(u, v)) return can1.empty() ? edge : can1;
}
return can2;
}class UnionFind {
constructor(size) {
this.parent = Array.from({ length: size }, (_, index) => index);
this.rank = Array(size).fill(1);
}
find(x) {
if (this.parent[x] !== x) {
this.parent[x] = this.find(this.parent[x]);
}
return this.parent[x];
}
union(x, y) {
let rootX = this.find(x);
let rootY = this.find(y);
if (rootX === rootY) return false;
if (this.rank[rootX] > this.rank[rootY]) {
this.parent[rootY] = rootX;
} else if (this.rank[rootX] < this.rank[rootY]) {
this.parent[rootX] = rootY;
} else {
this.parent[rootY] = rootX;
this.rank[rootX]++;
}
return true;
}
}
var findRedundantDirectedConnection = function(edges) {
const n = edges.length;
const parent = Array.from({ length: n + 1 }, (_, index) => index);
let can1 = null, can2 = null;
for (const [u, v] of edges) {
if (parent[v] !== v) {
can1 = [parent[v], v];
can2 = [u, v];
v = 0;
} else {
parent[v] = u;
}
}
const uf = new UnionFind(n + 1);
for (const [u, v] of edges) {
if (v === 0) continue;
if (!uf.union(u, v)) return can1 || [u, v];
}
return can2;
};#include <stdio.h>
#include <stdlib.h>
typedef struct UnionFind {
int* parent;
int* rank;
} UnionFind;
UnionFind* createUnionFind(int size) {
UnionFind* uf = (UnionFind*)malloc(sizeof(UnionFind));
uf->parent = (int*)malloc(sizeof(int) * size);
uf->rank = (int*)malloc(sizeof(int) * size);
for (int i = 0; i < size; i++) {
uf->parent[i] = i;
uf->rank[i] = 1;
}
return uf;
}
int find(UnionFind* uf, int x) {
if (uf->parent[x] != x) {
uf->parent[x] = find(uf, uf->parent[x]);
}
return uf->parent[x];
}
void unionSets(UnionFind* uf, int x, int y) {
int rootX = find(uf, x);
int rootY = find(uf, y);
if (rootX != rootY) {
if (uf->rank[rootX] > uf->rank[rootY]) {
uf->parent[rootY] = rootX;
} else if (uf->rank[rootX] < uf->rank[rootY]) {
uf->parent[rootX] = rootY;
} else {
uf->parent[rootY] = rootX;
uf->rank[rootX]++;
}
}
}
int* findRedundantDirectedConnection(int** edges, int edgesSize, int* edgesColSize, int* returnSize) {
int n = edgesSize;
int* parent = (int*)malloc(sizeof(int) * (n + 1));
for (int i = 0; i <= n; i++) {
parent[i] = i;
}
int* can1 = NULL;
int* can2 = NULL;
for (int i = 0; i < n; i++) {
int u = edges[i][0], v = edges[i][1];
if (parent[v] != v) {
can1 = (int*)malloc(sizeof(int) * 2);
can2 = (int*)malloc(sizeof(int) * 2);
can1[0] = parent[v];
can1[1] = v;
can2[0] = u;
can2[1] = v;
edges[i][1] = 0;
} else {
parent[v] = u;
}
}
UnionFind* uf = createUnionFind(n + 1);
for (int i = 0; i < n; i++) {
if (edges[i][1] == 0) continue;
int u = edges[i][0], v = edges[i][1];
if (find(uf, u) == find(uf, v)) {
if (can1) return can1;
int* result = (int*)malloc(sizeof(int) * 2);
result[0] = u;
result[1] = v;
return result;
}
unionSets(uf, u, v);
}
return can2;
}public class UnionFind {
private int[] parent;
private int[] rank;
public UnionFind(int size) {
parent = new int[size];
rank = new int[size];
for (int i = 0; i < size; i++) {
parent[i] = i;
rank[i] = 1;
}
}
public int Find(int x) {
if (parent[x] != x) {
parent[x] = Find(parent[x]);
}
return parent[x];
}
public bool Union(int x, int y) {
int rootX = Find(x);
int rootY = Find(y);
if (rootX == rootY) return false;
if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else {
parent[rootY] = rootX;
rank[rootX]++;
}
return true;
}
}
public class Solution {
public int[] FindRedundantDirectedConnection(int[][] edges) {
int n = edges.Length;
int[] parent = new int[n + 1];
for (int i = 0; i <= n; i++) {
parent[i] = i;
}
int[] can1 = null;
int[] can2 = null;
foreach (var edge in edges) {
int u = edge[0], v = edge[1];
if (parent[v] != v) {
can1 = new int[] { parent[v], v };
can2 = new int[] { u, v };
edge[1] = 0;
} else {
parent[v] = u;
}
}
UnionFind uf = new UnionFind(n + 1);
foreach (var edge in edges) {
if (edge[1] == 0) continue;
int u = edge[0], v = edge[1];
if (!uf.Union(u, v)) return can1 ?? edge;
}
return can2;
}
}The Python code uses the Union-Find construct to handle multiple paths effectively and determines early if redundant connections are present or removal is optimal, readying to designate that action among potentially overlapping connectivity options.
Time Complexity: O(n) given n edges to examine.
Space Complexity: O(n) used in the Union-Find structure.
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.
class Solution:
def findRedundantDirectedConnection(self, edges):
def dfs(parent, visited, cycle, node):
if cycle[0]:
return
visited[node] = True
next = parent[node]
if next != 0:
if not visited[next]:
dfs(parent, visited, cycle, next)
else:
cycle[0] = True
visited[node] = False
n = len(edges)
parent = [0] * (n + 1)
can1, can2 = None, None
for u, v in edges:
if parent[v] != 0:
can1 = (parent[v], v)
can2 = (u, v)
v = 0
else:
parent[v] = u
cycle = [False]
for i in range(1, n + 1):
if cycle[0]:
break
visited = [False] * (n + 1)
dfs(parent, visited, cycle, i)
return can1 if cycle[0] else can2import java.util.*;
public class Solution {
private void dfs(int[] parent, boolean[] visited, boolean[] cycle, int current) {
if (cycle[0]) return;
visited[current] = true;
int next = parent[current];
if (next != 0) {
if (!visited[next]) {
dfs(parent, visited, cycle, next);
} else {
cycle[0] = true;
}
}
visited[current] = false;
}
public int[] findRedundantDirectedConnection(int[][] edges) {
int n = edges.length;
int[] parent = new int[n + 1];
Arrays.fill(parent, 0);
int[] can1 = null, can2 = null;
for (int[] edge : edges) {
int u = edge[0], v = edge[1];
if (parent[v] != 0) {
can1 = new int[] {parent[v], v};
can2 = edge;
edge[1] = 0;
} else {
parent[v] = u;
}
}
boolean[] cycle = {false};
for (int i = 1; i <= n; i++) {
boolean[] visited = new boolean[n + 1];
dfs(parent, visited, cycle, i);
if (cycle[0]) break;
}
return cycle[0] ? can1 : can2;
}
}#include <vector>
using namespace std;
void dfs(vector<int>& parent, vector<bool>& visited, bool& hasCycle, int node) {
if (visited[node]) {
hasCycle = true;
return;
}
visited[node] = true;
int next = parent[node];
if (next != 0) dfs(parent, visited, hasCycle, next);
visited[node] = false;
}
vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {
int n = edges.size();
vector<int> parent(n + 1);
vector<int> can1, can2;
for (auto& edge : edges) {
int u = edge[0], v = edge[1];
if (parent[v] != 0) {
can1 = {parent[v], v};
can2 = edge;
edge[1] = 0;
} else {
parent[v] = u;
}
}
bool hasCycle = false;
for (int i = 1; i <= n; i++) {
vector<bool> visited(n + 1);
dfs(parent, visited, hasCycle, i);
if (hasCycle) break;
}
if (hasCycle) return can1;
return can2;
}var findRedundantDirectedConnection = function(edges) {
function dfs(parent, visited, cycle, node) {
if (cycle[0]) return;
visited[node] = true;
let next = parent[node];
if (next !== 0) {
if (!visited[next]) {
dfs(parent, visited, cycle, next);
} else {
cycle[0] = true;
}
}
visited[node] = false;
}
const n = edges.length;
const parent = new Array(n + 1).fill(0);
let can1 = null, can2 = null;
for (const [u, v] of edges) {
if (parent[v] !== 0) {
can1 = [parent[v], v];
can2 = [u, v];
continue;
}
parent[v] = u;
}
let cycle = [false];
for (let i = 1; i <= n; i++) {
if (cycle[0]) break;
let visited = new Array(n + 1).fill(false);
dfs(parent, visited, cycle, i);
}
return cycle[0] ? can1 : can2;
};#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
void dfs(int* parent, bool* visited, bool* cycle, int current) {
visited[current] = true;
int next = parent[current];
if (next != 0) {
if (!visited[next]) {
dfs(parent, visited, cycle, next);
} else {
*cycle = true;
}
}
}
int* findRedundantDirectedConnection(int** edges, int edgesSize, int* edgesColSize, int* returnSize) {
int n = edgesSize;
int* parent = (int*)calloc(n + 1, sizeof(int));
for (int i = 0; i < n; ++i) {
int u = edges[i][0], v = edges[i][1];
if (parent[v] != 0) {
int* can1 = (int*)malloc(sizeof(int) * 2);
int* can2 = (int*)malloc(sizeof(int) * 2);
can1[0] = parent[v];
can1[1] = v;
can2[0] = u;
can2[1] = v;
parent[v] = 0;
bool cycle = false;
for (int j = 0; j <= n; j++) {
if (parent[j] == 0) continue;
bool* visited = (bool*)calloc(n + 1, sizeof(bool));
dfs(parent, visited, &cycle, j);
free(visited);
if (cycle) break;
}
if (cycle) return can1;
else return can2;
}
parent[v] = u;
}
bool cycle = false;
for (int j = 0; j <= n; j++) {
if (parent[j] == 0) continue;
bool* visited = (bool*)calloc(n + 1, sizeof(bool));
dfs(parent, visited, &cycle, j);
free(visited);
if (cycle) {
int u = parent[j], v = j;
int* result = (int*)malloc(sizeof(int) * 2);
result[0] = u;
result[1] = v;
return result;
}
}
return NULL;
}public class Solution {
private void Dfs(int[] parent, bool[] visited, ref bool hasCycle, int node) {
if (hasCycle) return;
visited[node] = true;
if (parent[node] != 0) {
int next = parent[node];
if (!visited[next]) {
Dfs(parent, visited, ref hasCycle, next);
} else {
hasCycle = true;
}
}
visited[node] = false;
}
public int[] FindRedundantDirectedConnection(int[][] edges) {
int n = edges.Length;
int[] parent = new int[n + 1];
Array.Fill(parent, 0);
int[] can1 = null, can2 = null;
foreach (var edge in edges) {
int u = edge[0], v = edge[1];
if (parent[v] != 0) {
can1 = new int[] { parent[v], v };
can2 = new int[] { u, v };
edge[1] = 0;
} else {
parent[v] = u;
}
}
bool hasCycle = false;
for (int i = 1; i <= n; i++) {
if (hasCycle) break;
var visited = new bool[n + 1];
Dfs(parent, visited, ref hasCycle, i);
}
return hasCycle ? can1 : can2;
}
}The Python script leverages DFS walkthrough simplification to evaluate node links and rank suitable output arrays. Using inner loops partnered with recursive cycle validation, it correctly adjudicates offending connections.
Time Complexity: O(n^2) involving full edge exploration for cycles.
Space Complexity: O(n), scales with DFS state handling across graph 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.
function findRedundantDirectedConnection(edges: number[][]): number[] {
const n = edges.length;
const ind: number[] = Array(n).fill(0);
for (const [_, v] of edges) {
++ind[v - 1];
}
const dup: number[] = [];
for (let i = 0; i < n; ++i) {
if (ind[edges[i][1] - 1] === 2) {
dup.push(i);
}
}
const p: number[] = Array.from({ length: n }, (_, i) => i);
const find = (x: number): number => {
if (p[x] !== x) {
p[x] = find(p[x]);
}
return p[x];
};
if (dup.length) {
for (let i = 0; i < n; ++i) {
if (i === dup[1]) {
continue;
}
const [pu, pv] = [find(edges[i][0] - 1), find(edges[i][1] - 1)];
if (pu === pv) {
return edges[dup[0]];
}
p[pu] = pv;
}
return edges[dup[1]];
}
for (let i = 0; ; ++i) {
const [pu, pv] = [find(edges[i][0] - 1), find(edges[i][1] - 1)];
if (pu === pv) {
return edges[i];
}
p[pu] = pv;
}
}func findRedundantDirectedConnection(edges [][]int) []int {
n := len(edges)
ind := make([]int, n)
for _, e := range edges {
ind[e[1]-1]++
}
dup := []int{}
for i, e := range edges {
if ind[e[1]-1] == 2 {
dup = append(dup, i)
}
}
p := make([]int, n)
for i := range p {
p[i] = i
}
var find func(int) int
find = func(x int) int {
if p[x] != x {
p[x] = find(p[x])
}
return p[x]
}
if len(dup) > 0 {
for i, e := range edges {
if i == dup[1] {
continue
}
pu, pv := find(e[0]-1), find(e[1]-1)
if pu == pv {
return edges[dup[0]]
}
p[pu] = pv
}
return edges[dup[1]]
}
for _, e := range edges {
pu, pv := find(e[0]-1), find(e[1]-1)
if pu == pv {
return e
}
p[pu] = pv
}
return nil
}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.
class UnionFind {
p: number[];
size: number[];
constructor(n: number) {
this.p = Array.from({ length: n }, (_, i) => i);
this.size = Array(n).fill(1);
}
find(x: number): number {
if (this.p[x] !== x) {
this.p[x] = this.find(this.p[x]);
}
return this.p[x];
}
union(a: number, b: number): boolean {
const [pa, pb] = [this.find(a), this.find(b)];
if (pa === pb) {
return false;
}
if (this.size[pa] > this.size[pb]) {
this.p[pb] = pa;
this.size[pa] += this.size[pb];
} else {
this.p[pa] = pb;
this.size[pb] += this.size[pa];
}
return true;
}
}
function findRedundantDirectedConnection(edges: number[][]): number[] {
const n = edges.length;
const ind: number[] = Array(n).fill(0);
for (const [_, v] of edges) {
++ind[v - 1];
}
const dup: number[] = [];
for (let i = 0; i < n; ++i) {
if (ind[edges[i][1] - 1] === 2) {
dup.push(i);
}
}
const uf = new UnionFind(n);
if (dup.length) {
for (let i = 0; i < n; ++i) {
if (i === dup[1]) {
continue;
}
if (!uf.union(edges[i][0] - 1, edges[i][1] - 1)) {
return edges[dup[0]];
}
}
return edges[dup[1]];
}
for (let i = 0; ; ++i) {
if (!uf.union(edges[i][0] - 1, edges[i][1] - 1)) {
return edges[i];
}
}
}type unionFind struct {
p, size []int
}
func newUnionFind(n int) *unionFind {
p := make([]int, n)
size := make([]int, n)
for i := range p {
p[i] = i
size[i] = 1
}
return &unionFind{p, size}
}
func (uf *unionFind) find(x int) int {
if uf.p[x] != x {
uf.p[x] = uf.find(uf.p[x])
}
return uf.p[x]
}
func (uf *unionFind) union(a, b int) bool {
pa, pb := uf.find(a), uf.find(b)
if pa == pb {
return false
}
if uf.size[pa] > uf.size[pb] {
uf.p[pb] = pa
uf.size[pa] += uf.size[pb]
} else {
uf.p[pa] = pb
uf.size[pb] += uf.size[pa]
}
return true
}
func findRedundantDirectedConnection(edges [][]int) []int {
n := len(edges)
ind := make([]int, n)
for _, e := range edges {
ind[e[1]-1]++
}
dup := []int{}
for i, e := range edges {
if ind[e[1]-1] == 2 {
dup = append(dup, i)
}
}
uf := newUnionFind(n)
if len(dup) > 0 {
for i, e := range edges {
if i == dup[1] {
continue
}
if !uf.union(e[0]-1, e[1]-1) {
return edges[dup[0]]
}
}
return edges[dup[1]]
}
for _, e := range edges {
if !uf.union(e[0]-1, e[1]-1) {
return e
}
}
return nil
}Complexity comparison
| Approach | Complexity |
|---|---|
| Union-Find with Parent Check | Time Complexity: O(n) given n edges to examine. Space Complexity: O(n) used in the Union-Find structure. |
| Graph Traversal & Cycle Detection | Time Complexity: O(n^2) involving full edge exploration for cycles. Space Complexity: O(n), scales with DFS state handling across graph nodes. |
| Union-Find | – |
| Union-Find (Template Approach) | – |
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. |
Frequently asked questions
Is Redundant Connection II easy or hard?
Redundant Connection II is categorized as a Hard problem on LeetCode. The difficulty comes from handling two separate constraints simultaneously: detecting a node with two parents and detecting a cycle in a directed graph.
Redundant Connection II Python/Java solution
Most implementations use Union-Find with path compression in Python, Java, C++, or JavaScript. The algorithm scans edges once to detect a node with two parents and then performs union operations to check for cycles, keeping the runtime close to O(n).
How to solve Redundant Connection II in O(n)?
Track whether any node receives two parents while iterating through edges. Store the two candidate edges if this happens. Then run union-find across the edges to detect a cycle, skipping the later conflicting edge initially. Depending on whether a cycle still appears, return the appropriate candidate edge.
What is the best approach for Redundant Connection II?
Union-Find with a parent check is the most effective approach. It first detects if a node has two parents and then uses union-find to determine whether removing the conflicting edge resolves a cycle. With path compression and union by rank, the runtime is nearly linear at O(n α(n)).
Is Redundant Connection II asked at Google/Amazon/Meta?
Redundant Connection II represents the type of advanced graph problem asked at companies like Google, Amazon, and Meta. It tests knowledge of Union-Find, directed graph properties, and edge case reasoning involving cycles and multiple parents.
What data structure is used in Redundant Connection II?
The main data structure is Union-Find (Disjoint Set Union) combined with a parent array to track incoming edges. Graph traversal techniques like DFS can also be used to detect cycles in the directed graph variant of the problem.
What is the time complexity of Redundant Connection II?
The optimal solution runs in O(n α(n)) time using Union-Find, which is effectively linear for practical input sizes. Each edge performs a small number of find and union operations. Space complexity is O(n) for parent and rank arrays.