0839HardBinary SearchGreedyUnion-FindGraph TheoryMinimum Spanning Tree

Strongest Weakest Link in the Mesh

Tracked in this browser only

Trains the technique from

LeetCode 3600Maximize Spanning Tree Stability with Upgrades

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A mesh joins n relay sites numbered 0 through n - 1. Each entry edges[i] = [u, v, s, must] describes a possible two-way link between site u and site v whose signal strength is s. When must is 1 the link is already laid and has to stay; when it is 0 the link is optional. No two entries describe the same pair of sites.

The operator installs a set of links so that every site is reachable from every other and no loop is formed, which means exactly n - 1 links. Before doing so the operator may pick at most k of the optional links and double their signal strength. A link that has to stay can never be doubled.

The stability of the finished mesh is the strength of its weakest installed link. Return the largest stability achievable, or -1 if the links that have to stay already form a loop or no choice connects every site.

Examples

Example 1

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

Installing the links of strength 4 and 3 connects all three sites, and doubling the one of strength 3 makes it 6, so the weakest installed link has strength 4.

Example 2

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

All three links have to stay, and together they close a loop around the three sites, which the mesh is not allowed to contain.

Example 3

Input: n = 3, edges = [[0, 1, 7, 0]], k = 2
Output: -1

Site 2 appears in no link at all, so no set of links reaches every site and the answer is -1.

Constraints

2 <= n <= 10^5
1 <= edges.length <= 10^5
edges[i].length == 4
0 <= edges[i][0] <= 99999
0 <= edges[i][1] <= 99999
1 <= edges[i][2] <= 10^5
0 <= edges[i][3] <= 1
0 <= k <= 10^5
A link never joins a site to itself, and no pair of sites appears twice

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def best_weakest_link(n: int, edges: list[list[int]], k: int) -> int:

Java

public int bestWeakestLink(int n, int[][] edges, int k)

The intended approach

Time O((E log E) log S) for E links and strength ceiling S: one bisection step is a near-linear pass over the links.Space O(n + E) for the disjoint-set structure and the pending list.

Stability only goes down as more links are added, and asking whether a given floor is achievable is much easier than finding the best floor directly, so bisect the floor. The links that have to stay go in first, through a disjoint-set structure; if two of them ever join sites already connected they form a loop and the job is impossible. For a candidate floor, merge every optional link already at or above it, since those are free, and only then spend doubling on the links that reach the floor once doubled, which keeps an upgrade from being wasted where a free link would have served. If every site ends up in one group the floor is achievable. Finally the answer can never exceed the weakest link that had to stay, because that link is in the mesh whatever else happens.

Pythonentry point: best_weakest_link

def best_weakest_link(n, edges, k):
    # a link marked required must be in the network, so those go in first; if two
    # required links already join the same pair of sites the network is impossible
    parent = list(range(n))

    def root(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    def join(a, b):
        ra, rb = root(a), root(b)
        if ra == rb:
            return False
        parent[ra] = rb
        return True

    weakest = None
    for u, v, s, must in edges:
        if must:
            if not join(u, v):
                return -1
            if weakest is None or s < weakest:
                weakest = s

    base = parent[:]

    def spans(floor):
        """Can the required links plus links of strength >= floor, with at most k
        doubled, span every site?"""
        nonlocal parent
        parent = base[:]
        spare = k
        # links already strong enough cost nothing
        for u, v, s, must in edges:
            if must or s < floor:
                continue
            join(u, v)
        # then spend upgrades on links that reach the floor once doubled
        pending = []
        for u, v, s, must in edges:
            if must or s >= floor:
                continue
            if 2 * s >= floor:
                pending.append((u, v))
        for u, v in pending:
            if spare == 0:
                break
            if join(u, v):
                spare -= 1
        first = root(0)
        for site in range(1, n):
            if root(site) != first:
                return False
        return True

    lo = 1
    hi = 2 * 100000
    answer = -1
    while lo <= hi:
        mid = (lo + hi) // 2
        if spans(mid):
            answer = mid
            lo = mid + 1
        else:
            hi = mid - 1
    if answer < 0:
        return -1
    if weakest is not None and weakest < answer:
        answer = weakest
    return answer

The obvious version

Enumerate every set of links that could form the mesh, discard any that omits a link which has to stay or that fails to be a loop-free spanning set, then try every choice of at most k optional links to double and take the weakest link of each. Exponential in the number of links, but it makes no argument about floors or greediness.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_best_weakest_link(n, edges, k):
    import itertools
    m = len(edges)
    best = -1
    # try every subset of links to install and every subset of those to double
    for install in range(1 << m):
        chosen = [i for i in range(m) if install >> i & 1]
        if any(edges[i][3] == 1 for i in range(m) if not (install >> i & 1)):
            continue
        parent = list(range(n))

        def root(x):
            while parent[x] != x:
                x = parent[x]
            return x

        ok = True
        for i in chosen:
            u, v = edges[i][0], edges[i][1]
            ru, rv = root(u), root(v)
            if ru == rv:
                ok = False
                break
            parent[ru] = rv
        if not ok:
            continue
        if len(chosen) != n - 1:
            continue
        for size in range(0, min(k, len(chosen)) + 1):
            for boost in itertools.combinations(chosen, size):
                if any(edges[i][3] == 1 for i in boost):
                    continue
                low = None
                for i in chosen:
                    s = edges[i][2]
                    if i in boost:
                        s *= 2
                    if low is None or s < low:
                        low = s
                if low is not None and low > best:
                    best = low
    return best

How this problem was checked

Reference solution executed against 14 test cases — 14 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in