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

0% completed

Vote For New Content
Connecting Cities With Minimum Cost (medium)
Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

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!

Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible