Maximize the Minimum Powered City

Hard

#2308Time: O(n * log(S)) where `n` is the number of cities and `S` is the search space size. The `check` function is optimized to O(n) using prefix sums and a difference array. The binary search contributes the `log(S)` factor.Space: O(n) to store the prefix sum array, the initial power array, and the difference array for the boost.

Patterns

Sliding Window Greedy Prefix Sum

Algorithms

Binary Search

Data structures

Array Queue

Prompt

You are given a 0-indexed integer array stations of length n, where stations[i] represents the number of power stations in the i^th city.

Each power station can provide power to every city in a fixed range. In other words, if the range is denoted by r, then a power station at city i can provide power to all cities j such that |i - j| <= r and 0 <= i, j <= n - 1.

Note that |x| denotes absolute value. For example, |7 - 5| = 2 and |3 - 10| = 7.

The power of a city is the total number of power stations it is being provided power from.

The government has sanctioned building k more power stations, each of which can be built in any city, and have the same range as the pre-existing ones.

Given the two integers r and k, return the maximum possible minimum power of a city, if the additional power stations are built optimally.

Note that you can build the k power stations in multiple cities.

Example 1:

Input: stations = [1,2,4,5,0], r = 1, k = 2
Output: 5
Explanation: 
One of the optimal ways is to install both the power stations at city 1. 
So stations will become [1,4,4,5,0].
- City 0 is provided by 1 + 4 = 5 power stations.
- City 1 is provided by 1 + 4 + 4 = 9 power stations.
- City 2 is provided by 4 + 4 + 5 = 13 power stations.
- City 3 is provided by 5 + 4 = 9 power stations.
- City 4 is provided by 5 + 0 = 5 power stations.
So the minimum power of a city is 5.
Since it is not possible to obtain a larger power, we return 5.

Example 2:

Input: stations = [4,4,4,4], r = 0, k = 3
Output: 4
Explanation: 
It can be proved that we cannot make the minimum power of a city greater than 4.

Constraints:

n == stations.length
1 <= n <= 10⁵
0 <= stations[i] <= 10⁵
0 <= r <= n - 1
0 <= k <= 10⁹

Approaches

2 approaches with complexity analysis and trade-offs.

This is the optimal approach, building upon the binary search framework. The key improvement is optimizing the check(x) function to run in linear time, O(n). This is achieved by avoiding the repeated power calculations. We first pre-calculate the initial power of every city. Then, as we iterate through the cities and add new stations, we use a difference array (or a similar sliding window technique) to efficiently track the additional power (boost) these new stations provide to subsequent cities.

Algorithm

Define a search range for the minimum power, from 0 to sum(stations) + k.
Perform binary search on this range. For each mid value:

Call an efficient check(mid) function.
The check(targetPower) function works as follows:
1. In O(n), pre-calculate initialPower[i] for all i using a prefix sum array on stations.
2. Initialize a difference array boostDiff of size n+1 to all zeros.
3. Initialize stationsLeft = k and currentBoost = 0.
4. Iterate through each city i from 0 to n-1: a. Update the power from new stations: currentBoost += boostDiff[i]. b. Calculate total power: totalPower = initialPower[i] + currentBoost. c. If totalPower < targetPower, calculate needed stations. d. If needed > stationsLeft, return false. e. Decrement stationsLeft by needed. f. Increase currentBoost by needed as these new stations help city i immediately. g. Schedule the boost to be removed after its effect ends. The stations added for city i cover up to city i+2r. So, boostDiff[i+2r+1] -= needed (with bounds check).
5. If the loop completes, return true.

If check(mid) is true, try for a higher power: ans = mid, low = mid + 1.
If check(mid) is false, we need a lower power: high = mid - 1.
Return the final ans.

Walkthrough

The check(targetPower) function is optimized as follows:

Pre-computation: Calculate the initial power of every city based on the original stations array. This can be done in O(n) time using a prefix sum array. initialPower[i] = sum(stations[j]) for j in [i-r, i+r].
Greedy Iteration with Efficient Updates: We iterate through cities from i = 0 to n-1. We maintain a variable currentBoost which represents the extra power city i receives from all the new stations added for previous cities (j < i).
When we add needed stations for city i, they are placed at i+r and provide power to cities in the range [i, i+2r]. This means the currentBoost increases by needed starting from city i. This boost effect stops after city i+2r. We can model this efficiently using a difference array, boostDiff. When we add needed stations for city i, we've already added needed to currentBoost. To stop this effect later, we schedule a subtraction: boostDiff[i + 2*r + 1] -= needed.
At each city i, we update currentBoost by adding boostDiff[i]. The total power is then initialPower[i] + currentBoost. If this is less than targetPower, we add new stations and update our data structures as described.

