You are given an undirected connected graph with n nodes labeled from 0 to n - 1 and a 2D integer array edges where edges[i] = [ui, vi, wi] denotes an undirected edge between node ui and node vi with weight wi, and an integer k.
You are allowed to remove any number of edges from the graph such that the resulting graph has at most k connected components.
The cost of a component is defined as the maximum edge weight in that component. If a component has no edges, its cost is 0.
Return the minimum possible value of the maximum cost among all components after such removals.
Example 1:
Input: n = 5, edges = [[0,1,4],[1,2,3],[1,3,2],[3,4,6]], k = 2
Output: 4
Explanation:
Example 2:
Input: n = 4, edges = [[0,1,5],[1,2,5],[2,3,5]], k = 1
Output: 5
Explanation:
k = 1) requires the graph to stay fully connected.
Constraints:
1 <= n <= 5 * 1040 <= edges.length <= 105edges[i].length == 30 <= ui, vi < n1 <= wi <= 1061 <= k <= nProblem Overview: You are given a graph where edges or nodes contribute a cost to the connected component they belong to. The goal is to combine vertices while keeping the largest component cost as small as possible. The challenge is choosing the order of connections so the maximum cost among all resulting components stays minimized.
Approach 1: Brute Force Threshold Simulation (O(E * (V + E)) time, O(V) space)
A direct approach tries every possible cost threshold. For each candidate maximum cost, iterate through the edges and build components only if the resulting component does not exceed that threshold. This requires repeatedly traversing edges and rebuilding connectivity using DFS/BFS or a temporary disjoint structure. While it helps reason about the constraint ("can we keep every component ≤ X?"), it becomes expensive because the graph is rebuilt for each candidate threshold.
Approach 2: Sorting + Union-Find (O(E log E) time, O(V) space)
The efficient solution processes edges in increasing cost order, similar to Kruskal’s algorithm. First sort edges by cost. Then iterate through them and merge components using a Union-Find (Disjoint Set Union) structure. Each union operation combines two components and updates the cost contribution for that merged component. Because edges are processed from smallest to largest, the moment a component forms, its maximum contributing cost is already minimized.
The Union-Find structure tracks component parents and optionally component metadata such as accumulated cost or size. With path compression and union by rank, each operation runs in near-constant time O(α(V)). Sorting dominates the complexity, resulting in O(E log E) overall time. This greedy strategy works because delaying expensive edges ensures the maximum component cost grows as slowly as possible.
This approach is common in graph optimization problems involving connectivity constraints. It relies on ideas from sorting, efficient component merging using union find, and greedy edge processing often seen in graph algorithms.
Recommended for interviews: Interviewers expect the Sorting + Union-Find approach. The brute force threshold idea demonstrates understanding of the constraint, but the optimal solution shows you recognize the Kruskal-style greedy pattern and know how to implement efficient disjoint-set structures.
If k = n, it means all edges can be removed. In this case, all connected components are isolated nodes, and the maximum cost is 0.
Otherwise, we can sort all edges by weight in ascending order, then use a union-find data structure to maintain connected components.
We assume that initially all nodes are not connected, with each node being an independent connected component. Starting from the edge with the smallest weight, we try to add it to the current connected components. If the number of connected components becomes less than or equal to k after adding the edge, it means all remaining edges can be removed, and the weight of the current edge is the maximum cost we are looking for. We return this weight. Otherwise, we continue processing the next edge.
The time complexity is O(n times log n), and the space complexity is O(n), where n is the number of nodes.
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Threshold Simulation | O(E * (V + E)) | O(V) | Useful for understanding feasibility checks or very small graphs |
| Sorting + Union-Find (Greedy) | O(E log E) | O(V) | Best general solution for large graphs with connectivity constraints |
Leetcode 3613 | Minimize Maximum Component Cost Detailed Explanation | Q2 Leetcode contest 458 • Samrat Bhardwaj • 573 views views
Watch 5 more video solutions →Practice Minimize Maximum Component Cost with our built-in code editor and test cases.
Practice on FleetCode