Redundant Connection

TIP103 Unit 7 Session 1 (Click for link to problem statements)

Problem Highlights

• 💡 Difficulty: Medium
• ⏰ Time to complete: 25-30 mins
• 🛠️ Topics: Graphs, Union-Find (Disjoint Set), Cycle Detection

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Established a set (2-3) of test cases to verify their own solution later.
• Established a set (1-2) of edge cases to verify their solution handles complexities.
• Have fully understood the problem and have no clarifying questions.
• Have you verified any Time/Space Constraints for this problem?

• Q: What does the input graph look like?

  • A: It started as a tree with n nodes labeled 1 to n, and exactly one extra edge was added. That extra edge creates exactly one cycle, so the graph has n nodes and n edges.

• Q: What should the function return?

  • A: One edge that can be removed so the remaining graph is a tree again. If several edges would work, return the one that appears last in the input list.

• Q: Are the edges directed?

  • A: No, the edges are undirected. [u, v] connects node u and node v in both directions.

HAPPY CASE
Input: edges = [[1, 2], [1, 3], [2, 3]]
Output: [2, 3]
Explanation: Nodes 1, 2, and 3 form a triangle. Removing any of the three edges breaks the cycle, but [2, 3] is the one that appears last in the input.

Input: edges = [[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]]
Output: [1, 4]
Explanation: The cycle is 1 -> 2 -> 3 -> 4 -> 1. Edge [1, 4] closes that cycle and is the last cycle edge in the input; [1, 5] comes later but is not part of any cycle.

EDGE CASE
Input: edges = [[1, 2], [2, 1]]
Output: [2, 1]
Explanation: The smallest possible input. The tree is the single edge [1, 2], and the duplicate edge [2, 1] creates the cycle, so it is the redundant one.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Cycle Detection in an Undirected Graph, we can consider the following approaches:

• Union-Find (Disjoint Set): Process edges one at a time, merging the sets of the two endpoints. The first edge whose endpoints are already in the same set is the edge that closes the cycle.
• DFS (Depth-First Search): For each edge, check whether its endpoints are already connected before adding it. This works but rebuilds a traversal per edge, making it slower than Union-Find.

Because edges are processed in input order, Union-Find naturally returns the last edge that completes the cycle, exactly matching the tie-breaking rule.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea:
Add edges one by one into a Union-Find structure. Each node starts in its own set. For every edge [u, v], find the root of each endpoint. If the roots differ, union the two sets and move on. If the roots are the same, u and v are already connected by earlier edges, so adding [u, v] would create the cycle — return it.

1) Initialize a `parent` array where each node is its own parent.
2) Define find(x): follow parent pointers until reaching the root, compressing the path along the way.
3) Define union(a, b): find the roots of a and b.
   a) If the roots are the same, a and b are already connected -> return False.
   b) Otherwise attach one root to the other -> return True.
4) Iterate through `edges` in order. For each edge [u, v]:
   a) If union(u, v) fails, return [u, v].

⚠️ Common Mistakes

• Forgetting that nodes are labeled 1 to n, and sizing the parent array as n instead of n + 1 (or off-by-one when using 0-indexed arrays).
• Returning the first edge of the cycle found by a traversal instead of the last edge in input order — processing edges in input order with Union-Find handles this automatically.
• Comparing the nodes themselves instead of their roots when checking whether two nodes are already connected.
• Skipping path compression, which is fine for correctness but slows find down on long parent chains.

4: I-mplement

Implement the code to solve the algorithm.

def find_redundant_connection(edges):
    n = len(edges)
    parent = [i for i in range(n + 1)]  # parent[i] = parent of node i

    def find(x):
        # Find the root of x, compressing the path along the way
        while parent[x] != x:
            parent[x] = parent[parent[x]]  # Path compression
            x = parent[x]
        return x

    def union(a, b):
        # Merge the sets containing a and b; return False if already merged
        root_a, root_b = find(a), find(b)
        if root_a == root_b:
            return False  # a and b are already connected -> cycle
        parent[root_a] = root_b
        return True

    for u, v in edges:
        if not union(u, v):
            return [u, v]  # This edge closes the cycle

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

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

  • Edge [1, 2]: roots 1 and 2 differ, union them.
  • Edge [1, 3]: roots differ, union them. Nodes 1, 2, 3 now share one root.
  • Edge [2, 3]: find(2) and find(3) return the same root, so union fails.
  • Output: [2, 3]

• Input: edges = 1, 2], [2, 3], [3, 4], [1, 4], [1, 5

  • Edges [1, 2], [2, 3], [3, 4]: each union succeeds, merging nodes 1-4 into one set.
  • Edge [1, 4]: find(1) and find(4) return the same root, so union fails.
  • Output: [1, 4] (edge [1, 5] is never reached)

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

  • Output: [2, 1] (the duplicate edge is the redundant one)

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume N is the number of nodes (which equals the number of edges).

• Time Complexity: O(N * α(N)), where α is the inverse Ackermann function — effectively O(N). Each of the N edges performs a near-constant-time find/union thanks to path compression.
• Space Complexity: O(N) for the parent array.