Skip to main content

684. Redundant Connection

medium

An undirected graph started as a tree on n nodes; one extra edge was added. Find that edge — return the last one (in input order) that creates a cycle. Union-Find solves it in a single pass.

By Sam K., Founder, InterviewChamp.AI · Last verified

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 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.

Constraints

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

Examples

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]

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

If you process edges in order and union the two endpoints, the FIRST edge whose endpoints are already in the same component is your answer.

Hint 2

Why? In a tree with one extra edge, exactly one edge closes a cycle. Processing in order, that edge is the redundant one — and the problem asks for the last-in-input that does so, which equals the first-detected because edges are processed in order.

Hint 3

Initialize Union-Find with n+1 (1-indexed) slots, then iterate; on find(u) == find(v) return [u, v].

Solution approach

Reveal approach

Standard Union-Find on n+1 slots (the graph is 1-indexed). Iterate edges in order; for each [u, v], find the roots of u and v. If they're equal, this edge closes a cycle — return [u, v] immediately. Otherwise union them and continue. The problem guarantees exactly one cycle-creating edge exists, so this terminates. The 'return the last in input' constraint is automatic: only ONE edge creates a cycle, and processing in order detects it on its own line. With path compression and union-by-rank the whole sweep is O(n * alpha(n)) which is effectively linear.

Complexity

Time
O(n * alpha(n))
Space
O(n)

Related patterns

  • union-find
  • graph
  • cycle-detection

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google
  • Microsoft

More Graphs practice problems

See all Graphs problems →