Redundant Connection solution and explanation
Google
9 more videos on this problem
Redundant Connection - Union Find - Leetcode 684 - PythonNeetCode · 16:04 · 133K views
Redundant Connection - Leetcode 684 - PythonNeetCodeIO · 18:34 · 57K views
Redundant Connection | DSU | DFS | BFS | Leetcode 684 | codestorywithMIKcodestorywithMIK · 32:38 · 13K views
Redundant Connection | Live Coding with Explanation | Leetcode - 684Algorithms Made Easy · 15:27 · 9K views
Leetcode 684 - Union Find | Redundant ConnectionNideesh Terapalli · 10:49 · 6K views
Redundant Connection | Leetcode 684Techdose · 14:14 · 6K views
Redundant Connection | graphs | dsu | shashcode | Leetcode Daily Challenge | javaShashCode · 11:37 · 4K views
684. Redundant Connection | Cycle in an Undirected Graph | DSU | Kruskal's IdeaAryan Mittal · 14:39 · 3K views
Redundant Connection | LeetCode 684 Union FindDestination FAANG · 20:07 · 620 views
LeetCode 684 | Redundant Connection DFS | OpHaxor SolutionAlgorithms & Programming Interview Prep · 17:10 · 383 views
The problem
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.
Example 1:
Input: edges = [[1,2],[1,3],[2,3]] Output: [2,3]
Example 2:
Input: edges = [[1,2],[2,3],[3,4],[1,4],[1,5]] Output: [1,4]
Constraints:
n == edges.length3 <= n <= 1000edges[i].length == 21 <= ai < bi <= edges.lengthai != bi- There are no repeated edges.
- The given graph is connected.
Approach overview
Problem Overview: You receive a list of edges representing an undirected graph that started as a tree with n nodes. One additional edge was added, creating exactly one cycle. Your task is to return the edge that introduces the cycle (the redundant connection).
Approach 1: Union-Find Algorithm (O(n α(n)) time, O(n) space)
The most efficient solution uses the Union-Find (Disjoint Set Union) data structure to track connected components. Iterate through each edge (u, v). If u and v already belong to the same set, adding this edge would connect two nodes that are already connected, which forms a cycle. That edge is the redundant one. Otherwise, union their sets using path compression and union by rank to keep operations nearly constant time. This approach processes each edge once and avoids explicitly traversing the graph.
Union-Find works well because a valid tree never connects two nodes already in the same component. The moment that happens, a cycle is detected. With path compression, the amortized complexity becomes almost linear (O(n α(n)), where α is the inverse Ackermann function).
Approach 2: Depth-First Search (DFS) (O(n²) time, O(n) space)
This approach builds the graph incrementally using an adjacency list and checks connectivity before adding each edge. For every new edge (u, v), run a DFS from u to see if v is already reachable. If a path already exists, adding the edge would close a cycle, so that edge is redundant. If not, add the edge to the graph and continue.
The traversal uses Depth-First Search on the evolving graph. Each DFS may visit up to O(n) nodes, and you potentially run it for every edge, which leads to O(n²) time in the worst case. This solution is easier to reason about if you're thinking in terms of connectivity checks rather than disjoint sets.
Recommended for interviews: The Union-Find solution is what most interviewers expect. It demonstrates understanding of cycle detection in undirected graphs and familiarity with disjoint-set optimizations like path compression. The DFS approach shows solid graph fundamentals, but Union-Find is both cleaner and more efficient for this specific problem.
Approach 1: Approach 1: Union-Find Algorithm
This approach utilizes the Union-Find (or Disjoint Set Union, DSU) data structure to detect cycles. The key operations in Union-Find are 'find', which determines the representative of a set, and 'union', which merges two sets. When processing each edge, we attempt to unite the vertices. If both vertices are already in the same set, a cycle is detected, and this edge is the redundant one.
class UnionFind:
def __init__(self, size):
self.root = list(range(size))
self.rank = [1] * size
def find(self, x):
if x != self.root[x]:
self.root[x] = self.find(self.root[x])
return self.root[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.root[rootY] = rootX
elif self.rank[rootX] < self.rank[rootY]:
self.root[rootX] = rootY
else:
self.root[rootY] = rootX
self.rank[rootX] += 1
return True
return False
class Solution:
def findRedundantConnection(self, edges):
uf = UnionFind(len(edges) + 1) # nodes are 1-indexed
for u, v in edges:
if not uf.union(u, v):
return [u, v]class UnionFind {
private int[] root;
private int[] rank;
public UnionFind(int size) {
root = new int[size];
rank = new int[size];
for (int i = 0; i < size; ++i) {
root[i] = i;
rank[i] = 1;
}
}
public int find(int x) {
if (root[x] != x) {
root[x] = find(root[x]);
}
return root[x];
}
public boolean union(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) {
if (rank[rootX] > rank[rootY]) {
root[rootY] = rootX;
} else if (rank[rootX] < rank[rootY]) {
root[rootX] = rootY;
} else {
root[rootY] = rootX;
rank[rootX]++;
}
return true;
}
return false;
}
}
public class Solution {
public int[] findRedundantConnection(int[][] edges) {
int n = edges.length;
UnionFind uf = new UnionFind(n + 1);
for (int[] edge : edges) {
if (!uf.union(edge[0], edge[1])) {
return edge;
}
}
return new int[0];
}
}#include <vector>
#include <numeric>
using namespace std;
class UnionFind {
vector<int> root, rank;
public:
UnionFind(int size) : root(size), rank(size, 1) {
iota(root.begin(), root.end(), 0);
}
int find(int x) {
if(root[x] != x) {
root[x] = find(root[x]);
}
return root[x];
}
bool unionSets(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if(rootX != rootY) {
if(rank[rootX] > rank[rootY]) {
root[rootY] = rootX;
} else if(rank[rootX] < rank[rootY]) {
root[rootX] = rootY;
} else {
root[rootY] = rootX;
rank[rootX]++;
}
return true;
}
return false;
}
};
class Solution {
public:
vector<int> findRedundantConnection(vector<vector<int>>& edges) {
int n = edges.size();
UnionFind uf(n + 1);
for(auto& edge : edges) {
if(!uf.unionSets(edge[0], edge[1])) {
return edge;
}
}
return {};
}
};class UnionFind {
constructor(size) {
this.root = Array.from({ length: size }, (_, i) => i);
this.rank = Array(size).fill(1);
}
find(x) {
if (this.root[x] !== x) {
this.root[x] = this.find(this.root[x]);
}
return this.root[x];
}
union(x, y) {
let rootX = this.find(x);
let rootY = this.find(y);
if (rootX !== rootY) {
if (this.rank[rootX] > this.rank[rootY]) {
this.root[rootY] = rootX;
} else if (this.rank[rootX] < this.rank[rootY]) {
this.root[rootX] = rootY;
} else {
this.root[rootY] = rootX;
this.rank[rootX] += 1;
}
return true;
}
return false;
}
}
var findRedundantConnection = function(edges) {
const uf = new UnionFind(edges.length + 1);
for (let [u, v] of edges) {
if (!uf.union(u, v)) return [u, v];
}
return [];
};#include <stdio.h>
#include <stdlib.h>
typedef struct {
int *root;
int *rank;
} UnionFind;
UnionFind* createUnionFind(int size) {
UnionFind *uf = (UnionFind *)malloc(sizeof(UnionFind));
uf->root = (int *)malloc(size * sizeof(int));
uf->rank = (int *)malloc(size * sizeof(int));
for (int i = 0; i < size; ++i) {
uf->root[i] = i;
uf->rank[i] = 1;
}
return uf;
}
int find(UnionFind *uf, int x) {
if (uf->root[x] != x) {
uf->root[x] = find(uf, uf->root[x]);
}
return uf->root[x];
}
int 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->root[rootY] = rootX;
} else if (uf->rank[rootX] < uf->rank[rootY]) {
uf->root[rootX] = rootY;
} else {
uf->root[rootY] = rootX;
uf->rank[rootX]++;
}
return 1;
}
return 0;
}
int* findRedundantConnection(int** edges, int edgesSize, int* edgesColSize, int* returnSize) {
UnionFind *uf = createUnionFind(edgesSize + 1);
int* redundantEdge = (int*)malloc(2 * sizeof(int));
for (int i = 0; i < edgesSize; i++) {
if (!unionSets(uf, edges[i][0], edges[i][1])) {
redundantEdge[0] = edges[i][0];
redundantEdge[1] = edges[i][1];
*returnSize = 2;
return redundantEdge;
}
}
*returnSize = 0;
return NULL;
}public class UnionFind {
private int[] root;
private int[] rank;
public UnionFind(int size) {
root = new int[size];
rank = new int[size];
for (int i = 0; i < size; i++) {
root[i] = i;
rank[i] = 1;
}
}
public int Find(int x) {
if (root[x] != x) {
root[x] = Find(root[x]);
}
return root[x];
}
public bool Union(int x, int y) {
int rootX = Find(x);
int rootY = Find(y);
if (rootX != rootY) {
if (rank[rootX] > rank[rootY]) {
root[rootY] = rootX;
} else if (rank[rootX] < rank[rootY]) {
root[rootX] = rootY;
} else {
root[rootY] = rootX;
rank[rootX]++;
}
return true;
}
return false;
}
}
public class Solution {
public int[] FindRedundantConnection(int[][] edges) {
int n = edges.Length;
UnionFind uf = new UnionFind(n + 1);
foreach (int[] edge in edges) {
if (!uf.Union(edge[0], edge[1])) {
return edge;
}
}
return new int[0];
}
}This solution implements a Union-Find class with path compression and rank optimization to efficiently find and union nodes. By iteratively applying union operation on each edge, it detects the first edge causing a cycle, which is the redundant edge to be returned.
Time Complexity: O(n) where n is the number of edges because we process each edge once.
Space Complexity: O(n) due to the storage of the parent and rank arrays.
Approach 2: Approach 2: Depth-First Search (DFS)
The DFS approach involves simulating the construction of the graph and utilizing DFS to detect cycles whenever a new edge is being added. If a cycle is detected upon adjacent traversal, that edge is the redundant one.
def dfs(graph, source, target, visited):
if source == target:
return True
visited.add(source)
for neighbor in graph[source]:
if neighbor not in visited:
if dfs(graph, neighbor, target, visited):
return True
return False
class Solution:
def findRedundantConnection(self, edges):
graph = collections.defaultdict(set)
for u, v in edges:
visited = set()
if u in graph and v in graph and dfs(graph, u, v, visited):
return [u, v]
graph[u].add(v)
graph[v].add(u)import java.util.*;
class Solution {
private boolean dfs(Map<Integer, Set<Integer>> graph, int source, int target, Set<Integer> visited) {
if (source == target) return true;
visited.add(source);
for (int neighbor : graph.get(source)) {
if (!visited.contains(neighbor)) {
if (dfs(graph, neighbor, target, visited)) return true;
}
}
return false;
}
public int[] findRedundantConnection(int[][] edges) {
Map<Integer, Set<Integer>> graph = new HashMap<>();
for (int[] edge : edges) {
int u = edge[0], v = edge[1];
if (!graph.containsKey(u)) graph.put(u, new HashSet<>());
if (!graph.containsKey(v)) graph.put(v, new HashSet<>());
Set<Integer> visited = new HashSet<>();
if (graph.get(u).contains(v) || (graph.get(v).contains(u) && dfs(graph, u, v, visited))) {
return edge;
}
graph.get(u).add(v);
graph.get(v).add(u);
}
return new int[0];
}
}#include <vector>
#include <unordered_set>
#include <unordered_map>
using namespace std;
bool dfs(int source, int target, unordered_map<int, unordered_set<int>>& graph, unordered_set<int>& visited) {
if (source == target) return true;
visited.insert(source);
for (int neighbor : graph[source]) {
if (!visited.count(neighbor)) {
if (dfs(neighbor, target, graph, visited)) return true;
}
}
return false;
}
class Solution {
public:
vector<int> findRedundantConnection(vector<vector<int>>& edges) {
unordered_map<int, unordered_set<int>> graph;
for (auto& edge : edges) {
int u = edge[0], v = edge[1];
unordered_set<int> visited;
if (graph.count(u) && graph.count(v) && dfs(u, v, graph, visited)) {
return edge;
}
graph[u].insert(v);
graph[v].insert(u);
}
return {};
}
};var findRedundantConnection = function(edges) {
let graph = {};
const dfs = function(source, target, visited) {
if (source === target) return true;
visited.add(source);
for (let neighbor of graph[source] || []) {
if (!visited.has(neighbor)) {
if (dfs(neighbor, target, visited)) return true;
}
}
return false;
};
for (let [u, v] of edges) {
if (graph[u] && graph[v] && dfs(u, v, new Set())) {
return [u, v];
}
if (!graph[u]) graph[u] = new Set();
if (!graph[v]) graph[v] = new Set();
graph[u].add(v);
graph[v].add(u);
}
return [];
};#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
// For simplicity, assume the graph contains nodes from 1 to 1000 maximum.
#define NODE_COUNT 1001
bool dfs(int src, int target, int graph[NODE_COUNT][NODE_COUNT], bool visited[NODE_COUNT]) {
if (src == target)
return true;
visited[src] = true;
for (int i = 1; i < NODE_COUNT; ++i) {
if (graph[src][i] && !visited[i]) {
if (dfs(i, target, graph, visited))
return true;
}
}
return false;
}
void findRedundantConnection(int edges[][2], int edgesSize, int* result) {
int graph[NODE_COUNT][NODE_COUNT] = {0};
bool visited[NODE_COUNT];
for (int i = 0; i < edgesSize; ++i) {
int u = edges[i][0], v = edges[i][1];
memset(visited, 0, sizeof(bool) * NODE_COUNT);
if (graph[u][v] || (dfs(u, v, graph, visited))) {
result[0] = u;
result[1] = v;
return;
}
graph[u][v] = 1;
graph[v][u] = 1;
}
}using System;
using System.Collections.Generic;
public class Solution {
private bool dfs(Dictionary<int, HashSet<int>> graph, int source, int target, HashSet<int> visited) {
if (source == target) return true;
visited.Add(source);
foreach (var neighbor in graph[source]) {
if (!visited.Contains(neighbor)) {
if (dfs(graph, neighbor, target, visited)) return true;
}
}
return false;
}
public int[] FindRedundantConnection(int[][] edges) {
var graph = new Dictionary<int, HashSet<int>>();
foreach (var edge in edges) {
int u = edge[0], v = edge[1];
if (!graph.ContainsKey(u)) graph[u] = new HashSet<int>();
if (!graph.ContainsKey(v)) graph[v] = new HashSet<int>();
if (graph[u].Contains(v) || (graph[v].Contains(u) && dfs(graph, u, v, new HashSet<int>()))) {
return edge;
}
graph[u].Add(v);
graph[v].Add(u);
}
return new int[0];
}
}This solution constructs the graph incrementally while running DFS to check for paths from vertex u to vertex v before adding each edge. If the path exists, addition of the edge creates a cycle, thereby identifying it as redundant.
Time Complexity: O(n^2), potentially examining each pair of nodes connected by added edges in the worst case.
Space Complexity: O(n), dictated by recursive stack depth in the DFS and the graph representation.
Approach 3: Union-Find
According to the problem description, we need to find an edge that can be removed so that the remaining part is a tree with n nodes. We can traverse each edge and determine whether the two nodes of this edge are in the same connected component. If they are in the same connected component, it means this edge is redundant and can be removed, so we directly return this edge. Otherwise, we merge the two nodes connected by this edge into the same connected component.
The time complexity is O(n log n), and the space complexity is O(n). Here, n is the number of edges.
function findRedundantConnection(edges: number[][]): number[] {
const n = edges.length;
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];
};
for (let i = 0; ; ++i) {
const pa = find(edges[i][0] - 1);
const pb = find(edges[i][1] - 1);
if (pa === pb) {
return edges[i];
}
p[pa] = pb;
}
}func findRedundantConnection(edges [][]int) []int {
n := len(edges)
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]
}
for i := 0; ; i++ {
pa, pb := find(edges[i][0]-1), find(edges[i][1]-1)
if pa == pb {
return edges[i]
}
p[pa] = pb
}
}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 findRedundantConnection(edges: number[][]): number[] {
const uf = new UnionFind(edges.length);
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 findRedundantConnection(edges [][]int) []int {
uf := newUnionFind(len(edges))
for i := 0; ; i++ {
if !uf.union(edges[i][0]-1, edges[i][1]-1) {
return edges[i]
}
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Union-Find Algorithm | Time Complexity: O(n) where n is the number of edges because we process each edge once. |
| Approach 2: Depth-First Search (DFS) | Time Complexity: O(n^2), potentially examining each pair of nodes connected by added edges in the worst case. |
| Union-Find | – |
| Union-Find (Template Approach) | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Union-Find (Disjoint Set) | O(n α(n)) | O(n) | Best general solution for cycle detection while processing edges |
| Depth-First Search (DFS) | O(n²) | O(n) | Useful when practicing graph traversal or when Union-Find is unavailable |
Frequently asked questions
Is Redundant Connection easy or hard?
Redundant Connection is generally considered a medium-level graph problem. The concept is straightforward once you know Union-Find, but candidates unfamiliar with disjoint sets may initially attempt slower DFS or BFS connectivity checks.
How to solve Redundant Connection in O(n)?
Use the Union-Find data structure. Initialize each node as its own parent, then iterate through the edges. For each edge (u, v), check if find(u) equals find(v). If they are already connected, the edge creates a cycle; otherwise union the two sets. Path compression keeps operations almost constant time.
What is the best approach for Redundant Connection?
The Union-Find (Disjoint Set Union) approach is the most efficient and commonly expected solution. As you iterate through edges, you check whether the two vertices already belong to the same component. If they do, that edge forms a cycle and is the redundant connection. With path compression and union by rank, the runtime is nearly linear at O(n α(n)).
Is Redundant Connection asked at Google Amazon Meta?
Cycle detection and Union-Find problems frequently appear in interviews at companies like Amazon, Google, Meta, and Microsoft. Variants of this question show up in graph or connectivity rounds because they test understanding of disjoint sets and graph fundamentals.
What data structure is used in Redundant Connection?
The primary data structure is Union-Find (Disjoint Set Union), which efficiently tracks connected components. Graph representations like adjacency lists are used in the DFS alternative. Union-Find is preferred because it detects cycles while processing edges without repeated graph traversal.
What is the time complexity of Redundant Connection?
Using Union-Find with path compression gives O(n α(n)) time complexity, where α(n) is the inverse Ackermann function and grows extremely slowly. This is effectively linear for practical input sizes. A DFS-based approach can take O(n²) time because a traversal may run for every edge.
Redundant Connection Python or Java solution approach?
In Python or Java, the typical solution implements a Union-Find class with parent and rank arrays. For each edge, call find() on both vertices and union them if they belong to different sets. If both vertices share the same root, return that edge because it forms the cycle.