Coding Interview PatternsRedundant Connection
MediumUnion Find

Redundant Connection

Explanation & Solution

Practice Problem

Description

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 of length n 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.

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

Output:[2,3]
0
2
1
3

Explanation: The edge [2,3] creates a cycle between nodes 1, 2, and 3. Removing it leaves a valid tree.

Constraints

  • n == edges.length
  • 3 <= n <= 1000
  • edges[i].length == 2
  • 1 <= ai < bi <= edges.length
  • ai != bi
  • There are no repeated edges.
  • The given graph is connected.

Approach

Union Find pattern

1. Initialize Union Find

  • Create a parent array where each node is its own parent (self-loop)
  • Create a rank array initialized to 0 for union by rank optimization
  • Nodes are labeled 1 to n, so arrays are sized n + 1

2. Implement Find with Path Compression

  • The find function recursively finds the root of a node
  • Path compression: during find, each node is directly linked to the root
  • This flattens the tree structure, making future finds nearly O(1)

3. Implement Union by Rank

  • The union function merges two components
  • Find the roots of both nodes
  • If they share the same root, they are already connected — return false (cycle detected)
  • Otherwise, attach the smaller-rank tree under the larger-rank tree
  • If ranks are equal, pick one as root and increment its rank

4. Process Edges in Order

  • Iterate through each edge [u, v] in the input order
  • Attempt to union u and v
  • If union returns false, this edge connects two already-connected nodes — it is the redundant edge
  • Return this edge immediately

5. Why Last Edge Works

  • Since we process edges in order, the first edge that creates a cycle is also the last such edge in the input (the problem guarantees exactly one extra edge)
  • The problem asks for the last edge in input that could be removed, which is exactly the edge that completes the cycle

Key Insight

  • A tree with n nodes has exactly n - 1 edges; the nth edge must create a cycle
  • Union Find detects the cycle the moment we try to connect two nodes that already share a root
  • Path compression + union by rank gives nearly O(α(n)) per operation, where α is the inverse Ackermann function
Time
**O(n · α(n))** ≈ O(n)
Space
O(n) for the parent and rank arrays

Visualization

Input:
Connected Components4 nodes, 3 edges
0123
output—

Press play to start connected components

CurrentQueuedVisited
8 steps

Solution Code

Next
Number of Provinces