Connecting Cities With Minimum Cost Solution in Python

Language Options

Problem Description

Imagine you’re the mayor of a city that’s trying to connect all its neighborhoods with roads. Sounds easy, right? Just throw some asphalt around and call it a day! But wait, you’re not made of money! You need to connect these neighborhoods with the minimum cost possible.

In the world of LeetCode, this problem is known as “Connecting Cities With Minimum Cost.” You’re given a number of cities and a list of connections between them, each with a cost. Your task is to find the minimum cost to connect all the cities. If it’s impossible to connect all the cities, you should return -1.

So, if you thought your last road trip was expensive, just wait until you see the costs of connecting cities in this problem!

Code Solution


class UnionFind:
    def __init__(self, n: int):
        self.id = list(range(n))
        self.rank = [0] * n

    def unionByRank(self, u: int, v: int) -> None:
        i = self.find(u)
        j = self.find(v)
        if i == j:
            return
        if self.rank[i] < self.rank[j]:
            self.id[i] = j
        elif self.rank[i] > self.rank[j]:
            self.id[j] = i
        else:
            self.id[i] = j
            self.rank[j] += 1

    def find(self, u: int) -> int:
        if self.id[u] != u:
            self.id[u] = self.find(self.id[u])
        return self.id[u]


class Solution:
    def minimumCost(self, n: int, connections: list[list[int]]) -> int:
        ans = 0
        uf = UnionFind(n + 1)

        # Sort by cost.
        connections.sort(key=lambda x: x[2])

        for u, v, cost in connections:
            if uf.find(u) == uf.find(v):
                continue
            uf.unionByRank(u, v)
            ans += cost

        root = uf.find(1)
        if any(uf.find(i) != root for i in range(1, n + 1)):
            return -1

        return ans

Approach Explanation

The solution employs a Union-Find (or Disjoint Set Union) data structure to efficiently manage and merge the connected components of the cities. Here’s a brief breakdown of the approach:

Initialization: We create a Union-Find structure to keep track of connected components.
Sorting Connections: The connections are sorted based on their costs. This allows us to consider the cheapest connections first.
Union Operation: For each connection, we check if the two cities are already connected. If not, we connect them and add the cost to our total.
Final Check: After processing all connections, we check if all cities are connected. If not, we return -1.

Time and Space Complexity

Time Complexity: O(E log E), where E is the number of connections. This is due to the sorting step. The union and find operations are nearly constant time, O(α(N)), where α is the inverse Ackermann function.

Space Complexity: O(N), where N is the number of cities, for storing the parent and rank arrays in the Union-Find structure.

Real-World Example

Think of this problem like planning a road trip across multiple cities. You want to visit all the cities without breaking the bank. You have a list of potential roads (connections) and their costs. By choosing the cheapest roads first, you can ensure that you visit all the cities while spending the least amount of money. If some cities are unreachable, you might as well stay home!