DSA problem
Connecting Cities With Minimum Cost
There are n cities labelled from 1 to n. You are given a list of connections where connections[i] = [xi, yi, costi] represents a bidirectional connection between city xi and city yi with cost costi. Return the minimum cost to make all cities connected. If it is impossible to connect them, return -1.
This is a textbook Minimum Spanning Tree (MST) problem on an explicit weighted, undirected graph. Unlike "Min Cost to Connect All Points", the edges are listed for you and the graph may be sparse, so iterating directly over the edge list is the most efficient strategy. The output is the sum of weights of a spanning tree, which is a subset of n - 1 edges that connects every vertex with no cycles.
Kruskal's algorithm is the canonical fit: sort the edge list by ascending cost, then walk it and greedily accept each edge whose endpoints lie in different components, rejecting edges that would form a cycle. Component membership is tracked with a Disjoint Set Union (DSU) that supports near-constant-time find and union thanks to path compression and union by rank.
The algorithm terminates after exactly n - 1 successful unions, at which point every city belongs to the same component and the running cost is the MST weight. If the loop ends with fewer accepted edges, the graph is disconnected and the answer is -1. Sorting dominates the work, giving O(E log E) time and O(n) extra space.
Examples
n = 3, connections = [[1,2,5],[1,3,6],[2,3,1]]6n = 4, connections = [[1,2,3],[3,4,4]]-1n = 1, connections = []0Constraints
- 1 <= n <= 10^4
- 1 <= connections.length <= 10^4
- connections[i].length == 3
- 1 <= xi, yi <= n
- xi != yi
- 0 <= costi <= 10^5
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.