Skip to main content
Talentd

Redundant Connection - Solution & Explanation

MediumDepth-First SearchBreadth-First SearchUnion FindGraph24 min readAsked at: Amazon, Microsoft, Meta +5
Practice this problem

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.

 

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.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.

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.

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.

Code

PythonC++JavaCJavaScriptC#

Python

C++

Java

C

JavaScript

C#

Complexity

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.

Try this approach in the editor →

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.

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.

Code

PythonC++JavaCJavaScriptC#

Python

C++

Java

C

JavaScript

C#

Complexity

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.

Try this approach in the editor →

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.

Code

PythonJavaC++GoTypeScriptJavaScript

Python

Java

C++

Go

TypeScript

JavaScript

Try this approach in the editor →

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

PythonJavaC++GoTypeScriptJavaScript

Python

Java

C++

Go

TypeScript

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Union-Find Algorithm

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: Depth-First Search (DFS)

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.

Union-Find—
Union-Find (Template Approach)—

Detailed Complexity Analysis

ApproachTimeSpaceWhen 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

Video Solution

Redundant Connection - Union Find - Leetcode 684 - Python • NeetCode • 133,798 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Redundant Connection with our built-in code editor and test cases.

Practice on FleetCode
Previous

Accounts Merge

Next

Maximum Employees to Be Invited to a Meeting