Coding interview problems › Graphs & Grids

🗺️ Graphs & Grids Medium

Redundant Connection

Redundant Connection explained: add edges with Union-Find; the first edge joining two already-connected nodes is the answer. Tested Python and a live visual.

Also searched as: find the edge that creates a cycle · detect cycle in an undirected graph with union find

🔗

Try it live Free

Union-Find (DSU)

Stream edges into the Union-Find lab and watch the redundant edge get flagged as a cycle the moment both ends already share a set.

Open the playground →

The problem

A graph started as a tree on nodes 1 to n, then one extra edge was added, creating exactly one cycle. Given the edges in order, return an edge you can remove to get a tree again; if several work, return the one that appears last in the input.

Inputedges = [[1,2],[1,3],[2,3]]
Output[2, 3]
Inputedges = [[1,2],[2,3],[3,4],[1,4],[1,5]]
Output[1, 4]

The key insight

Add the edges one at a time with Union-Find. An edge whose two endpoints are already in the same set closes a cycle, because a path between them already existed. Since the graph has exactly one cycle, the first such edge found while scanning in order is also the last cycle edge in the input.

Brute force first: For each edge from the end, remove it and run a DFS to check the rest is still connected: O(E·(V + E)).

Step-by-step approach

  1. Initialise parent[i] = i for nodes 1 to n.
  2. Process edges in input order.
  3. For edge (u, v), find both roots.
  4. If the roots are equal, return [u, v]: this edge is redundant.
  5. Otherwise union the two sets and continue.

Python solution

PYTHON 3tested
def find_redundant_connection(edges):
    parent = list(range(len(edges) + 1))   # nodes are 1..n, n == len(edges)

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

    for u, v in edges:
        ru, rv = find(u), find(v)
        if ru == rv:                   # already connected: this edge closes the cycle
            return [u, v]
        parent[ru] = rv
    return []

Complexity

TimeO(n·α(n))
SpaceO(n)

There are n edges and each needs two near-constant find operations. The parent array has n + 1 entries.

Common mistakes

Frequently asked questions

What is the time and space complexity of Redundant Connection?

O(n·α(n)) time, which is effectively linear, for n edges with path compression, and O(n) space for the parent array.

Why is the first edge that closes a cycle the right answer?

The graph has exactly one cycle. Every edge before the cycle-closing one is needed to connect its nodes, and the cycle-closing edge is the last cycle edge in input order, which is what the problem asks for.

Can DFS solve it?

Yes. Before adding each edge, DFS to check whether u can already reach v; if so, return the edge. That is O(n²) overall, slower than Union-Find.

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Graphs & Grids Graph Search: BFS vs DFS lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.