0566HardArrayBinary SearchGreedyQueueSliding WindowPrefix Sum

Lift the Weakest Relay Stop

Tracked in this browser only

Trains the technique from

LeetCode 2528Maximize the Minimum Powered City

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 single road has n numbered stops. stations[i] is how many relay masts stand at stop i. A mast standing at stop j puts signal on every stop i with |i - j| <= r, so the signal at stop i is the number of masts standing at stops within r of it, counting every mast at every such stop.

You may erect k further masts. Each one has to stand at one of the n stops, several new masts may share a stop, and they may share a stop with existing masts. You do not have to erect all k.

Return the largest value the weakest stop's signal can be raised to, that is the largest possible value of the smallest signal over all n stops.

Examples

Example 1

Input: stations = [1, 2, 4, 5, 0], r = 1, k = 2
Output: 5

The starting signals are 3, 7, 11, 9 and 5. Erecting both new masts at stop 1 gives the stop counts [1, 4, 4, 5, 0] and signals 5, 9, 13, 9 and 5, so the weakest stop reads 5.

Example 2

Input: stations = [0, 0, 0], r = 1, k = 1
Output: 1

A single mast at stop 1 reaches stops 0, 1 and 2, so every stop reads 1.

Example 3

Input: stations = [4, 4, 4, 4], r = 0, k = 0
Output: 4

With a reach of 0 each stop only sees its own masts, and no new mast may be erected, so the weakest signal stays at 4.

Constraints

n == stations.length
1 <= n <= 10^5
0 <= stations[i] <= 10^5
0 <= r <= n - 1
0 <= k <= 10^9
The answer never exceeds 1.1 * 10^10.

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 max_power(stations: list[int], r: int, k: int) -> int:

Java

public long maxPower(int[] stations, int r, int k)

The intended approach

Time O(n log(base + k)): each feasibility sweep is linear in n.Space O(n) for the prefix sums, the starting signals and the difference array.

Prefix sums turn the starting signal of every stop into one subtraction, since the signal is the sum of a window of width `2r + 1` clipped to the road. Raising the weakest stop to a given value is a yes-or-no question that gets harder as the value grows, so binary search on it between the current weakest signal and that value plus `k`. To answer one such question, sweep from the first stop onward with a difference array recording how far each batch of new masts still reaches: whenever a stop falls short, erect exactly the missing number of masts `r` stops further along, which is the furthest position that still covers this stop, and cancel their contribution once the sweep passes stop `i + 2r`. The question fails as soon as more than `k` masts have been spent.

Pythonentry point: max_power

def max_power(stations, r, k):
    # O(n log(base + k)) time, O(n) space: prefix sums give the starting signal of
    # every stop, then a binary search on the answer is checked by one left-to-right
    # sweep that spends new masts as late as they can still help, tracked with a
    # difference array.
    n = len(stations)
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i + 1] = prefix[i] + stations[i]
    base = []
    for i in range(n):
        lo = i - r
        if lo < 0:
            lo = 0
        hi = i + r + 1
        if hi > n:
            hi = n
        base.append(prefix[hi] - prefix[lo])

    def reachable(target):
        extra = [0] * (n + 2)
        running = 0
        used = 0
        for i in range(n):
            running += extra[i]
            have = base[i] + running
            if have < target:
                need = target - have
                used += need
                if used > k:
                    return False
                running += need
                end = i + 2 * r + 1
                if end <= n:
                    extra[end] -= need
        return True

    low = min(base)
    high = low + k
    while low < high:
        mid = (low + high + 1) // 2
        if reachable(mid):
            low = mid
        else:
            high = mid - 1
    return low

The obvious version

Enumerate every way of distributing exactly `k` new masts over the stops as a multiset of positions, recompute the signal of every stop from scratch for each distribution, and keep the largest weakest signal seen.

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_max_power(stations, r, k):
    import itertools
    n = len(stations)

    def weakest(counts):
        worst = None
        for i in range(n):
            total = 0
            for j in range(n):
                if abs(i - j) <= r:
                    total += counts[j]
            if worst is None or total < worst:
                worst = total
        return worst

    best = None
    for placement in itertools.combinations_with_replacement(range(n), k):
        counts = list(stations)
        for p in placement:
            counts[p] += 1
        value = weakest(counts)
        if best is None or value > best:
            best = value
    return best

How this problem was checked

Reference solution executed against 13 test cases — 13 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