← All questions
Coding

Connecting Cities With Minimum Cost

Asked atAmazon
1Give yourself 5 minutes
2Answer out loud, not in your head
3Then compare with the answer below

The 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 Here

javascript

/**
 * @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+
  1. 01Sort roads by cost.
  2. 02Use union-find to add only edges joining distinct components.
  3. 03Accumulate selected costs until n-1 edges are used.
  4. 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

Hiring now

Software engineer roles are open right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

  • Senior Software Engineer -.NET

    Tyler Technologies · Annapolis, Maryland

  • Software Development Engineer II

    SaaS Labs · Bengaluru, Karnataka, India

  • Advanced Software Engineer - Product Architect (Legal, Safety, and Risk)

    Metropolitan Transportation Authority · New York, NY

Or practice this question first

Next question