This content originally appeared on DEV Community and was authored by Rohith V
Problem Statement
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.
Test Cases
Example 1:
Input: n = 5, edges = [[0,1,4],[1,2,3],[1,3,2],[3,4,6]], k = 2
Output: 4
Explanation:
Remove the edge between nodes 3 and 4 (weight 6).
The resulting components have costs of 0 and 4, so the overall maximum cost is 4.
Example 2:
Input: n = 4, edges = [[0,1,5],[1,2,5],[2,3,5]], k = 1
Output: 5
Explanation:
No edge can be removed, since allowing only one component (k = 1) requires the graph to stay fully connected.
That single component’s cost equals its largest edge weight, which is 5.
Constraints:
1 <= n <= 5 * 10^4
0 <= edges.length <= 10^5
edges[i].length == 3
0 <= ui, vi < n
1 <= wi <= 10^6
1 <= k <= n
The input graph is connected.
Intuition
From the problem statement, we need to find the minimum possible value of the maximum edge weight such that, if we remove all edges with weight greater than this value, the graph splits into at most k connected components.
This hints at a binary search strategy on the edge weights, because we’re looking for the minimum value satisfying a condition.
The concept of connected components immediately suggests using Union Find (Disjoint Set Union - DSU) or DFS/BFS. Since DSU is more efficient for repeated connectivity queries, it's the preferred choice here.
So the idea is:
🔍 Use binary search on the edge weight — and for each weight W, check if the number of connected components formed using only edges ≤ W is ≤ k.
Approach
- Identify the maximum edge weight in the graph — this is the upper bound for binary search.
- Perform binary search in the range
[0, maxWeight]:- For each midpoint weight
W, consider only edges with weight ≤W. - Use Union Find to connect nodes using only those edges.
- Count the number of connected components formed.
- For each midpoint weight
- If the number of components is ≤
k, thenWis a valid candidate, but try to find a smaller one (moveright = mid - 1). - If more than
kcomponents are formed, thenWis too small (moveleft = mid + 1). - Finally, return the smallest weight that satisfies the condition.
Complexity
Time Complexity:
O(log(maxWeight) * E * α(N))
- Binary Search:
O(log(maxWeight)) - Each check: Union-Find over all
Eedges →O(E * α(N)), whereα(N)is the inverse Ackermann function (nearly constant time).
Space Complexity:
O(N) for Union-Find structures
Code
class Solution {
public int minCost(int n, int[][] edges, int k) {
if (edges == null || n <= 0 || k < 0) {
return 0;
}
int maxWeight = 0;
for (int [] edge : edges) {
maxWeight = Math.max(maxWeight, edge[2]);
}
return findMinCost(edges, k, n, maxWeight);
}
public int findMinCost(int [][] edges, int k, int n, int maxWeight) {
int low = 0;
int high = maxWeight;
int answer = -1;
while (low <= high) {
int middle = low + (high - low) / 2;
if (isGraphHaveKComponent(edges, k, middle, n)) {
answer = middle;
high = middle - 1;
}
else {
low = middle + 1;
}
}
return answer;
}
private boolean isGraphHaveKComponent(int [][] edges, int k, int currentMaxWeight, int n) {
UnionFind unionFind = new UnionFind(n);
for (int [] edge : edges) {
int node1 = edge[0];
int node2 = edge[1];
int weight = edge[2];
if (weight <= currentMaxWeight) {
unionFind.union(node1, node2);
}
}
return unionFind.getComponentCount() <= k;
}
}
class UnionFind {
int [] rank;
int [] parent;
int componentCount;
public UnionFind(int n) {
if (n <= 0) {
throw new IllegalArgumentException("N cannot be less or equal to 0");
}
componentCount = n;
rank = new int [n];
parent = new int [n];
for (int node = 0; node < n; node++) {
rank[node] = 1;
parent[node] = node;
}
}
public int findParent(int node) {
if (node != parent[node]) {
parent[node] = findParent(parent[node]);
}
return parent[node];
}
public void union(int node1, int node2) {
int parentNode1 = findParent(node1);
int parentNode2 = findParent(node2);
if (parentNode1 == parentNode2) {
return;
}
if (rank[parentNode1] < rank[parentNode2]) {
parent[parentNode1] = parentNode2;
rank[parentNode2] += rank[parentNode1];
}
else {
parent[parentNode2] = parentNode1;
rank[parentNode1] += rank[parentNode2];
}
componentCount--;
}
public boolean isConnectedComponent(int node1, int node2) {
return findParent(node1) == findParent(node2);
}
public int getComponentCount() {
return componentCount;
}
}
This content originally appeared on DEV Community and was authored by Rohith V
Rohith V | Sciencx (2025-07-13T06:55:46+00:00) Leetcode 3613. Minimize Maximum Component Cost. Retrieved from https://www.scien.cx/2025/07/13/leetcode-3613-minimize-maximum-component-cost/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.