Redundant Connection

MediumGraphsunion find

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You start with a tree consisting of n nodes labeled from 1 to n. A tree is an undirected, connected graph that contains no cycles, so a tree on n nodes has exactly n - 1 edges. Someone then adds **one extra edge** between two distinct nodes that were already part of the tree. The result is given to you as a list of edges. Because of the single added edge, the graph now has exactly n edges and contains **exactly one cycle**. You are given a 2D array edges where edges[i] = [a, b] indicates an undirected edge between nodes a and b. Return the one edge that can be removed so that the remaining graph is again a valid tree (connected with no cycles). If more than one valid answer exists, return the edge that appears **last** in the input edges.

Examples

Input: edges = [[1,2],[1,3],[2,3]]
Output: [2,3]
Nodes 1, 2, 3 form a cycle. Removing [2,3] leaves the edges [1,2] and [1,3], a valid tree. It is the last edge that closes the cycle.
Input: edges = [[1,2],[2,3],[3,4],[1,4],[1,5]]
Output: [1,4]
The cycle is 1-2-3-4-1. Both [3,4] and [1,4] are part of the cycle, but [1,4] appears later in the list, so it is the answer.
Input: edges = [[1,2],[2,3],[1,3]]
Output: [1,3]
Edges [1,2] and [2,3] connect all three nodes into a tree. Adding [1,3] creates the cycle, so it is the redundant edge.

Constraints

  • `n == edges.length`
  • `3 <= n <= 1000`
  • `edges[i].length == 2`
  • `1 <= a < b <= n` is not guaranteed; nodes are labeled `1` to `n`
  • There are no repeated edges.
  • The given graph is connected and contains exactly one cycle.

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More union find problems