Tejav
#3600

Maximize Spanning Tree Stability with Upgrades

Hard
Binary SearchGreedyUnion-FindGraph TheoryMinimum Spanning TreeUnion-FindBinary Search
LeetCode ↗

Approaches

Brute ForceOptimal
Complexity Comparison
Brute ForceOptimal Solution★
Time
O(n²)
O(E log E + E * α(N))
Space
O(1)
O(N)
💡

Intuition

Time O(E log E + E * α(N))Space O(N)

Use binary search on the strength of edges while employing a union-find structure to check connectivity. This efficiently narrows down the maximum stability.

⚙️

Algorithm

3 steps
  1. 1Step 1: Sort edges by strength in descending order.
  2. 2Step 2: Use binary search on possible stability values.
  3. 3Step 3: For each mid value, check if a spanning tree can be formed with at most k upgrades.
solution.py21 lines
1def maxStability(n, edges, k):
2    edges.sort(key=lambda x: -x[2])
3    def canFormTree(min_strength):
4        parent = list(range(n))
5        rank = [0] * n
6        count = 0
7        upgrades = 0
8        for u, v, s, must in edges:
9            if s < min_strength: continue
10            if find(u) != find(v):
11                union(u, v)
12                count += 1
13                if must == 0: upgrades += 1
14            if count == n - 1: return upgrades <= k
15        return False
16    low, high = 0, max(s for _, _, s, _ in edges)
17    while low < high:
18        mid = (low + high + 1) // 2
19        if canFormTree(mid): low = mid
20        else: high = mid - 1
21    return low if low > 0 else -1
ℹ

Complexity note: Sorting edges takes O(E log E) and union-find operations are nearly constant time, leading to efficient checks.

  • 1Must edges are mandatory and can't be upgraded.
  • 2Binary search helps efficiently find the maximum stability.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.