{ }DevToolsDaily
ToolsInterview
Problems
New
CheatsheetsChat
New
BlogPricing
Ctrl + K

Redundant Connection – Solution & Complexity

Interview solutions
/
Redundant Connection

1. Understand the Goal

  • Identify the required output and the state that changes.
  • Use the examples to rule out tempting but incorrect interpretations.

2. Choose the Core Pattern

  • This problem is best exposed by Disjoint-set union detects an edge joining already-connected nodes.
  • Maintain only the state needed for the next operation.

3. Build the Algorithm

  • Process each state once when possible.
  • Record state before scheduling dependent work to avoid duplicates.

4. Check Edge Cases

  • Verify the smallest input, impossible cases, and repeated values where allowed.
  • Keep output ordering deterministic.

5. Final Solution and Complexity

  • Time complexity is O(n α(n)).
  • Space complexity is O(n).
def find_redundant_connection(edges: list[list[int]]) -> list[int]:
    parent = list(range(len(edges) + 1)); rank = [0] * (len(edges) + 1)
    def find(node):
        while node != parent[node]:
            parent[node] = parent[parent[node]]; node = parent[node]
        return node
    for left, right in edges:
        a, b = find(left), find(right)
        if a == b: return [left, right]
        if rank[a] < rank[b]: a, b = b, a
        parent[b] = a
        if rank[a] == rank[b]: rank[a] += 1
    return []

FAQ

See also

Practice Redundant Connection online (run code in the browser)Clone Graph solution (medium)Course Schedule solution (medium)Network Delay Time solution (medium)Number of Islands solution (medium)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsContact Us © Monkey SkatesHave kids?