684. Redundant Connection
Redundant Connection (LeetCode 684) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Graph Traversal Patterns (DFS & BFS) pattern, in the Union-Find (Disjoint Set Union - DSU) subpattern.
How to solve Redundant Connection
Redundant Connection is a Union-Find problem, part of Graph Traversal Patterns (DFS & BFS). Master Union-Find data structure with path compression and union by rank for connectivity problems.
Work towards the solution in these steps:
- Recall that the problem involves detecting cycles in an undirected graph, which can be efficiently managed using specific data structures.
- Consider using the Union-Find (Disjoint Set Union) data structure to keep track of connected components as you process each edge.
- As you iterate through the edges, try to union the sets of the two vertices; if they are already in the same set, adding this edge creates a cycle.
The reference solution runs in O(n * α(n)) time and O(n) space.
The Redundant Connection solution and editorial walks through the full approach with reference code.
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.
Topics and companies
Topics: Depth-First Search, Breadth-First Search, Union Find, Graph.
Reported in interviews at Amazon.
How to practise Redundant Connection on Thita.ai
Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n * α(n)) time and O(n) space.
Open Redundant Connection in the code editor, or read the Redundant Connection editorial for a worked solution with its approach and complexity analysis.
Where Redundant Connection sits in the DSA pattern sheet
- Graph Traversal Patterns (DFS & BFS) pattern guide
- Union-Find (Disjoint Set Union - DSU) subpattern
- The full DSA patterns sheet
Problems related to Redundant Connection
Other problems that use the same Union-Find (Disjoint Set Union - DSU) and Graph Traversal Patterns (DFS & BFS) techniques:
- Accounts Merge — Medium, same subpattern
- Graph Valid Tree — Medium, same subpattern
- Greatest Common Divisor Traversal — Hard, same subpattern
- Largest Component Size by Common Factor — Hard, same subpattern
- Most Stones Removed with Same Row or Column — Medium, same subpattern
- Number of Connected Components in an Undirected Graph — Medium, same subpattern
Redundant Connection FAQ
What is the LeetCode number of Redundant Connection?
Redundant Connection is LeetCode problem 684, rated Medium.
What pattern is used to solve Redundant Connection?
Redundant Connection is a Union-Find problem. It belongs to the Graph Traversal Patterns (DFS & BFS) pattern, in the Union-Find (Disjoint Set Union - DSU) subpattern.
What is the time complexity of Redundant Connection?
The reference solution runs in O(n * α(n)) time and O(n) space.
Which companies ask Redundant Connection?
Redundant Connection has been reported in interviews at Amazon.