Grokking Graph Algorithms for Coding Interviews
Ask Author
Back to course home

0% completed

Vote For New Content
Connecting Cities With Minimum Cost (medium)
On this page

Problem Statement

Examples

Try it yourself

Problem Statement

You have n cities labeled from 1 to n. You are given an integer n and a list of connections where each connection is represented as [x<sub>i</sub>, y<sub>i</sub>, cost<sub>i</sub>]. This means that there is a bidirectional road between city x<sub>i</sub> and city y<sub>i</sub> with a cost of cost<sub>i</sub>.

Return the minimum cost to connect all the cities so that there is a path between any two cities. If it's not possible to connect all cities, return -1. The total cost is the sum of the costs of the connections used.

Examples

  1. Example 1:

    • Input: n = 5, connections = [[1, 2, 2], [1, 3, 3], [4, 5, 1], [3, 4, 4], [2, 5, 6]]
    • Expected Output: 10
Image
  • Explanation: The minimum cost to connect all cities is obtained by using the connections [1, 2, 2], [1, 3, 3], [4, 5, 1], and [3, 4, 4]. This gives a total cost of 2 + 3 + 1 + 4 = 10.

  1. Example 2:

    • Input: n = 4, connections = [[1, 2, 3], [2, 3, 4], [3, 4, 5], [1, 4, 10]]
    • Expected Output: 12
Image
  • Explanation: The minimum cost to connect all cities is obtained by using the connections [1, 2, 3], [2, 3, 4], and [3, 4, 5]. This gives a total cost of 3 + 4 + 5 = 12.

  1. Example 3:

    • Input: n = 3, connections = [[1, 2, 6], [2, 3, 2], [1, 3, 10]]
    • Expected Output: 8
Image
  • Explanation: The minimum cost to connect all cities is obtained by using the connections [1, 2, 6] and [2, 3, 2]. This gives a total cost of 6 + 2 = 8.

Constraints:

  • 1 <= n <= 10<sup>4</sup>
  • 1 <= connections.length <= 10<sup>4</sup>
  • connections[i].length == 3
  • 1 <= x<sub>i</sub>, y<sub>i</sub> <= n
  • x<sub>i</sub> != y<sub>i</sub>
  • 0 <= cost<sub>i</sub> <= 10<sup>5</sup>

Try it yourself

Try solving this question here:

Python3
Python3
. . . .

.....

.....

.....

Like the course? Get enrolled and start learning!

On this page

Problem Statement

Examples

Try it yourself