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 Alex Chen, 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

Practice these live with InterviewChamp.AI

Drill Redundant Connection and Graphs problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →