Skip to content
RED SAGSkills
medium30 ptsunion-findgraph

Find the Redundant Cable

A network of n switches, numbered 1 to n, was originally wired as a tree (connected, no loops). Then one extra cable was added between two different switches that were not already directly connected. The list cables holds all n cables as pairs [a, b].

Return the cable that can be removed so the network becomes a tree again. If several cables qualify, return the one that appears last in cables.

Example 1

Input: cables = [[1,2],[1,3],[2,3]]
Output: [2,3]
Explanation: Removing [2,3] leaves a tree.

Example 2

Input: cables = [[1,2],[2,3],[3,4],[1,4],[1,5]]
Output: [1,4]
Explanation: The loop is 1-2-3-4-1; [1,4] is the last of those cables in the list.

Constraints

  • 3 <= n <= 2 * 10^4
  • cables.length == n
  • 1 <= a, b <= n, a != b
  • No cable is repeated.
Hint 1

Add cables one by one, tracking which switches are already connected.

Hint 2

With union-find, the first cable whose two ends already share a root closes the loop, and it is the last loop cable in the list.

Discussion 0

Join free to post in the discussion.

Good practice for: DevOps Engineer, Site Reliability Engineer, Cloud Engineer, Backend Developer, Embedded Systems Engineer

Run checks your code on 2 sample tests. Submit runs all 7 tests, including hidden ones, and earns points. Use console.log to debug. Python's first run can take a few seconds while it starts.