Connecting Cities With Minimum Cost
Medium · Advanced Graphs · Union Find · Graph · Heap (Priority Queue) · Minimum Spanning Tree
Problem
There are n cities labeled 1 to n. You are given connections, where connections[i] = [x, y, cost] means a two-way road between cities x and y can be built for cost.
Return the minimum total cost of roads to build so that every pair of cities is connected by some path. If the cities cannot all be connected, return -1.
Examples
Input: n = 4, connections = [[1,2,3],[2,3,1],[3,4,4],[1,4,2],[1,3,6]] Output: 6
Build 2-3 (1), 1-4 (2) and 1-2 (3): every city is connected for 6. The road 3-4 (4) would close a cycle.
Input: n = 3, connections = [[1,2,5]] Output: -1
City 3 has no road at all, so the cities cannot all be connected.
Input: n = 2, connections = [[1,2,9],[1,2,4]] Output: 4
Of the two roads between the same cities, build the cheaper one.
Constraints
- 1 <= n <= 10^4
- 1 <= len(connections) <= 10^4
- connections[i].length == 3
- 1 <= x, y <= n, x != y
- 0 <= cost <= 10^5
Approaches
- Baseline: Kruskal, relabel a whole group on each merge — time O(E log E + n²), space O(n)
Follow-up
Prim's algorithm grows one tree from a city with a min-heap of the roads leaving it, in O(E log E) as well. Which would you pick for a dense graph given as a cost matrix? (Prim with an array runs in O(n²) without sorting any edges.)
Related problems
Start free on Cariara · Coding problems · System design studio
