LeetCode 2528 - Maximize the Minimum Powered City

The problem asks us to determine the maximum possible minimum power that any city can have after optimally adding k new power stations to an existing configuration.

leetcodehardarraybinary-searchgreedyqueuesliding-windowprefix-sum

LeetCode Problem 2528

Difficulty: 🔴 Hard
Topics: Array, Binary Search, Greedy, Queue, Sliding Window, Prefix Sum

Solution

Problem Understanding

The problem asks us to determine the maximum possible minimum power that any city can have after optimally adding k new power stations to an existing configuration. Each city already has some power stations, and each station has a range r over which it contributes to the power of nearby cities. The power of a city is the sum of all stations affecting it, including both original and added stations.

The input consists of an array stations of length n, where stations[i] is the number of existing stations at city i. We are also given the range r and the number of new stations k that can be added anywhere. The output is a single integer representing the maximum minimum power, which is the largest value we can guarantee for the city with the least power if we place the k new stations optimally.

Constraints indicate that n can be as large as 10^5 and k up to 10^9. This suggests that a naive solution checking all possible station placements is infeasible and that a logarithmic or linear scan approach is required. Edge cases include r = 0 where stations only affect their own city, k = 0 meaning no stations can be added, and arrays with uniform or highly skewed station distributions.

Approaches

A brute-force approach would try all possible ways to distribute k stations across cities and calculate the resulting minimum city power. This is clearly infeasible because the number of distributions grows combinatorially with n and k.

The key insight for an optimal solution is that the problem can be reduced to a decision problem: for a given target minimum power target, can we place stations such that every city's power is at least target? If we can solve this efficiently, we can use binary search on the possible minimum power values. To check feasibility for a given target, we can use a sliding window with a prefix sum array to maintain the cumulative effect of added stations efficiently, ensuring an O(n) check.

Approach Time Complexity Space Complexity Notes
Brute Force O((n+k)^n) O(n) Checks all possible placements of k stations; infeasible for constraints
Optimal O(n log(max_possible_power)) O(n) Uses binary search on the minimum power and a sliding window / prefix sum to efficiently check feasibility

Algorithm Walkthrough

  1. Initialize low as the minimum current power in all cities and high as the maximum possible power if all k stations were added to a single city plus its range contribution.
  2. Perform binary search while low < high. For each mid = (low + high + 1) // 2:

a. Check if it is feasible to ensure every city has at least mid power.

b. To do this efficiently, use a sliding window that represents the sum of added stations affecting the current city.

c. Iterate through cities from left to right, and whenever the current city's effective power (original + added via window) is below mid, add the necessary stations to bring it up to mid. Update the sliding window to propagate their effect to the next cities.

d. If the total stations added exceeds k, mid is not feasible. 3. If mid is feasible, update low = mid; otherwise, update high = mid - 1. 4. Return low after the binary search terminates.

Why it works: Binary search guarantees we find the maximum feasible minimum because each feasibility check is monotonic - if a target is achievable, any lower target is also achievable. The sliding window ensures the effect of added stations is accounted efficiently without recalculating for each city.

Python Solution

from typing import List

class Solution:
    def maxPower(self, stations: List[int], r: int, k: int) -> int:
        n = len(stations)

        def is_feasible(target: int) -> bool:
            added = [0] * n
            window_sum = 0
            used_stations = 0
            for i in range(n):
                if i > r:
                    window_sum -= added[i - r - 1]
                current_power = stations[i] + window_sum
                if current_power < target:
                    need = target - current_power
                    added[i] = need
                    window_sum += need
                    used_stations += need
                    if used_stations > k:
                        return False
            return True

        low, high = min(stations), max(stations) + k
        while low < high:
            mid = (low + high + 1) // 2
            if is_feasible(mid):
                low = mid
            else:
                high = mid - 1
        return low

The Python code implements the binary search with a sliding window. The is_feasible function checks if a given minimum power can be achieved using at most k additional stations, using a prefix-like sliding window to propagate added station effects efficiently.

Go Solution

func maxPower(stations []int, r int, k int) int64 {
    n := len(stations)
    added := make([]int64, n)

    var isFeasible func(int64) bool
    isFeasible = func(target int64) bool {
        var windowSum, usedStations int64
        for i := 0; i < n; i++ {
            if i > r {
                windowSum -= added[i - r - 1]
            }
            currentPower := int64(stations[i]) + windowSum
            if currentPower < target {
                need := target - currentPower
                added[i] = need
                windowSum += need
                usedStations += need
                if usedStations > int64(k) {
                    return false
                }
            } else {
                added[i] = 0
            }
        }
        return true
    }

    low, high := int64(stations[0]), int64(k)
    for _, val := range stations {
        if int64(val) > high {
            high = int64(val) + int64(k)
        }
    }

    for low < high {
        mid := (low + high + 1) / 2
        // reset added array
        for i := range added {
            added[i] = 0
        }
        if isFeasible(mid) {
            low = mid
        } else {
            high = mid - 1
        }
    }
    return low
}

In Go, slices and int64 are used to handle large numbers safely. The logic mirrors the Python version, with explicit reset of the added slice before each feasibility check.

Worked Examples

Example 1

Input: stations = [1,2,4,5,0], r = 1, k = 2, target minimum power check: 5.

City Original WindowSum Added Effective
0 1 0 4 5
1 2 4 0 6
2 4 4 0 8
3 5 4 0 9
4 0 0 5 5

Minimum power achieved is 5, total added stations = 2 ≤ k, so feasible.

Example 2

Input: stations = [4,4,4,4], r = 0, k = 3, maximum minimum achievable = 4 because each station only affects its city. Adding 3 anywhere cannot raise the minimum above 4.

Complexity Analysis

Measure Complexity Explanation
Time O(n log(max_possible_power)) Binary search on possible power values with O(n) feasibility check
Space O(n) For the added array used in sliding window

The binary search range is bounded by the maximum current power plus k, and each check iterates through n cities, giving the overall complexity.

Test Cases

# Provided examples
assert Solution().maxPower([1,2,4,5,0], 1, 2) == 5  # Example 1
assert Solution().maxPower([4,4,4,4], 0, 3) == 4     # Example 2

# Edge cases
assert Solution().maxPower([0,0,0], 1, 10) == 3      # k > total needed to equalize
assert Solution().maxPower([1,1,1], 1, 0) == 1      # k=0, cannot add
assert Solution().maxPower([100000]*100000, 0, 0) == 100000  # Large n, uniform, r=0

# Single city
assert Solution().maxPower([5], 0, 10) == 15        # Single city, can add all stations

# Increasing range
assert Solution().maxPower([1,2,3,4], 2, 5) >= 5    # r affects multiple cities
Test Why
Example 1 Standard case with small