{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

Redundant Connection – Solution & Complexity

Interview solutions
/
Redundant Connection

Solution Walkthrough

  1. Step 1: Understand the Goal

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

  2. Step 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. Step 3: Build the Algorithm

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

  4. Step 4: Check Edge Cases

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

  5. Step 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)Accounts Merge solution (medium)Connected Components in an Undirected Graph solution (medium)Number of Provinces solution (medium)01 Matrix solution (medium)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?