Reconnect the Stations
Medium About 30 min Free, no account needed
Find the first connection event that reunites every station without rebuilding reachability after each cable.
The brief
After an outage, a repair crew restores cables between monitoring stations. The event log records successful repairs in order. A repaired cable works in both directions and stays available. Messages may travel through several stations.
Implement int Solve(int[] connections, int stationCount). The array stores endpoint pairs: [a0, b0, a1, b1, ...]. Return the smallest number of events from the beginning of the log after which every station can reach every other station. Return -1 if the complete log never connects them all. With zero or one station, return 0.
For four stations, [0, 1, 2, 3, 1, 2] returns 3. The first two events create separate pairs. The third cable joins those pairs into a connected network.
Each pair occupies an event position even if it repeats a cable, reverses its endpoints, or connects a station to itself. For [0, 1, 0, 1, 1, 2] and three stations, return 3, not the number of distinct cables.
There are at most 200,000 stations and 200,000 events. Station IDs are 0 through stationCount - 1; all endpoints are valid, the array has even length, and a zero-station input has no events. Preserve the input array. The result is a prefix length, so the first event has answer 1.
Starter code
using System;
public class Solution
{
public int Solve(int[] connections, int stationCount)
{
throw new NotImplementedException();
}
}How it is graded
Visible examples help you iterate. Hidden tests then cover edge cases and larger inputs, and every test reports server-measured time and allocated bytes.
What it practices
- Union-find
- Merge sets and answer connectivity questions in near-constant time.
Related katas
- Last Patch Wins Hard Free Recover the final contents of a strip after a long log of overlapping range assignments.
- Boats to Save People Medium Free Pair people into two-person boats under a weight limit, using as few boats as possible.
- Coin Change (Fewest Coins) Medium Free The fewest coins that make the amount, or -1.
- Coin Change II (Count the Ways) Medium Free How many coin combinations make the amount?