Leetcode 1135. Connecting Cities With Minimum Cost
Problem Description
There are N cities numbered from 1 to N. You are given some connections among the cities. Each connection is represented as an array of three elements [city1, city2, cost], which indicates that city1 and city2 can be connected directly and the cost of this connection is cost. Note that the connection is bidirectional so connecting city1 to city2 is the same as connecting city2 to city1.
Now, the goal is to come up with a plan that connects all cities with minimum total cost. In other words, for every pair of cities, there should be a path of connections that connect those two cities together and the sum of the connection costs used should be minimum.
If it is impossible to connect all cities, the function should return -1.
Example
Consider an example where there are 3 cities and the connections among them are as follows:
1 1 - 2 with cost 5 2 1 - 3 with cost 6 3 2 - 3 with cost 1
We can connect all three cities with total cost 6 if we choose the connections 1-2 and 2-3.
Approach
The problem asks for the minimum cost to connect all cities together, which is essentially asking for a minimum spanning tree in the graph theory. A minimum spanning tree of a graph is a tree that spans all the vertices in the graph and has the minimum total edge weight.
We can use Kruskalโs algorithm to find the minimum spanning tree. Here is the basic idea of Kruskal's algorithm:
- Sort all the edges in the graph in non-decreasing order of their cost.
- Start adding edges to the MST from the edge with the smallest cost.
- Add an edge only if it doesn't form a cycle with the MST formed so far.
- Repeat steps #2 and #3 until there are (V - 1) edges in the spanning tree (V is the number of vertices in the graph).
To detect cycles, we can use Union-Find algorithm. Union-Find algorithm is a very efficient algorithm to perform the following two operations: joined(a, b) (โare a and b in the same set?โ) and join(a, b) (โput a and b into the same setโ).
Coding solutions
Python Solution
1 2python 3class UnionFind: 4 def __init__(self): 5 self.parent = {} 6 7 def union(self, x, y): 8 self.parent[self.find(x)] = self.find(y) 9 10 def find(self, x): 11 path = [] 12 while x != self.parent[x]: 13 path.append(x) 14 x = self.parent[x] 15 # compress the path leading back to the root 16 for node in path: 17 self.parent[node] = x 18 return x 19 20 21class Solution: 22 def minimumCost(self, N, connections): 23 uf = UnionFind() 24 # Initialize the parent pointer for each city 25 for i in range(1, N+1): 26 uf.parent[i] = i 27 # Sort the connections by their cost 28 connections.sort(key=lambda x: x[2]) 29 res = 0 30 for city1, city2, cost in connections: 31 if uf.find(city1) != uf.find(city2): 32 uf.union(city1, city2) 33 res += cost 34 # Check if all cities are connected 35 root = uf.find(1) 36 for i in range(2, N+1): 37 if uf.find(i) != root: 38 return -1 39 return res
Java Solution
1 2java 3class Solution { 4 public int minimumCost(int N, int[][] connections) { 5 int[] parent = new int[N+1]; 6 for (int i = 1; i <= N; i++) 7 parent[i] = i; 8 Arrays.sort(connections, (a, b) -> a[2] - b[2]); 9 int total = 0, edges = 0; 10 for (int[] conn : connections) { 11 int x = find(parent, conn[0]), y = find(parent, conn[1]); 12 if (x != y) { 13 parent[x] = y; 14 total += conn[2]; 15 edges++; 16 if (edges == N-1) 17 return total; 18 } 19 } 20 return -1; 21 } 22 23 private int find(int[] parent, int x) { 24 if (x != parent[x]) 25 parent[x] = find(parent, parent[x]); 26 return parent[x]; 27 } 28}
JavaScript Solution
1
2javascript
3class UnionFind {
4 constructor(N) {
5 this.parent = Array(N+1).fill(0).map((value, index) => index);
6 }
7
8 find(x) {
9 if (x !== this.parent[x]) {
10 this.parent[x] = this.find(this.parent[x]);
11 }
12 return this.parent[x];
13 }
14
15 union(x, y) {
16 this.parent[this.find(x)] = this.find(y);
17 }
18}
19
20var minimumCost = function(N, connections) {
21 const uf = new UnionFind(N);
22 connections.sort((a, b) => a[2] - b[2]);
23 let total = 0, edges = 0;
24 for (let conn of connections) {
25 let x = uf.find(conn[0]), y = uf.find(conn[1]);
26 if (x !== y) {
27 uf.union(x, y);
28 total += conn[2];
29 edges++;
30 if (edges === N-1)
31 return total;
32 }
33 }
34 return -1;
35};
C++ Solution
1
2cpp
3class Solution {
4public:
5 int minimumCost(int N, vector<vector<int>>& connections) {
6 vector<int> parent(N+1);
7 iota(parent.begin(), parent.end(), 0);
8 sort(connections.begin(), connections.end(), [](auto &a, auto &b){
9 return a[2] < b[2];
10 });
11 int total = 0, edges = 0;
12 for (auto &conn : connections) {
13 int x = find(parent, conn[0]), y = find(parent, conn[1]);
14 if (x != y) {
15 parent[x] = y;
16 total += conn[2];
17 edges++;
18 if (edges == N-1)
19 return total;
20 }
21 }
22 return -1;
23 }
24
25private:
26 int find(vector<int> &parent, int x) {
27 if (x != parent[x])
28 parent[x] = find(parent, parent[x]);
29 return parent[x];
30 }
31};
C# Solution
1
2csharp
3public class UnionFind
4{
5 private int[] parent;
6 public UnionFind(int n)
7 {
8 parent = new int[n+1];
9 for(int i=0; i<=n; i++) {
10 parent[i] = i;
11 }
12 }
13
14 public int Find(int x)
15 {
16 if(parent[x] != x) {
17 parent[x] = Find(parent[x]);
18 }
19 return parent[x];
20 }
21
22 public void Union(int x, int y)
23 {
24 parent[Find(x)] = Find(y);
25 }
26}
27
28public class Solution {
29 public int MinimumCost(int N, int[][] connections)
30 {
31 var uf = new UnionFind(N);
32 int totalCost = 0, edges = 0;
33
34 Array.Sort(connections, (a, b) => a[2] - b[2]);
35 foreach (var connection in connections)
36 {
37 var city1 = uf.Find(connection[0]);
38 var city2 = uf.Find(connection[1]);
39 if (city1 != city2)
40 {
41 uf.Union(connection[0], connection[1]);
42 totalCost += connection[2];
43 edges++;
44 }
45 if (edges == N - 1) return totalCost;
46 }
47 return -1;
48 }
49}
The various implementations above provide a comprehensive solution to the problem of finding the minimum cost of connections among cities. Each of these solutions uses the Union-Find algorithm combined with Kruskal's algorithm to find the minimum spanning tree of the graph that represents the connections among the cities.
Each implementation first sorts the connections by cost in ascending order. After that, it iteratively constructs a minimum spanning tree by adding the cheapest possible edge that does not create a cycle. The cycle detection is efficiently performed by the Union-Find algorithm. If it is possible to connect all cities, the final total cost of the connections used is returned. Otherwise, the function returns -1.
These implementations exhibit excellent efficiency. They have a time complexity that is roughly proportional to E log E, where E is the number of edges in the graph (the number of given connections). This time complexity is due to the sorting of the edges and the use of the Union-Find algorithm which has almost linear time complexity.
The solutions also feature good space complexity, which is approximately O(N). The Union-Find data structure occupies linear space with respect to the number of vertices (cities).
In conclusion, these solutions efficiently solve the problem by combining the power of Union-Find and Kruskal's algorithms and effectively applying the concept of minimum spanning tree from graph theory.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.