One Cable Too Many
A small office network has n devices, numbered 0 to n - 1. It used to be wired as a tree: every device reachable from every other, with no loops. Then someone plugged in one extra cable, and now packets circle round a loop and the switches complain.
The installer's log lists every cable in the order it was plugged in. You need to pick one cable to unplug so the network is a tree again. Several cables on the loop would work; the installer asks for the one that went in latest.
Your task
Write cableToUnplug(n, cables). cables has exactly n entries, each [a, b] joining devices a and b. It is a tree on all n devices plus one extra cable.
Return the cable whose removal leaves a tree. If several cables qualify, return the one that appears last in cables. Return it exactly as written in the list.
cableToUnplug(n: int, cables: int[][]) → int[]
Examples
n = 4 cables = [[0, 1], [1, 2], [2, 0], [2, 3]]
[2, 0]
The loop is 0-1-2-0. Unplugging any of its three cables leaves a tree. Of those, [2, 0] is the latest in the log. [2, 3] comes later, but it is not on the loop: unplugging it would cut device 3 off.
n = 5 cables = [[0, 1], [1, 2], [3, 4], [2, 3], [4, 1]]
[4, 1]
The loop is 1-2-3-4-1, made of [1, 2], [3, 4], [2, 3] and [4, 1]. The latest of those is [4, 1].
Constraints
- 3 ≤ n ≤ 1,000
- cables.length = n
- 0 ≤ a, b < n, a ≠ b, and no two cables join the same pair of devices
- Removing some cable leaves every device connected with no loop
Start with brute force
Try removing each cable, starting from the end of the log, and check whether the rest is still connected, for example with a depth-first search. Return the first one that works.
Each check walks the whole network, so this costs O(n²). With 1,000 devices that is around a million steps: fine here, but it does the same connectivity work over and over. Union-find gets the answer in one pass.
Hints
0 of 4 shown- Hint 1
Plug the cables of the first example in one at a time, in log order. At which moment does a loop first appear?
- Hint 2
A cable creates a loop exactly when its two devices are already connected by the cables plugged in before it. And the loop appears at the moment its last cable goes in, so that cable is the answer.
- Hint 3
So you need to keep track of which devices are already connected as cables arrive, and answer "are these two connected?" quickly. Which structure is built for exactly that?
- Hint 4
Use union-find. Go through the cables in order. For each
[a, b], find both leaders. If they are the same,aandbwere already connected: return this cable. Otherwise merge the two groups.
Walkthrough and solution
Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.
How to solve it
The network has exactly one loop, and only cables on that loop can be removed. Replay the log: before the loop is complete, every cable joins two devices that were not yet connected. The cable that completes the loop is the first one whose two ends are already connected, and since it completes the loop it is also the latest loop cable in the log. So the first cable that joins two already-connected devices is the answer.
Trace the second example, [[0,1],[1,2],[3,4],[2,3],[4,1]]:
- [0, 1]: different groups. Merge. Groups: {0,1}, {2}, {3}, {4}.
- [1, 2]: different. Merge. Groups: {0,1,2}, {3}, {4}.
- [3, 4]: different. Merge. Groups: {0,1,2}, {3,4}.
- [2, 3]: different. Merge. Groups: {0,1,2,3,4}.
- [4, 1]: same group already. Return [4, 1].
A common slip is to return the last cable in the whole log. That only works when the loop happens to close at the end. In the first example the last cable, [2, 3], is a bridge to device 3.
function cableToUnplug(n, cables) {
const parent = Array.from({ length: n }, (_, i) => i);
function find(x) {
while (parent[x] !== x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
for (const cable of cables) {
const ra = find(cable[0]), rb = find(cable[1]);
if (ra === rb) return cable; // already connected: this closes the loop
parent[ra] = rb;
}
return []; // never reached for valid input
}def cable_to_unplug(n, cables):
parent = list(range(n))
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
for cable in cables:
ra, rb = find(cable[0]), find(cable[1])
if ra == rb:
return cable # already connected: this closes the loop
parent[ra] = rb
return [] # never reached for valid inputRun your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.