MediumUnion FindGraphMinimum Spanning TreeHeap (Priority Queue)Sorting

Connecting Cities With Minimum Cost

1 approach, code in every language

There are n cities labeled from 1 to n. You are given a list of connections, where each connection [a, b, cost] means city a and city b can be linked for the given cost.

Return the minimum total cost needed so that every pair of cities is connected, either directly or through other cities. If it is impossible to connect all cities, return -1.

Example 1

Input: n = 3, connections = [[1,2,5],[1,3,6],[2,3,1]]

Output: 6

Choosing the edges 2-3 (cost 1) and 1-2 (cost 5) links all three cities for a total of 6, the cheapest possible.

Example 2

Input: n = 4, connections = [[1,2,3],[3,4,4]]

Output: -1

Cities {1,2} and {3,4} form two separate groups with no edge between them, so full connectivity is impossible.

Constraints

1 <= n <= 10^4
1 <= connections.length <= 10^4
connections[i].length == 3
1 <= xi, yi <= n
xi != yi
0 <= costi <= 10^5

Kruskal with Union-Find

Sort the connections by cost and greedily union endpoints, accumulating cost only for edges that merge two components.

Loading animation…

Intuition

Connecting every city with the least total cost is a Minimum Spanning Tree problem on the given weighted edges. Kruskal's algorithm processes edges from cheapest to most expensive and keeps an edge only if it links two cities that are not yet connected. A union-find structure tracks which cities already share a component, so we can reject an edge whose endpoints are already merged. A spanning tree over n cities needs exactly n-1 accepted edges; if fewer merges succeed, the graph is split into multiple pieces and connecting everything is impossible, so we return -1.

Algorithm walkthrough

1Create a union-find over cities 1..n, each city its own root.
2Sort all connections in non-decreasing order of cost.
3For each connection, look up the roots of both cities.
4If the roots differ, union them, add the cost to the total, and increment a counter of successful merges.
5After processing every edge, check whether exactly n-1 merges happened.
6Return the accumulated total if the graph is fully connected, otherwise return -1.

Implementation

class Solution:
    def minimumCost(self, n: int, connections: List[List[int]]) -> int:
        parent = list(range(n + 1))

        def find(x: int) -> int:
            while parent[x] != x:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x

        connections.sort(key=lambda c: c[2])
        total = 0
        used = 0
        for a, b, cost in connections:
            ra, rb = find(a), find(b)
            if ra != rb:
                parent[ra] = rb
                total += cost
                used += 1
        return total if used == n - 1 else -1

Time

O(E log E)

Space

O(n)

Sorting the E connections dominates; union-find uses O(n) space and near-constant time per operation with path compression.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Graphs

After the pattern

Now solve one you haven't seen.

Reading a pattern isn't the same as using it. The practice set has 1,194 original problems on the same techniques, each graded in your browser.

Open the practice set Start the FDE path

1,194 problems · 15,062 graded tests · free