Connecting Cities With Minimum Cost

Tested Python solution for LeetCode 1135 with 16 pytest cases. Generate a practice environment with lcpy.

LeetCode 1135, Medium. Topics: Union Find, Graph, Minimum Spanning Tree, Heap (Priority Queue). View on LeetCode.

Generate this problem as a practice environment: tested reference solution, 16 parametrized pytest cases, and a playground notebook:

lcpy gen -n 1135   # by problem number
lcpy gen -s connecting_cities_with_minimum_cost   # by problem name

​

Problem

There are n cities labeled from 1 to n. You are given the integer n and an array connections where connections[i] = [xi, yi, costi] indicates that the cost of connecting city xi and city yi (bidirectional connection) is costi.

Return the minimum cost to connect all the n cities such that there is at least one path between each pair of cities. If it is impossible to connect all the n cities, return -1.

The cost is the sum of the connections’ costs used.

​

Examples

Input: n = 3, connections = [[1,2,5],[1,3,6],[2,3,1]]
Output: 6
Explanation: Choosing any 2 edges will connect all cities so we choose the minimum 2.

Input: n = 4, connections = [[1,2,3],[3,4,4]]
Output: -1
Explanation: There is no way to connect all cities even if all edges are used.

​

Constraints

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

​

Solution

Reference implementation from solution.py on GitHub, full suite in test_solution.py:

class Solution:
    # Time: O(m log m) where m = len(connections)
    # Space: O(n)
    def minimum_cost(self, n: int, connections: list[list[int]]) -> int:
        parent = list(range(n + 1))
        rank = [0] * (n + 1)

        def find(node: int) -> int:
            root = node
            while parent[root] != root:
                root = parent[root]
            while parent[node] != root:
                parent[node], node = root, parent[node]
            return root

        total = 0
        edges_used = 0
        for x, y, cost in sorted(connections, key=lambda edge: edge[2]):
            rx, ry = find(x), find(y)
            if rx == ry:
                continue
            if rank[rx] < rank[ry]:
                rx, ry = ry, rx
            parent[ry] = rx
            if rank[rx] == rank[ry]:
                rank[rx] += 1
            total += cost
            edges_used += 1
            if edges_used == n - 1:
                return total
        return total if edges_used == n - 1 else -1

​

Complexity

Time	Space
O(m log m) where m = len(connections)	O(n)

​

Tags