Here is the efficient check function implementation:

1private boolean check(long targetPower, int[] stations, int r, long k) {2    int n = stations.length;3    long[] prefixSum = new long[n + 1];4    for (int i = 0; i < n; i++) {5        prefixSum[i + 1] = prefixSum[i] + stations[i];6    }7 8    long[] initialPower = new long[n];9    for (int i = 0; i < n; i++) {10        int left = Math.max(0, i - r);11        int right = Math.min(n - 1, i + r);12        initialPower[i] = prefixSum[right + 1] - prefixSum[left];13    }14 15    long stationsLeft = k;16    long[] boostDiff = new long[n + 1];17    long currentBoost = 0;18 19    for (int i = 0; i < n; i++) {20        currentBoost += boostDiff[i];21        long currentTotalPower = initialPower[i] + currentBoost;22 23        if (currentTotalPower < targetPower) {24            long needed = targetPower - currentTotalPower;25            if (needed > stationsLeft) {26                return false;27            }28            stationsLeft -= needed;29            currentBoost += needed;30            int endEffectIndex = i + 2 * r + 1;31            if (endEffectIndex < n) {32                boostDiff[endEffectIndex] -= needed;33            }34        }35    }36    return true;37}

Complexity

Time

O(n * log(S)) where `n` is the number of cities and `S` is the search space size. The `check` function is optimized to O(n) using prefix sums and a difference array. The binary search contributes the `log(S)` factor.

Space

O(n) to store the prefix sum array, the initial power array, and the difference array for the boost.

Trade-offs

Pros

Highly efficient and meets the time constraints of the problem.
It's the standard and optimal way to solve this category of problems.

Cons

The logic for the check function, especially the use of the difference array to track power boosts, is more complex to understand and implement correctly.

This approach identifies that the problem is a 'maximize the minimum' type, which is a classic signal for binary searching on the answer. We can binary search for the maximum possible minimum power. For each candidate minimum power x, we need a function check(x) that determines if it's possible to make every city's power at least x using at most k additional stations.

Algorithm

Define a search range for the minimum power, from 0 to a safe upper bound like sum(stations) + k.
Perform binary search on this range. For each mid value:

Call a check(mid) function to see if a minimum power of mid is achievable.
The check(targetPower) function works as follows:
1. Create a mutable copy of the stations array, say currentStations.
2. Initialize stationsUsed = 0.
3. Iterate through each city i from 0 to n-1: a. Calculate the power of city i by summing currentStations[j] for j in [max(0, i-r), min(n-1, i+r)]. b. If the calculated power is less than targetPower, calculate the needed stations. c. If needed exceeds the remaining k, it's impossible, so return false. d. Add needed stations to currentStations[min(n-1, i+r)] and decrement the remaining k.
4. If the loop completes, it's possible, so return true.

If check(mid) is true, we try for a higher power: ans = mid, low = mid + 1.
If check(mid) is false, we need a lower power: high = mid - 1.
Return the final ans.

Walkthrough

The core of this method is the check(targetPower) function. It simulates the process of adding stations greedily. We iterate through the cities from left to right. For each city, we calculate its current power. If it's below targetPower, we must add new stations. The optimal greedy strategy is to place these new stations as far to the right as possible while still covering the current city. This position is i + r. This helps cover the maximum number of subsequent cities.

In this specific approach, the calculation of each city's power is done naively. For each city i, we iterate through its range [i-r, i+r] and sum up the stations (including any newly added ones) to find its power. This leads to a less efficient check function.

Here is the check function implementation:

