Redundant Connection

Difficulty: Medium Source: NeetCode

Problem

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 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
• No repeated edges, no self-loops

Prerequisites

Before attempting this problem, you should be comfortable with:

• Union-Find — the most natural and efficient solution
• Cycle detection in undirected graphs — DFS can also find the redundant edge

1. Brute Force (DFS Cycle Detection)

Intuition

Process edges one by one. Before adding each edge, check if the two nodes are already connected (via existing edges). If they are, this edge would form a cycle — return it. We can check connectivity with DFS on the current graph.

Algorithm

1. Maintain the current edge set as an adjacency list.
2. For each new edge (a, b): run DFS from a to check if b is already reachable.
   • If yes, return [a, b] (this edge is redundant).
   • If no, add the edge to the graph.

Solution

def findRedundantConnection(edges: list[list[int]]) -> list[int]:
    n = len(edges)
    graph = [[] for _ in range(n + 1)]

    def is_connected(src, dst, visited):
        if src == dst:
            return True
        visited.add(src)
        for neighbor in graph[src]:
            if neighbor not in visited:
                if is_connected(neighbor, dst, visited):
                    return True
        return False

    for a, b in edges:
        if is_connected(a, b, set()):
            return [a, b]
        graph[a].append(b)
        graph[b].append(a)

    return []


print(findRedundantConnection([[1,2],[1,3],[2,3]]))           # [2, 3]
print(findRedundantConnection([[1,2],[2,3],[3,4],[1,4],[1,5]]))  # [1, 4]

Complexity

• Time: O(N²) — one DFS per edge, each O(N)
• Space: O(N)

2. Union-Find (Optimal)

Intuition

Union-Find is perfect here. Process edges in order. For each edge (a, b), try to union a and b. If they already belong to the same component (i.e., find(a) == find(b)), this edge creates a cycle — return it. Since the problem guarantees only one extra edge, the first such edge is the answer. Because we process in order and return the first problematic edge, the returned edge is automatically the last one in input order that creates a cycle (since there’s only one cycle, any approach returns the same edge).

Algorithm

1. Initialize Union-Find with nodes 1 to n.
2. For each edge (a, b) in order:
   • If find(a) == find(b), return [a, b].
   • Otherwise, union(a, b).

Solution

def findRedundantConnection(edges: list[list[int]]) -> list[int]:
    n = len(edges)
    parent = list(range(n + 1))
    rank = [0] * (n + 1)

    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]

    def union(x, y):
        px, py = find(x), find(y)
        if px == py:
            return False  # already connected — cycle!
        if rank[px] < rank[py]:
            px, py = py, px
        parent[py] = px
        if rank[px] == rank[py]:
            rank[px] += 1
        return True

    for a, b in edges:
        if not union(a, b):
            return [a, b]

    return []


print(findRedundantConnection([[1,2],[1,3],[2,3]]))               # [2, 3]
print(findRedundantConnection([[1,2],[2,3],[3,4],[1,4],[1,5]]))   # [1, 4]
print(findRedundantConnection([[1,2],[2,3],[1,3]]))               # [1, 3]

Complexity

• Time: O(N * α(N)) — nearly O(N) with path compression
• Space: O(N)

Common Pitfalls

1-indexed nodes. The problem labels nodes from 1 to n, so allocate arrays of size n+1 and ignore index 0.

Returning the last occurrence. The problem says to return the answer that occurs last in the input. With only one extra edge, there’s exactly one edge that creates a cycle — returning it directly satisfies this requirement.

Trying to union after detecting the cycle. Once you find that find(a) == find(b), return immediately — don’t union. The edge that creates the cycle is the redundant one; unioning would corrupt the structure.