Problem

There are n cities labeled from 1 to n. You are given the integer n and an array connections where connections[i] = [xi, yi, costi] indicates that the cost of connecting city xi and city yi (bidirectional connection) is costi.

Return _the minimumcost to connect all the _n cities such that there is at least one path between each pair of cities. If it is impossible to connect all the n cities, return -1,

The cost is the sum of the connections’ costs used.

Examples

Example 1:

1
2
3

Input: n = 3, connections = [[1,2,5],[1,3,6],[2,3,1]]
Output: 6
Explanation: Choosing any 2 edges will connect all cities so we choose the minimum 2.

Example 2:

1
2
3

Input: n = 4, connections = [[1,2,3],[3,4,4]]
Output: -1
Explanation: There is no way to connect all cities even if all edges are used.

Constraints:

  • 1 <= n <= 10^4
  • 1 <= connections.length <= 10^4
  • connections[i].length == 3
  • 1 <= xi, yi <= n
  • xi != yi
  • 0 <= costi <= 10^5

Solution

Method 1 – Kruskal’s Algorithm (Union-Find)

Intuition

To connect all cities with minimum cost, we need to find a Minimum Spanning Tree (MST) of the graph formed by the cities and connections. Kruskal’s algorithm is efficient for this, as it sorts all edges by cost and greedily adds the smallest edge that doesn’t form a cycle, using Union-Find to track connected components.

Approach

  1. Sort all connections by cost.
  2. Initialize Union-Find (Disjoint Set Union) for n cities.
  3. For each connection, if the two cities are not already connected, connect them and add the cost.
  4. If all cities are connected (only one component remains), return the total cost. Otherwise, return -1.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    int minimumCost(int n, vector<vector<int>>& connections) {
        sort(connections.begin(), connections.end(), [](auto &a, auto &b) { return a[2] < b[2]; });
        vector<int> p(n+1);
        iota(p.begin(), p.end(), 0);
        function<int(int)> find = [&](int x) { return p[x] == x ? x : p[x] = find(p[x]); };
        int ans = 0, cnt = 0;
        for (auto &e : connections) {
            int u = find(e[0]), v = find(e[1]);
            if (u != v) {
                p[u] = v;
                ans += e[2];
                cnt++;
            }
        }
        return cnt == n-1 ? ans : -1;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

func MinimumCost(n int, connections [][]int) int {
    sort.Slice(connections, func(i, j int) bool { return connections[i][2] < connections[j][2] })
    p := make([]int, n+1)
    for i := 0; i <= n; i++ { p[i] = i }
    var find func(int) int
    find = func(x int) int { if p[x] != x { p[x] = find(p[x]) }; return p[x] }
    ans, cnt := 0, 0
    for _, e := range connections {
        u, v := find(e[0]), find(e[1])
        if u != v {
            p[u] = v
            ans += e[2]
            cnt++
        }
    }
    if cnt == n-1 { return ans }
    return -1
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    public int minimumCost(int n, int[][] connections) {
        Arrays.sort(connections, Comparator.comparingInt(a -> a[2]));
        int[] p = new int[n+1];
        for (int i = 0; i <= n; i++) p[i] = i;
        int ans = 0, cnt = 0;
        for (int[] e : connections) {
            int u = find(p, e[0]), v = find(p, e[1]);
            if (u != v) {
                p[u] = v;
                ans += e[2];
                cnt++;
            }
        }
        return cnt == n-1 ? ans : -1;
    }
    int find(int[] p, int x) { return p[x] == x ? x : (p[x] = find(p, p[x])); }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    fun minimumCost(n: Int, connections: Array<IntArray>): Int {
        connections.sortBy { it[2] }
        val p = IntArray(n+1) { it }
        fun find(x: Int): Int = if (p[x] == x) x else { p[x] = find(p[x]); p[x] }
        var ans = 0; var cnt = 0
        for (e in connections) {
            val u = find(e[0]); val v = find(e[1])
            if (u != v) {
                p[u] = v
                ans += e[2]
                cnt++
            }
        }
        return if (cnt == n-1) ans else -1
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def minimumCost(self, n: int, connections: list[list[int]]) -> int:
        p = list(range(n+1))
        def find(x: int) -> int:
            if p[x] != x:
                p[x] = find(p[x])
            return p[x]
        ans = cnt = 0
        for x, y, c in sorted(connections, key=lambda x: x[2]):
            u, v = find(x), find(y)
            if u != v:
                p[u] = v
                ans += c
                cnt += 1
        return ans if cnt == n-1 else -1
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

impl Solution {
    pub fn minimum_cost(n: i32, mut connections: Vec<Vec<i32>>) -> i32 {
        connections.sort_by_key(|e| e[2]);
        let mut p: Vec<i32> = (0..=n).collect();
        fn find(p: &mut Vec<i32>, x: i32) -> i32 {
            if p[x as usize] != x { p[x as usize] = find(p, p[x as usize]); }
            p[x as usize]
        }
        let (mut ans, mut cnt) = (0, 0);
        for e in connections {
            let (u, v) = (find(&mut p, e[0]), find(&mut p, e[1]));
            if u != v {
                p[u as usize] = v;
                ans += e[2];
                cnt += 1;
            }
        }
        if cnt == n-1 { ans } else { -1 }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    minimumCost(n: number, connections: number[][]): number {
        connections.sort((a, b) => a[2] - b[2]);
        const p = Array.from({length: n+1}, (_, i) => i);
        function find(x: number): number {
            if (p[x] !== x) p[x] = find(p[x]);
            return p[x];
        }
        let ans = 0, cnt = 0;
        for (const [x, y, c] of connections) {
            const u = find(x), v = find(y);
            if (u !== v) {
                p[u] = v;
                ans += c;
                cnt++;
            }
        }
        return cnt === n-1 ? ans : -1;
    }
}

Complexity

  • ⏰ Time complexity: O(m log m + m α(n)), where m is the number of connections and n is the number of cities. Sorting takes O(m log m), and each union/find is nearly constant time.
  • 🧺 Space complexity: O(n), for the Union-Find parent array.