Connecting Cities With Minimum Cost - Solution & Explanation
Problem Statement
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.
Code
Python
Java
C++
Go
TypeScript
Detailed 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 |
Video Solution
Connecting cities with minimum cost || Graph theory • Pepcoding • 10,417 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Connecting Cities With Minimum Cost easy or hard?
Connecting Cities With Minimum Cost Python/Java solution
How to solve Connecting Cities With Minimum Cost in O(E log E)?
What is the best approach for Connecting Cities With Minimum Cost?
Is Connecting Cities With Minimum Cost asked at Google/Amazon/Meta?
What data structure is used in Connecting Cities With Minimum Cost?
What is the time complexity of Connecting Cities With Minimum Cost?
Ready to solve this problem?
Practice Connecting Cities With Minimum Cost with our built-in code editor and test cases.
Practice on FleetCode