Problem 27.2 · Minimum Spanning TreesMedium

Connecting Cities With Minimum Cost

What it teaches: Kruskal on an edge list, returning −1 when the graph can't be connected.

Practise it on judges as “Connecting Cities With Minimum Cost”.

The problem

Cities are 1..n; connections[i] = [a, b, cost]. Return the minimum cost to connect all cities, or −1 if impossible.

Example 1

Input: n = 3, connections = [[1,2,5],[1,3,6],[2,3,1]]
Output: 6

Constraints

1 ≤ n ≤ 10⁴

Pattern clues in the wording

→ Edge list, connect all, minimum

These clues point to Minimum Spanning Tree: Connect all nodes with the cheapest total edges: sort edges and add each one that doesn't form a cycle (Kruskal).

Stuck? Take one hint at a time

Solution.java · starter

import java.util.*;

class Solution {
    public int minimumCost(int n, int[][] connections) {
        return -1;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	n = 3 connections = [[1,2,5],[1,3,6],[2,3,1]]	6
2	n = 4 connections = [[1,2,3],[3,4,4]]	-1

From slow to fast

Approaches

1. Kruskal · O(E log E)

Kruskal

Time O(E log E) Space O(n)

Sort by cost; union endpoints in different sets; if fewer than n − 1 edges are taken, return −1.

Approach 1

import java.util.*;

class Solution {
    private int[] parent;

    public int minimumCost(int n, int[][] connections) {
        Arrays.sort(connections, Comparator.comparingInt(c -> c[2]));
        parent = new int[n + 1];
        for (int i = 0; i <= n; i++) parent[i] = i;
        int total = 0, used = 0;
        for (int[] c : connections) {
            int a = find(c[0]), b = find(c[1]);
            if (a == b) continue;
            parent[a] = b;
            total += c[2];
            if (++used == n - 1) return total;
        }
        return n == 1 ? 0 : -1;
    }

    private int find(int x) {
        while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; }
        return x;
    }
}

Verdict: Direct.

Before you submit

Edge cases and common mistakes

Test these inputs

Disconnected (−1)
Parallel edges

Mistakes people make

Returning the total even when not all cities were connected.

Interview

Follow-up questions

What is the second-best MST?

Command Palette

The problem

Approaches

Kruskal

Edge cases and common mistakes

Follow-up questions