Connecting Cities With Minimum Cost
There are n cities labeled from 1 to n, and connections is an array where connectionsi = [city1, city2, cost] means it costs cost to connect city1 and city2 directly. Return the minimum cost to connect all n cities using Prim's algorithm ; if some city is unreachable from the others, return -1. Grow a tree outward starting at city 1, tracking the frontier — the cheapest known edge from the tree to each city not yet in it — in a min-heap , and always absorb the cheapest frontier edge next.
Constraints
- 1 ≤ n ≤ 104
- 0 ≤ connections.length ≤ 104
- connectionsi.length == 3
- 1 ≤ city1, city2 ≤ n
- 0 ≤ cost ≤ 105
- city1 != city2
Example
Input
n = 3, connections = [[1, 2, 5], [1, 3, 6], [2, 3, 1]]Output
6Explanation Absorb 1→2 for cost 5, which reveals 2→3 for cost 1 — cheaper than the old 1→3 edge (cost 6). Total cost 5 + 1 = 6.
In plain terms
- Minimum spanning tree
- A set of edges that connects every node using the smallest possible total edge weight, with no cycles.
- Frontier edge
- The cheapest known edge connecting the tree built so far to a node that isn't in the tree yet.
Grow the tree from city 1, absorbing the cheapest frontier edge
City 1root
City 2frontier 5
City 3frontier 6
Statusinit
Start the tree at city 1. Frontier: 1→2 costs 5, 1→3 costs 6 — the cheapest frontier edge is 1→2.
What happens in this step
tree = {1}
frontier: 1→2 (w=5), 1→3 (w=6)
cheapest frontier edge is 1→2 (w=5) — absorb it next.Step 1 of 3
Steps to visualize
- Start the tree at city 1 and add its edges to the frontier.
- Always absorb the cheapest frontier edge next — that grows the tree by exactly one city.
- Absorbing a city adds its edges to the frontier, replacing a costlier entry whenever a cheaper way in appears.
- Stop once every city is in the tree; the sum of absorbed edges is the minimum cost, or -1 if a city is never reached.
Walk through the code
Same walkthrough, now with the code. Press Next to move one step and watch which lines run.
City 1root
City 2frontier 5
City 3frontier 6
Statusinit
Start the tree at city 1. Frontier: 1→2 costs 5, 1→3 costs 6 — the cheapest frontier edge is 1→2.
What happens in this step
tree = {1}
frontier: 1→2 (w=5), 1→3 (w=6)
cheapest frontier edge is 1→2 (w=5) — absorb it next.Step 1 of 3
Solution
function minimumCost(n, connections) {
const adjacency = new Map();
for (let city = 1; city <= n; city++) adjacency.set(city, []);
for (const [a, b, cost] of connections) {
adjacency.get(a).push([b, cost]);
adjacency.get(b).push([a, cost]);
}
function heapPush(heap, item) {
heap.push(item);
let i = heap.length - 1;
while (i > 0) {
const parent = (i - 1) >> 1;
if (heap[parent][0] <= heap[i][0]) break;
[heap[parent], heap[i]] = [heap[i], heap[parent]];
i = parent;
}
}
function heapPop(heap) {
const top = heap[0];
const last = heap.pop();
if (heap.length > 0) {
heap[0] = last;
let i = 0;
while (true) {
const left = 2 * i + 1;
const right = 2 * i + 2;
let smallest = i;
if (left < heap.length && heap[left][0] < heap[smallest][0]) smallest = left;
if (right < heap.length && heap[right][0] < heap[smallest][0]) smallest = right;
if (smallest === i) break;
[heap[smallest], heap[i]] = [heap[i], heap[smallest]];
i = smallest;
}
}
return top;
}
const visited = new Set([1]);
const frontier = [];
for (const [neighbor, weight] of adjacency.get(1)) {
heapPush(frontier, [weight, neighbor]);
}
let totalCost = 0;
let edgesUsed = 0;
while (frontier.length > 0 && edgesUsed < n - 1) {
const [weight, node] = heapPop(frontier);
if (visited.has(node)) continue;
visited.add(node);
totalCost += weight;
edgesUsed++;
for (const [neighbor, edgeWeight] of adjacency.get(node)) {
if (!visited.has(neighbor)) heapPush(frontier, [edgeWeight, neighbor]);
}
}
return visited.size === n ? totalCost : -1;
}- Time
- O(E log V)
- Space
- O(V + E)
Test cases
| Input | Expected | Covers |
|---|---|---|
n = 3, connections = [[1, 2, 5], [1, 3, 6], [2, 3, 1]] | 6 | example from the docstring |
n = 4, connections = [[1, 2, 3], [3, 4, 4]] | -1 | two components can never be joined into one tree |
n = 1, connections = [] | 0 | a single city needs no connections at all |
n = 2, connections = [[1, 2, 10]] | 10 | smallest non-trivial case, exactly one connection |
n = 4, connections = [[1, 2, 1], [2, 3, 1], [3, 4, 1], [1, 4, 10], [1, 3, 10]] | 3 | the frontier prefers a cheap chain over pricier direct shortcuts |
n = 3, connections = [[1, 2, 1], [1, 3, 1], [2, 3, 100]] | 2 | an expensive edge that would only create a cycle is never absorbed |
n = 5, connections = [[1, 2, 2], [1, 3, 2], [1, 4, 2], [1, 5, 2], [2, 3, 1]] | 7 | a mid-tree edge undercuts a direct connection after the frontier updates |