1private boolean check(long targetPower, int[] stations, int r, long k) {2    int n = stations.length;3    long[] currentStations = new long[n];4    for (int i = 0; i < n; i++) {5        currentStations[i] = stations[i];6    }7    long stationsLeft = k;8 9    for (int i = 0; i < n; i++) {10        // Naively calculate power for city i by summing its window11        long currentPower = 0;12        for (int j = Math.max(0, i - r); j <= Math.min(n - 1, i + r); j++) {13            currentPower += currentStations[j];14        }15 16        if (currentPower < targetPower) {17            long needed = targetPower - currentPower;18            if (needed > stationsLeft) {19                return false;20            }21            stationsLeft -= needed;22            // Place new stations greedily at the rightmost edge of the range23            int placementCity = Math.min(n - 1, i + r);24            currentStations[placementCity] += needed;25        }26    }27    return true;28}

The main function performs binary search calling this check function.

Complexity

Time

O(n * r * log(S)) where `n` is the number of cities, `r` is the range, and `S` is the size of the search space for the answer (from 0 to `sum(stations) + k`). The `check` function takes O(n * r) because for each of the `n` cities, it iterates up to `2r+1` other cities to calculate power. The binary search contributes the `log(S)` factor.

Space

O(n) to store the copy of the `stations` array within the `check` function.

Trade-offs

Pros

The logic for the check function is straightforward and easier to understand.

Cons

This approach is too slow for the given constraints on n and r, and will likely result in a Time Limit Exceeded error.

Solutions

Solution

1class Solution {2private3  long[] s;4private5  long[] d;6private7  int n;8public9  long maxPower(int[] stations, int r, int k) {10    n = stations.length;11    d = new long[n + 1];12    s = new long[n + 1];13    for (int i = 0; i < n; ++i) {14      int left = Math.max(0, i - r), right = Math.min(i + r, n - 1);15      d[left] += stations[i];16      d[right + 1] -= stations[i];17    }18    s[0] = d[0];19    for (int i = 1; i < n + 1; ++i) {20      s[i] = s[i - 1] + d[i];21    }22    long left = 0, right = 1 l << 40;23    while (left < right) {24      long mid = (left + right + 1) >>> 1;25      if (check(mid, r, k)) {26        left = mid;27      } else {28        right = mid - 1;29      }30    }31    return left;32  }33private34  boolean check(long x, int r, int k) {35    Arrays.fill(d, 0);36    long t = 0;37    for (int i = 0; i < n; ++i) {38      t += d[i];39      long dist = x - (s[i] + t);40      if (dist > 0) {41        if (k < dist) {42          return false;43        }44        k -= dist;45        int j = Math.min(i + r, n - 1);46        int left = Math.max(0, j - r), right = Math.min(j + r, n - 1);47        d[left] += dist;48        d[right + 1] -= dist;49        t += dist;50      }51    }52    return true;53  }54}

1class Solution {2public:3  long long maxPower(vector<int> &stations, int r, int k) {4    int n = stations.size();5    long d[n + 1];6    memset(d, 0, sizeof d);7    for (int i = 0; i < n; ++i) {8      int left = max(0, i - r), right = min(i + r, n - 1);9      d[left] += stations[i];10      d[right + 1] -= stations[i];11    }12    long s[n + 1];13    s[0] = d[0];14    for (int i = 1; i < n + 1; ++i) {15      s[i] = s[i - 1] + d[i];16    }17    auto check = [&](long x, int k) {18      memset(d, 0, sizeof d);19      long t = 0;20      for (int i = 0; i < n; ++i) {21        t += d[i];22        long dist = x - (s[i] + t);23        if (dist > 0) {24          if (k < dist) {25            return false;26          }27          k -= dist;28          int j = min(i + r, n - 1);29          int left = max(0, j - r), right = min(j + r, n - 1);30          d[left] += dist;31          d[right + 1] -= dist;32          t += dist;33        }34      }35      return true;36    };37    long left = 0, right = 1e12;38    while (left < right) {39      long mid = (left + right + 1) >> 1;40      if (check(mid, k)) {41        left = mid;42      } else {43        right = mid - 1;44      }45    }46    return left;47  }48};

1class Solution:2    def maxPower(self, stations: List[int], r: int, k: int) -> int: def check(x, k): d = [0] * (n + 1) t = 0 for i in range(n): t += d[i] dist = x - (s[i] + t) if dist > 0: if k < dist: return False k -= dist j = min(i + r, n - 1) left, right = max(0, j - r), min(j + r, n - 1) d[left] += dist d[right + 1] -= dist t += dist return True n = len(stations) d = [0] * (n + 1) for i, v in enumerate(stations): left, right = max(0, i - r), min(i + r, n - 1) d[left] += v d[right + 1] -= v s = list(accumulate(d)) left, right = 0, 1 << 40 while left < right: mid = (left + right + 1) >> 1 if check(mid, k): left = mid else: right = mid - 1 return left

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem