Skip to content
Katabench
Try free

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

C#
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.

C# coding challenges →

What it practices

Union-find
Merge sets and answer connectivity questions in near-constant time.

Related katas