Problem statement

A connected undirected graph has n nodes labelled 0 to n - 1; each edges[i] = [u, v, w] joins u and v with weight w.

You may delete any number of edges (possibly none), as long as the graph that remains has at most k connected components. The cost of a component is the largest edge weight inside it, or 0 if it has no edges.

Return the minimum possible value of the largest component cost after your deletions.

Example 1

Input: n = 5, edges = [[0,1,4],[1,2,3],[1,3,2],[3,4,6]], k = 2
Output: 4
Explanation: Delete the edge of weight 6: components {0,1,2,3} (cost 4) and {4} (cost 0). Keeping only edges of weight below 4 leaves three components, too many.

Example 2

Input: n = 4, edges = [[0,1,5],[1,2,5],[2,3,5]], k = 1
Output: 5
Explanation: One component needs every node joined, and every edge weighs 5.

Example 3

Input: n = 3, edges = [[0,1,9],[1,2,1]], k = 3
Output: 0
Explanation: Three components are allowed, so every edge can go.

Constraints

• 1 <= n <= 5 * 10^4
• 0 <= edges.length <= 10^5
• edges[i] = [u, v, w]
• 0 <= u, v < n, u != v
• 0 <= w <= 10^6
• 1 <= k <= n
• the input graph is connected

Hints for Minimize Maximum Component Cost

1. Hint 1

   Fix a limit L and keep every edge of weight at most L: the largest component cost is then at most L, and keeping more edges only merges components.

2. Hint 2

   So the question is the smallest L for which the edges of weight <= L leave at most k components.

3. Hint 3

   Kruskal's algorithm answers it directly: add edges in increasing weight and stop the moment the component count reaches k.

How to solve Minimize Maximum Component Cost

This is a minimum spanning forest cut short: adding edges cheapest-first with union-find, the weight of the edge that brings the count down to k components is the smallest possible maximum.

Approach

1. If n <= k, delete everything and return 0.
2. Sort the edges by weight, smallest first, and start with n components.
3. For each edge that joins two different components, merge them and decrement the count; when it reaches k, return that edge's weight.

Why it works

For any limit L, keeping all edges of weight <= L is the best you can do with that limit — dropping some only splits components. The component count with that edge set is the count Kruskal reaches after processing every edge of weight <= L, and it first hits k exactly at the returned weight; any smaller limit leaves more than k components.

Complexity

• Time — O(m log m + m α(n))
• Space — O(n + m)

Pitfalls

• Return 0 when k >= n — no edge is needed at all.
• Edges that close a cycle do not reduce the count and must not end the loop.
• The answer is the weight of the last useful edge, not the largest weight seen so far among skipped ones.

Reference solution

Python

from typing import List

def minCost(n: int, edges: List[List[int]], k: int) -> int:
    if n <= k:
        return 0
    parent = list(range(n))

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    comps = n
    for u, v, w in sorted(edges, key=lambda e: e[2]):
        a, b = find(u), find(v)
        if a == b:
            continue
        parent[a] = b
        comps -= 1
        if comps <= k:
            return w
    return 0

Java

static int mcFind(int[] parent, int x) {
    while (parent[x] != x) {
        parent[x] = parent[parent[x]];
        x = parent[x];
    }
    return x;
}

public static int minCost(int n, int[][] edges, int k) {
    if (n <= k) return 0;
    int[] parent = new int[n];
    for (int i = 0; i < n; i++) parent[i] = i;
    int[][] sorted = edges.clone();
    Arrays.sort(sorted, (p, q) -> Integer.compare(p[2], q[2]));
    int comps = n;
    for (int[] e : sorted) {
        int a = mcFind(parent, e[0]), b = mcFind(parent, e[1]);
        if (a == b) continue;
        parent[a] = b;
        comps--;
        if (comps <= k) return e[2];
    }
    return 0;
}

C++

static int mcFind(vector<int>& parent, int x) {
    while (parent[x] != x) {
        parent[x] = parent[parent[x]];
        x = parent[x];
    }
    return x;
}

int minCost(int n, vector<vector<int>>& edges, int k) {
    if (n <= k) return 0;
    vector<int> parent(n);
    for (int i = 0; i < n; i++) parent[i] = i;
    vector<vector<int>> sorted = edges;
    sort(sorted.begin(), sorted.end(), [](const vector<int>& p, const vector<int>& q) { return p[2] < q[2]; });
    int comps = n;
    for (auto& e : sorted) {
        int a = mcFind(parent, e[0]), b = mcFind(parent, e[1]);
        if (a == b) continue;
        parent[a] = b;
        comps--;
        if (comps <= k) return e[2];
    }
    return 0;
}

JavaScript

var minCost = function(n, edges, k) {
    if (n <= k) return 0;
    var parent = [];
    for (var i = 0; i < n; i++) parent.push(i);
    var find = function(x) {
        while (parent[x] !== x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    };
    var sorted = edges.slice().sort(function(p, q) { return p[2] - q[2]; });
    var comps = n;
    for (var e = 0; e < sorted.length; e++) {
        var a = find(sorted[e][0]), b = find(sorted[e][1]);
        if (a === b) continue;
        parent[a] = b;
        comps--;
        if (comps <= k) return sorted[e][2];
    }
    return 0;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More sorting problems

• Implement Router Medium
• Longest Uploaded Prefix Medium
• Range Frequency Queries Medium
• Tweet Counts Per Frequency Medium
• Snapshot Array Medium
• Time Based Key-Value Store Medium