LeetCode Solutions Blog

Connecting Cities With Minimum Cost

Number: 1100

Difficulty: Medium

Paid? Yes

Companies: Amazon

Problem Description

You are given n cities and a list of connections where each connection specifies two cities and the cost to connect them. The goal is to connect all the cities with the minimum total cost. If it isn’t possible to connect all cities using the given connections, return -1.

Key Insights

This is a Minimum Spanning Tree (MST) problem.
Kruskal’s algorithm can be used by sorting the edges by cost and using a Union-Find (Disjoint Set Union) structure to efficiently check if adding an edge forms a cycle.
Alternatively, Prim’s algorithm with a priority queue can solve this, but Kruskal’s is straightforward given edge-based input.
The key is to add edges one by one in increasing order of cost until all cities are connected.

Space and Time Complexity

Time Complexity: O(E log E) due to sorting the connections, where E is the number of connections. Space Complexity: O(n) for the Union-Find data structure, plus O(E) space for storing the edges.

Solution

We use Kruskal's algorithm to build a Minimum Spanning Tree. First, sort the connections by cost. Then, iterate through each edge and use a Union-Find data structure to determine if the current edge connects two previously disconnected components. If it does, add the edge’s cost to the total cost and union the two components. Finally, if we have connected all n cities (i.e., used n-1 edges), return the total cost; otherwise, return -1.

Code Solutions

# Python solution using Union Find (Kruskal's Algorithm)

# Define the Union find class to manage connected components
class UnionFind:
    def __init__(self, size):
        # Parent list: each node is initially its own parent.
        self.parent = list(range(size))
    
    def find(self, x):
        # Path Compression: make every node on the path point directly to the root
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        # Union the roots of x and y, if they are different
        rootX = self.find(x)
        rootY = self.find(y)
        if rootX == rootY:
            return False  # x and y are already in the same set
        self.parent[rootY] = rootX
        return True

def minimumCost(n, connections):
    # Sort the connections based on cost
    connections.sort(key=lambda x: x[2])
    
    uf = UnionFind(n)
    total_cost = 0
    edges_used = 0
    
    # Iterate over each connection in sorted order
    for city1, city2, cost in connections:
        # Adjust city labels to 0-indexed
        if uf.union(city1 - 1, city2 - 1):
            total_cost += cost
            edges_used += 1
            # Once we use n-1 edges, all cities are connected
            if edges_used == n - 1:
                return total_cost
    # If we haven't connected all cities, return -1
    return -1

# Example usage:
# print(minimumCost(3, [[1,2,5],[1,3,6],[2,3,1]]))