You are given an integer n, representing n nodes numbered from 0 to n - 1 and a list of edges, where edges[i] = [ui, vi, si, musti]:
ui and vi indicates an undirected edge between nodes ui and vi.si is the strength of the edge.musti is an integer (0 or 1). If musti == 1, the edge must be included in the spanning tree. These edges cannot be upgraded.You are also given an integer k, the maximum number of upgrades you can perform. Each upgrade doubles the strength of an edge, and each eligible edge (with musti == 0) can be upgraded at most once.
The stability of a spanning tree is defined as the minimum strength score among all edges included in it.
Return the maximum possible stability of any valid spanning tree. If it is impossible to connect all nodes, return -1.
Note: A spanning tree of a graph with n nodes is a subset of the edges that connects all nodes together (i.e. the graph is connected) without forming any cycles, and uses exactly n - 1 edges.
Example 1:
Input: n = 3, edges = [[0,1,2,1],[1,2,3,0]], k = 1
Output: 2
Explanation:
[0,1] with strength = 2 must be included in the spanning tree.[1,2] is optional and can be upgraded from 3 to 6 using one upgrade.Example 2:
Input: n = 3, edges = [[0,1,4,0],[1,2,3,0],[0,2,1,0]], k = 2
Output: 6
Explanation:
k = 2 upgrades are allowed.[0,1] from 4 to 8 and [1,2] from 3 to 6.Example 3:
Input: n = 3, edges = [[0,1,1,1],[1,2,1,1],[2,0,1,1]], k = 0
Output: -1
Explanation:
Constraints:
2 <= n <= 1051 <= edges.length <= 105edges[i] = [ui, vi, si, musti]0 <= ui, vi < nui != vi1 <= si <= 105musti is either 0 or 1.0 <= k <= nProblem Overview: You are given a graph where some edges may be upgraded to improve their stability. The goal is to build a spanning tree whose overall stability is maximized while using at most k upgrades. The challenge is deciding which edges to upgrade and which edges to include so the graph remains connected.
Approach 1: Enumerate Upgrade Combinations + MST (Brute Force) (Time: O(2^E * E log E), Space: O(E))
The most direct idea is to try every possible set of edges to upgrade and compute the resulting spanning tree. For each configuration, adjust the upgraded edge weights and run a standard MST algorithm such as Kruskal’s. Track the maximum stability value achieved. This approach guarantees correctness but becomes infeasible quickly because the number of upgrade combinations grows exponentially with the number of edges.
Approach 2: Greedy MST with Upgrades (Time: O(E log E), Space: O(V))
A natural improvement is to sort edges by stability and greedily build the spanning tree using Kruskal’s algorithm. While iterating through edges, you can optionally upgrade edges that would help improve the minimum stability in the tree. A Union-Find structure keeps track of connected components. This reduces search space but still struggles because deciding when to upgrade an edge locally may not lead to the globally optimal stability.
Approach 3: Binary Search + Union-Find (Optimal) (Time: O(E log W), Space: O(V))
The key observation: instead of constructing the best tree directly, you can binary search the answer. Guess a candidate stability value S and check whether it is possible to build a spanning tree where every selected edge has stability at least S, allowing up to k upgrades.
During the feasibility check, iterate through all edges. Edges that already satisfy weight ≥ S can be used normally. Edges that can reach S after an upgrade are counted toward the upgrade budget. Use a Union-Find structure to connect components while tracking how many upgrades are required. If the graph becomes fully connected using ≤ k upgrades, the candidate stability is feasible.
Binary search the maximum feasible S. Each feasibility test runs nearly linear time using Union-Find with path compression. This transforms a difficult combinatorial optimization into repeated connectivity checks. The approach combines Binary Search, Union-Find, and concepts from Minimum Spanning Tree construction.
Recommended for interviews: The Binary Search + Union-Find approach. Brute force shows you understand MST construction, but the optimal solution demonstrates the key insight: convert the optimization goal into a decision problem and verify connectivity efficiently with Union-Find.
According to the problem description, the stability of a spanning tree is determined by the minimum strength edge in it. If a stability x is feasible, then for any y < x, stability y is also feasible. Therefore, we can use binary search to find the maximum stability.
We first add all required edges into the Union-Find and record the minimum strength mn among them. If there is a cycle among the required edges, return -1 directly. Then we add all edges into the Union-Find; if the final number of connected components is greater than 1, it means not all nodes can be connected, and we return -1.
Next, we perform binary search in the range [1, mn]. We define a function check(lim) to check whether there exists a spanning tree with stability at least lim. In the check function, we first add all edges with strength no less than lim into the Union-Find. Then we try to use the upgrade count to connect the remaining edges, with the condition that the edge strength is at least lim/2 (since upgrading doubles the strength). If the final number of connected components in the Union-Find is 1, a spanning tree satisfying the condition exists.
The time complexity is O((m times \alpha(n) + n) times log M), and the space complexity is O(n). Here, m is the number of edges, n is the number of nodes, and M is the maximum edge strength.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Enumerate Upgrade Sets + MST | O(2^E * E log E) | O(E) | Conceptual baseline for very small graphs or understanding upgrade impact |
| Greedy Kruskal with Upgrades | O(E log E) | O(V) | When experimenting with heuristic upgrade decisions |
| Binary Search + Union-Find | O(E log W) | O(V) | Optimal approach for large graphs and interview settings |
Maximize Spanning Tree Stability with Upgrades | Detailed | Broken Down | Leetcode 3600 | MIK • codestorywithMIK • 9,148 views views
Watch 9 more video solutions →Practice Maximize Spanning Tree Stability with Upgrades with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor