Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Binary-search a minimum power that every city should reach. In a left-to-right feasibility scan, a city's deficit forces that many new stations. Place them as far right as possible while still covering this city, maximizing their help to cities not yet checked.

Approach

Build a difference array describing existing station coverage. For each candidate power, copy it and accumulate power across cities while tracking the remaining station budget. When city i is short, add exactly its deficit at min(n - 1, i + r) and reject if the budget is insufficient. Increase the current power immediately and record its future decrease at min(n, i + 2*r + 1). This also handles placement clipped to the final city: the added coverage then lasts through the end. Earlier cities already meet the target, so only future coverage needs recording. Binary-search upward on feasible targets and return the largest feasible minimum. The rightmost-placement greedy rule makes each check use the fewest necessary stations.

class Solution:
    def maxPower(self, stations: List[int], r: int, k: int) -> int:
        n = len(stations)
        diff = [0] * (n + 1)
        for i in range(n):
            diff[max(0, i - r)] += stations[i]
            diff[min(n, i + r + 1)] -= stations[i]

        def check(target):
            dc = diff[:]
            ps = 0
            available = k

            for i in range(n):
                ps += dc[i]
                if ps < target:
                    add = target - ps
                    if add > available:
                        return False
                    ps += add
                    dc[min(n, i + r * 2 + 1)] -= add
                    available -= add

            return True

        left = min(stations)
        right = sum(stations) + k

        while left < right:
            mid = left + (right - left + 1) // 2
            if check(mid):
                left = mid
            else:
                right = mid - 1

        return left

Complexity analysis

Let n = stations.length and S = sum(stations) + k. Time is O(n log(S + 2)), including initialization and copied-difference-array feasibility scans. The +2 covers S = 0 or 1. Auxiliary space is O(n), including each feasibility copy and JavaScript's temporary copies for the initial minimum/sum.