Scale Engineer

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 WindowGreedyPrefix Sum
Algorithms
Binary Search
Data structures
ArrayQueue

Prompt

You are given a 0-indexed integer array stations of length n, where stations[i] represents the number of power stations in the ith 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 <= 105
  • 0 <= stations[i] <= 105
  • 0 <= r <= n - 1
  • 0 <= k <= 109

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

  1. Define a search range for the minimum power, from 0 to sum(stations) + k.
  2. 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.
  1. If check(mid) is true, try for a higher power: ans = mid, low = mid + 1.
  2. If check(mid) is false, we need a lower power: high = mid - 1.
  3. Return the final ans.

Walkthrough

The check(targetPower) function is optimized as follows:

  1. 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].
  2. 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).
  3. 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.
  4. 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:

private boolean check(long targetPower, int[] stations, int r, long k) {    int n = stations.length;    long[] prefixSum = new long[n + 1];    for (int i = 0; i < n; i++) {        prefixSum[i + 1] = prefixSum[i] + stations[i];    }     long[] initialPower = new long[n];    for (int i = 0; i < n; i++) {        int left = Math.max(0, i - r);        int right = Math.min(n - 1, i + r);        initialPower[i] = prefixSum[right + 1] - prefixSum[left];    }     long stationsLeft = k;    long[] boostDiff = new long[n + 1];    long currentBoost = 0;     for (int i = 0; i < n; i++) {        currentBoost += boostDiff[i];        long currentTotalPower = initialPower[i] + currentBoost;         if (currentTotalPower < targetPower) {            long needed = targetPower - currentTotalPower;            if (needed > stationsLeft) {                return false;            }            stationsLeft -= needed;            currentBoost += needed;            int endEffectIndex = i + 2 * r + 1;            if (endEffectIndex < n) {                boostDiff[endEffectIndex] -= needed;            }        }    }    return true;}

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.

Solutions

class Solution {private  long[] s;private  long[] d;private  int n;public  long maxPower(int[] stations, int r, int k) {    n = stations.length;    d = new long[n + 1];    s = new long[n + 1];    for (int i = 0; i < n; ++i) {      int left = Math.max(0, i - r), right = Math.min(i + r, n - 1);      d[left] += stations[i];      d[right + 1] -= stations[i];    }    s[0] = d[0];    for (int i = 1; i < n + 1; ++i) {      s[i] = s[i - 1] + d[i];    }    long left = 0, right = 1 l << 40;    while (left < right) {      long mid = (left + right + 1) >>> 1;      if (check(mid, r, k)) {        left = mid;      } else {        right = mid - 1;      }    }    return left;  }private  boolean check(long x, int r, int k) {    Arrays.fill(d, 0);    long t = 0;    for (int i = 0; i < n; ++i) {      t += d[i];      long dist = x - (s[i] + t);      if (dist > 0) {        if (k < dist) {          return false;        }        k -= dist;        int j = Math.min(i + r, n - 1);        int left = Math.max(0, j - r), right = Math.min(j + r, n - 1);        d[left] += dist;        d[right + 1] -= dist;        t += dist;      }    }    return true;  }}

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 →

Next problem