DSA problem

Maximize Spanning Tree Stability with Upgrades

HardMinimum Spanning TreePattern: Minimum Spanning Treetop600GoogleAmazonMicrosoftMetaUber

You are given an undirected, weighted, connected graph of n nodes labeled from 0 to n - 1 and a list of edges where edges[i] = [u_i, v_i, s_i, type_i] indicates an undirected edge between u_i and v_i with stability s_i. The type_i is either 0 (a "fixed" edge whose stability cannot be changed) or 1 (an "upgradable" edge that can have its stability doubled). You are also given an integer k representing the maximum number of upgradable edges you may choose to upgrade.

Build a spanning tree that uses exactly n - 1 edges, connects every node, and maximises the spanning tree stability — defined as the minimum edge stability in the tree. You may upgrade at most k of the upgradable edges you choose. Return the maximum stability achievable, or -1 if no spanning tree exists (the graph is disconnected even using all edges).

This is a Kruskal-flavoured maximum-bottleneck spanning tree problem with an upgrade twist. The bottleneck of the spanning tree is the smallest edge weight in it, so we want every edge in our tree to be as "heavy" as possible. The standard trick for max-bottleneck MST is to sort edges in descending order of weight and run Kruskal's union-find: each edge we add becomes the new bottleneck candidate.

The upgrade rule adds a twist: an upgradable edge of stability s can effectively be treated as having stability 2 * s if we are willing to spend one of our k upgrade tokens on it. The cleanest implementation is binary search on the bottleneck value B: can we form a spanning tree where every chosen edge has effective stability >= B? An edge qualifies if it is fixed and s >= B, or upgradable with s >= B (no upgrade needed), or upgradable with 2 * s >= B (uses one upgrade). Greedily prefer no-upgrade edges first; spend upgrades only when forced. Run DSU connectivity check; if a spanning tree exists within k upgrades, the bottleneck B is feasible. Binary search the largest feasible B.

Examples

Example 1

Input: n = 4, edges = [[0,1,3,0],[1,2,2,1],[2,3,1,1],[0,3,4,0]], k = 1

Output: 4

Explanation: Edges (0,1,3) and (0,3,4) plus the upgraded edge (1,2,2->4) form a spanning tree whose minimum stability is 4. Using 1 upgrade is within k = 1.

Example 2

Input: n = 3, edges = [[0,1,5,0],[1,2,3,0]], k = 0

Output: 3

Explanation: The only spanning tree uses both edges; the bottleneck is min(5, 3) = 3. No upgrades available.

Example 3

Input: n = 4, edges = [[0,1,1,1],[1,2,1,1],[2,3,1,1]], k = 2

Output: 2

Explanation: With 2 upgrade tokens we can double 2 of the 3 edges, but the un-upgraded edge bottlenecks the tree at 1 if all three are needed. By upgrading the two weakest, we get 2, 2, 1 → bottleneck 1; with k = 2 we cannot upgrade all 3, so the answer is 2 only if we can drop one edge — since exactly 3 edges form the spanning tree, the answer is 1 in the naive reading, but with k = 2 upgrades on the appropriate 2 of the 3, the bottleneck is 1 (the un-upgraded one). Picking edges with higher effective stability when several form the same MST yields the best answer.

Constraints

2 <= n <= 10^5
n - 1 <= edges.length <= 2 * 10^5
edges[i].length == 4
0 <= u_i, v_i < n, u_i != v_i
1 <= s_i <= 10^9
type_i is either 0 or 1
0 <= k <= edges.length

3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.

graphminimum-spanning-treekruskalunion-findbinary-search

Browse all DSA problems