Connecting Cities With Minimum Cost
Connecting Cities With Minimum Cost is a medium graphs problem solved with the minimum spanning tree pattern.
The best approach, optimal (kruskal with union-find), runs in O(E log E) time and O(V + E) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (kruskal with a dfs connectivity check) up.
Problem
There are n cities numbered from 1 to n. You are given a list connections, where connections[i] = [x, y, cost] says that a two-way road between city x and city y can be built for cost. There may be more than one possible road between the same pair of cities.
Choose roads to build so that every city can reach every other city (directly or through other cities), while paying the smallest possible total cost. Return that minimum total cost, or -1 if it is impossible to connect all the cities.
Examples
Example 1
- Input
n = 4, connections = [[1,2,4],[2,3,1],[3,4,6],[1,3,3],[2,4,5]]- Output
9- Why
- Build 2-3 (cost 1), 1-3 (cost 3) and 2-4 (cost 5). Every city is reachable and no cheaper set of roads does that.
Example 2
- Input
n = 3, connections = [[1,2,7]]- Output
-1- Why
- No road touches city 3, so it can never be connected.
Example 3
- Input
n = 3, connections = [[1,2,5],[1,2,2],[2,3,4]]- Output
6- Why
- There are two possible roads between 1 and 2; take the cheaper one (2) plus 2-3 (4).
Constraints
1 <= n <= 10^41 <= connections.length <= 10^4connections[i].length == 31 <= x_i, y_i <= n,x_i != y_i0 <= cost_i <= 10^5
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (Kruskal with a DFS connectivity check) | O(E log E + E · (V + E)) | O(V + E) |
| Optimal (Kruskal with Union-Find) | O(E log E) | O(V + E) |
1Brute force (Kruskal with a DFS connectivity check)
O(E log E + E · (V + E))Sorting costs E log E; each of the E roads may trigger a DFS over the chosen forest.O(V + E)The chosen roads as adjacency lists plus the DFS stack and visited array.Sort the roads by cost. Keep a graph of the roads chosen so far. For each road in order, run a DFS from one city to see whether the other is already reachable; if not, add the road. When n - 1 roads are chosen, every city is connected.
- Sort connections by cost.
- For each road (x, y, c): DFS over the chosen roads from x. If y is not reached, add the road to the chosen graph, add c to the total and count it.
- Return the total if n - 1 roads were chosen, otherwise -1.
class Solution {
public int minimumCost(int n, int[][] connections) {
int[][] edges = connections.clone();
Arrays.sort(edges, (a, b) -> a[2] - b[2]);
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i <= n; i++) adj.add(new ArrayList<>());
int total = 0, used = 0;
for (int[] e : edges) {
if (used == n - 1) break;
if (reachable(adj, n, e[0], e[1])) continue;
adj.get(e[0]).add(e[1]);
adj.get(e[1]).add(e[0]);
total += e[2];
used++;
}
return used == n - 1 ? total : -1;
}
private boolean reachable(List<List<Integer>> adj, int n, int from, int to) {
boolean[] seen = new boolean[n + 1];
Deque<Integer> stack = new ArrayDeque<>();
stack.push(from);
seen[from] = true;
while (!stack.isEmpty()) {
int u = stack.pop();
if (u == to) return true;
for (int v : adj.get(u)) {
if (!seen[v]) {
seen[v] = true;
stack.push(v);
}
}
}
return false;
}
}class Solution:
def minimumCost(self, n: int, connections: List[List[int]]) -> int:
edges = sorted(connections, key=lambda e: e[2])
adj = [[] for _ in range(n + 1)]
total = used = 0
for x, y, c in edges:
if used == n - 1:
break
if self.reachable(adj, n, x, y):
continue
adj[x].append(y)
adj[y].append(x)
total += c
used += 1
return total if used == n - 1 else -1
def reachable(self, adj: List[List[int]], n: int, start: int, target: int) -> bool:
seen = [False] * (n + 1)
stack = [start]
seen[start] = True
while stack:
u = stack.pop()
if u == target:
return True
for v in adj[u]:
if not seen[v]:
seen[v] = True
stack.append(v)
return Falseclass Solution {
public:
int minimumCost(int n, vector<vector<int>>& connections) {
vector<vector<int>> edges = connections;
sort(edges.begin(), edges.end(), [](const vector<int>& a, const vector<int>& b) { return a[2] < b[2]; });
vector<vector<int>> adj(n + 1);
int total = 0, used = 0;
for (auto& e : edges) {
if (used == n - 1) break;
if (reachable(adj, n, e[0], e[1])) continue;
adj[e[0]].push_back(e[1]);
adj[e[1]].push_back(e[0]);
total += e[2];
used++;
}
return used == n - 1 ? total : -1;
}
private:
bool reachable(vector<vector<int>>& adj, int n, int from, int to) {
vector<bool> seen(n + 1, false);
vector<int> stack = {from};
seen[from] = true;
while (!stack.empty()) {
int u = stack.back();
stack.pop_back();
if (u == to) return true;
for (int v : adj[u]) {
if (!seen[v]) {
seen[v] = true;
stack.push_back(v);
}
}
}
return false;
}
};function minimumCost(n, connections) {
const edges = [...connections].sort((a, b) => a[2] - b[2]);
const adj = Array.from({ length: n + 1 }, () => []);
const reachable = (from, to) => {
const seen = new Array(n + 1).fill(false);
const stack = [from];
seen[from] = true;
while (stack.length > 0) {
const u = stack.pop();
if (u === to) return true;
for (const v of adj[u]) {
if (!seen[v]) {
seen[v] = true;
stack.push(v);
}
}
}
return false;
};
let total = 0, used = 0;
for (const [x, y, c] of edges) {
if (used === n - 1) break;
if (reachable(x, y)) continue;
adj[x].push(y);
adj[y].push(x);
total += c;
used++;
}
return used === n - 1 ? total : -1;
}2Optimal (Kruskal with Union-Find)
O(E log E)Sorting dominates; each union-find operation is nearly O(1) (inverse Ackermann).O(V + E)Parent and size arrays of size V, plus the sorted copy of the roads.Same greedy order as before, but replace the DFS with a disjoint set union. find tells which component a city is in; a road is taken only when its two cities are in different components, and then the components are merged. With path compression and union by size each check is almost constant time.
- Sort connections by cost; parent[i] = i and size[i] = 1 for every city.
- For each road (x, y, c): if find(x) != find(y), union them, add c to the total and count the road.
- Stop early once n - 1 roads are taken.
- Return the total if n - 1 roads were taken, otherwise -1.
class Solution {
private int[] parent, size;
public int minimumCost(int n, int[][] connections) {
int[][] edges = connections.clone();
Arrays.sort(edges, (a, b) -> a[2] - b[2]);
parent = new int[n + 1];
size = new int[n + 1];
for (int i = 0; i <= n; i++) {
parent[i] = i;
size[i] = 1;
}
int total = 0, used = 0;
for (int[] e : edges) {
if (used == n - 1) break;
int a = find(e[0]), b = find(e[1]);
if (a == b) continue;
if (size[a] < size[b]) { int t = a; a = b; b = t; }
parent[b] = a;
size[a] += size[b];
total += e[2];
used++;
}
return used == n - 1 ? total : -1;
}
private int find(int x) {
while (parent[x] != x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
}class Solution:
def minimumCost(self, n: int, connections: List[List[int]]) -> int:
edges = sorted(connections, key=lambda e: e[2])
parent = list(range(n + 1))
size = [1] * (n + 1)
def find(x: int) -> int:
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
total = used = 0
for x, y, c in edges:
if used == n - 1:
break
a, b = find(x), find(y)
if a == b:
continue
if size[a] < size[b]:
a, b = b, a
parent[b] = a
size[a] += size[b]
total += c
used += 1
return total if used == n - 1 else -1class Solution {
vector<int> parent, sz;
int find(int x) {
while (parent[x] != x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
public:
int minimumCost(int n, vector<vector<int>>& connections) {
vector<vector<int>> edges = connections;
sort(edges.begin(), edges.end(), [](const vector<int>& a, const vector<int>& b) { return a[2] < b[2]; });
parent.assign(n + 1, 0);
sz.assign(n + 1, 1);
for (int i = 0; i <= n; i++) parent[i] = i;
int total = 0, used = 0;
for (auto& e : edges) {
if (used == n - 1) break;
int a = find(e[0]), b = find(e[1]);
if (a == b) continue;
if (sz[a] < sz[b]) swap(a, b);
parent[b] = a;
sz[a] += sz[b];
total += e[2];
used++;
}
return used == n - 1 ? total : -1;
}
};function minimumCost(n, connections) {
const edges = [...connections].sort((a, b) => a[2] - b[2]);
const parent = Array.from({ length: n + 1 }, (_, i) => i);
const size = new Array(n + 1).fill(1);
const find = (x) => {
while (parent[x] !== x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
};
let total = 0, used = 0;
for (const [x, y, c] of edges) {
if (used === n - 1) break;
let a = find(x), b = find(y);
if (a === b) continue;
if (size[a] < size[b]) [a, b] = [b, a];
parent[b] = a;
size[a] += size[b];
total += c;
used++;
}
return used === n - 1 ? total : -1;
}Edge cases to test
- Only two cities and a single road between them
- Several roads between the same pair of cities: only the cheapest can matter
- The graph is split into separate parts: return -1
- Roads with cost 0
Hints
Hint 1
You need a set of roads that touches every city, has no cycle and costs as little as possible. That is a minimum spanning tree.
Hint 2
Look at roads from cheapest to most expensive. A road is useful only if its two cities are not yet connected by the roads you already picked.
Hint 3
Answering "are these two cities already connected?" quickly is exactly what a Union-Find (disjoint set) structure does.
FAQ
What is the best time complexity for Connecting Cities With Minimum Cost?
Optimal (Kruskal with Union-Find) runs in O(E log E) time and O(V + E) extra space. Sorting dominates; each union-find operation is nearly O(1) (inverse Ackermann).
Which pattern does Connecting Cities With Minimum Cost use?
It is a graphs problem that uses the minimum spanning tree pattern.
Is there a brute force solution for Connecting Cities With Minimum Cost?
Yes. Brute force (Kruskal with a DFS connectivity check) takes O(E log E + E · (V + E)) time and O(V + E) space. Sort the roads by cost.
Which edge cases should I test for Connecting Cities With Minimum Cost?
Only two cities and a single road between them; Several roads between the same pair of cities: only the cheapest can matter; The graph is split into separate parts: return -1; Roads with cost 0.