Connecting Cities With Minimum Cost solution and explanation
9 more videos on this problem
Connecting cities with minimum cost || Graph theoryPepcoding · 9:42 · 10K views
1135. Connecting Cities With Minimum Cost (Biweekly Contest 5)Kelvin Chandra · 11:16 · 6K views
Kruskal + Union Find | Leetcode | 1135 | Connecting Cities With Minimum CostImran Sarwar · 18:57 · 4K views
Amazon Coding Interview Question: Connecting Cities With Minimum Costand1can · 15:19 · 3K views
Amazon Coding Interview Question | Leetcode 1135 | Connecting Cities With Minimum CostWorkWithGoogler · 10:30 · 3K views
Leetcode 1135. Connecting Cities With Minimum Cost,Priority Queue, Graph, Min Heap, Amazon InterviewNeedCode⚡ · 12:12 · 1K views
LeetCode 1135. Connecting Cities With Minimum CostKacy Codes · 11:11 · 1K views
1135. Connecting Cities With Minimum Cost - Week 1/5 Leetcode October ChallengeProgramming Live with Larry · 8:16 · 404 views
1135. Connecting Cities With Minimum Cost (Leetcode Medium)Programming Live with Larry · 7:53 · 332 views
Connecting Cities With Minimum Cost - 1135 - Leetcode Problem C++ solutionAshish Garg · 9:06 · 324 views
The 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.
Example 1:
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.
Example 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 <= 1041 <= connections.length <= 104connections[i].length == 31 <= xi, yi <= nxi != yi0 <= costi <= 105
Approach overview
Problem Overview: You are given n cities and a list of connections where each entry [city1, city2, cost] represents the cost to connect two cities. The goal is to connect every city with the minimum possible total cost. If it is impossible to connect all cities, return -1. This is a classic Minimum Spanning Tree problem on an undirected weighted graph.
Approach 1: Minimum Spanning Tree with Kruskal's Algorithm (O(E log E) time, O(V) space)
Kruskal's algorithm builds the minimum spanning tree by always selecting the cheapest edge that does not form a cycle. Start by sorting all connections by cost. Then iterate through the sorted edges and use a Union Find (Disjoint Set Union) structure to check whether the two cities already belong to the same component. If they are in different components, union them and add the edge cost to the total. The key insight: selecting the smallest valid edge at every step guarantees a globally optimal spanning tree. Sorting takes O(E log E), while union and find operations are nearly constant with path compression.
This approach works well when all edges are available upfront. The union-find structure prevents cycles efficiently and keeps the algorithm simple and fast for dense graphs.
Approach 2: Prim's Algorithm with Min Heap (O(E log V) time, O(V + E) space)
Prim's algorithm grows the minimum spanning tree starting from an arbitrary city. Maintain a priority queue (min heap) that always picks the smallest edge connecting the current tree to a new city. Each time you add a city, push all its outgoing edges into the heap. Skip edges that lead to already visited cities. This greedy expansion continues until all cities are included.
This approach relies heavily on a heap (priority queue) and adjacency lists of the graph. It is often preferred when the graph is represented with adjacency lists or when edges are discovered dynamically.
Approach 3: Naive Greedy MST Construction (O(E * V) time, O(V) space)
A simpler but inefficient strategy repeatedly scans all edges to find the smallest valid edge connecting two different components. Without an optimized structure like union-find or a heap, each step requires checking connectivity through repeated traversal. This quickly becomes expensive as the number of cities grows.
This approach mainly demonstrates the intuition behind minimum spanning trees: always expand the network with the cheapest available connection that keeps the graph acyclic.
Recommended for interviews: Kruskal's algorithm with Union Find is the expected solution. It shows strong understanding of greedy algorithms and efficient cycle detection. Mentioning the MST concept and explaining why sorting edges works demonstrates solid graph fundamentals. Prim's algorithm is also acceptable, but Kruskal tends to be easier to implement under interview pressure.
Solution
Kruskal's algorithm is a greedy algorithm used to compute the minimum spanning tree.
The basic idea of Kruskal's algorithm is to select the smallest edge from the edge set each time. If the two vertices connected by this edge are not in the same connected component, then add this edge to the minimum spanning tree, otherwise discard this edge.
For this problem, we can sort the edges in ascending order of connection cost, use a union-find set to maintain connected components, select the smallest edge each time, and if the two vertices connected by this edge are not in the same connected component, then merge these two vertices and accumulate the connection cost. If a situation occurs where the number of connected components is 1, it means that all vertices are connected, and we return the accumulated connection cost, otherwise, we return -1.
The time complexity is O(m times log m), and the space complexity is O(n). Here, m and n are the number of edges and vertices, respectively.
class Solution:
def minimumCost(self, n: int, connections: List[List[int]]) -> int:
def find(x):
if p[x] != x:
p[x] = find(p[x])
return p[x]
connections.sort(key=lambda x: x[2])
p = list(range(n))
ans = 0
for x, y, cost in connections:
x, y = x - 1, y - 1
if find(x) == find(y):
continue
p[find(x)] = find(y)
ans += cost
n -= 1
if n == 1:
return ans
return -1class Solution {
private int[] p;
public int minimumCost(int n, int[][] connections) {
Arrays.sort(connections, Comparator.comparingInt(a -> a[2]));
p = new int[n];
for (int i = 0; i < n; ++i) {
p[i] = i;
}
int ans = 0;
for (int[] e : connections) {
int x = e[0] - 1, y = e[1] - 1, cost = e[2];
if (find(x) == find(y)) {
continue;
}
p[find(x)] = find(y);
ans += cost;
if (--n == 1) {
return ans;
}
}
return -1;
}
private int find(int x) {
if (p[x] != x) {
p[x] = find(p[x]);
}
return p[x];
}
}class Solution {
public:
int minimumCost(int n, vector<vector<int>>& connections) {
vector<int> p(n);
iota(p.begin(), p.end(), 0);
sort(connections.begin(), connections.end(), [](auto& a, auto& b) { return a[2] < b[2]; });
int ans = 0;
function<int(int)> find = [&](int x) -> int {
if (p[x] != x) {
p[x] = find(p[x]);
}
return p[x];
};
for (auto& e : connections) {
int x = e[0] - 1, y = e[1] - 1, cost = e[2];
if (find(x) == find(y)) {
continue;
}
p[find(x)] = find(y);
ans += cost;
if (--n == 1) {
return ans;
}
}
return -1;
}
};function minimumCost(n: number, connections: number[][]): number {
const p: number[] = Array.from({ length: n }, (_, i) => i);
const find = (x: number): number => {
if (p[x] !== x) {
p[x] = find(p[x]);
}
return p[x];
};
connections.sort((a, b) => a[2] - b[2]);
let ans = 0;
for (const [x, y, cost] of connections) {
if (find(x - 1) === find(y - 1)) {
continue;
}
p[find(x - 1)] = find(y - 1);
ans += cost;
if (--n === 1) {
return ans;
}
}
return -1;
}func minimumCost(n int, connections [][]int) (ans int) {
p := make([]int, n)
for i := range p {
p[i] = i
}
sort.Slice(connections, func(i, j int) bool { return connections[i][2] < connections[j][2] })
var find func(int) int
find = func(x int) int {
if p[x] != x {
p[x] = find(p[x])
}
return p[x]
}
for _, e := range connections {
x, y, cost := e[0]-1, e[1]-1, e[2]
if find(x) == find(y) {
continue
}
p[find(x)] = find(y)
ans += cost
n--
if n == 1 {
return
}
}
return -1
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Kruskal's Algorithm with Union Find | O(E log E) | O(V) | Best general solution when all edges are available and you can sort them |
| Prim's Algorithm with Min Heap | O(E log V) | O(V + E) | When using adjacency lists or expanding the graph from a starting node |
| Naive Greedy MST Construction | O(E * V) | O(V) | Conceptual understanding of MST without optimized data structures |
Frequently asked questions
Is Connecting Cities With Minimum Cost easy or hard?
Connecting Cities With Minimum Cost is classified as Medium difficulty. The challenge lies in recognizing it as a Minimum Spanning Tree problem and choosing the correct greedy algorithm such as Kruskal or Prim.
Connecting Cities With Minimum Cost Python/Java solution
Most implementations follow the Kruskal pattern: sort edges by cost, iterate through them, and union cities if they are not already connected. The logic is identical across Python, Java, C++, Go, and TypeScript, differing only in syntax and class structure.
How to solve Connecting Cities With Minimum Cost in O(E log E)?
Use Kruskal's Minimum Spanning Tree algorithm. First sort all connections by cost. Then iterate through them and use a Union Find structure to connect cities if they belong to different components. Stop once exactly n-1 edges are chosen, which forms a spanning tree.
What is the best approach for Connecting Cities With Minimum Cost?
Kruskal's algorithm with a Union Find (Disjoint Set Union) data structure is the most common solution. Sort all edges by cost and add them to the network only if they connect two different components. This guarantees the minimum spanning tree while avoiding cycles. The time complexity is O(E log E) due to sorting.
Is Connecting Cities With Minimum Cost asked at Google/Amazon/Meta?
Minimum Spanning Tree problems like this frequently appear in interviews at companies such as Amazon, Google, and Meta. Variants involving network cost optimization, connecting servers, or building road systems are common graph interview questions.
What data structure is used in Connecting Cities With Minimum Cost?
The optimal approach uses a Union Find (Disjoint Set Union) data structure to track connected components efficiently. Some solutions also use a priority queue (min heap) when implementing Prim's algorithm for the minimum spanning tree.
What is the time complexity of Connecting Cities With Minimum Cost?
The optimal solution using Kruskal's algorithm runs in O(E log E) time where E is the number of connections. Sorting edges dominates the runtime, while union-find operations are nearly constant with path compression. Space complexity is O(V) for the disjoint set structure.