Redundant Connection — Medium Coding Interview Question

Given a graph that started as a tree with n nodes (1 to n) plus one additional edge, find the edge that can be removed so that the resulting graph is a tree of n nodes.

Example

Input: edges = [[1,2],[1,3],[2,3]]

Output: [2,3]

Constraints

• n == edges.length
• 3 ≤ n ≤ 1000

Topics & Companies

Topics: graphs

Asked by: Amazon, Google, Meta

Optimal Solution Complexity

Time complexity: O(n α(n)). Space complexity: O(n).

Practice more

• All DSA Problems
• DSA Patterns