Connecting Cities With Minimum Cost
AmazonThe problem
There are n cities labeled from 1 to n, and edges[i] = [u, v, cost] represents a bidirectional road between city u and city v with a construction cost of cost. Your task is to find the minimum cost to connect all the cities such that every city is reachable from any other city. Return the minimum cost to connect all the cities. If it is impossible to connect all cities, return -1.
**Input: **n = 3, edges = [[1,2,5],[1,3,6],[2,3,1]] **Output: **6 **Explanation: **The minimum spanning tree consists of edges [2,3,1] and [1,2,5], with a total cost of 6.
Input: n = 4, edges = [[1,2,3],[3,4,4]] Output: -1 Explanation: It is impossible to connect all cities, as city 4 cannot be reached from city 1.
Input: n=5, edges=[[1,2,2], [2,3,3], [3,4,4],[4,5,5],[1,5,10]]
- 1 <= n <= 1000
- 1 <= edges.length <= 200000
- 1 <= cost <= 10^6
- The input guarantees that there are no duplicate edges.
cpp
class Solution {
public:
int minimumCost(int n, vector<vector<int>>& connections) {
// Your Code Goes Here
}
};java
class Solution {
public int minimumCost(int n, int[][] connections) {
// Your Code Goes Here
}
}python
class Solution(object):
def minimumCost(self, n, connections):
"""
:type n: int
:type connections: List[List[int]]
:rtype: int
"""
# Your Code Goes Herejavascript
/**
* @param {number} n
* @param {number[][]} connections
* @return {number}
*/
var minimumCost = function(n, connections) {
// Your Code Goes Here
};csharp
public class Solution
{
public static int MinimumCost(int n, List<int[]> connections)
{
// Your Code Goes Here
}
}go
func minimumCost(n int, connections [][]int) int {
}Stuck? Show a way to structure it+
- 01Sort roads by cost.
- 02Use union-find to add only edges joining distinct components.
- 03Accumulate selected costs until n-1 edges are used.
- 04Return -1 if a spanning tree cannot be formed.
Reference answer
Then expect these follow-ups
How does Prim's algorithm solve the same task?
Tests: MST alternatives
How would you return the selected roads?
Tests: reconstruction
Free to read · better with Enzo
Practice this out loud with Enzo
Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.
Next question