# Maximize the Minimum Powered City
**Difficulty:** HARD
[External](https://leetcode.com/problems/maximize-the-minimum-powered-city)
Canonical: https://scaleengineer.com/dsa/problems/maximize-the-minimum-powered-city
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window), [Greedy](https://scaleengineer.com/dsa/patterns/greedy), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array, Queue
---
## Problem
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
## Binary Search with Naive Power Calculation in Check Function
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.
**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.
**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.
### Explanation
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:
```java
private boolean check(long targetPower, int[] stations, int r, long k) {
    int n = stations.length;
    long[] currentStations = new long[n];
    for (int i = 0; i < n; i++) {
        currentStations[i] = stations[i];
    }
    long stationsLeft = k;

    for (int i = 0; i < n; i++) {
        // Naively calculate power for city i by summing its window
        long currentPower = 0;
        for (int j = Math.max(0, i - r); j <= Math.min(n - 1, i + r); j++) {
            currentPower += currentStations[j];
        }

        if (currentPower < targetPower) {
            long needed = targetPower - currentPower;
            if (needed > stationsLeft) {
                return false;
            }
            stationsLeft -= needed;
            // Place new stations greedily at the rightmost edge of the range
            int placementCity = Math.min(n - 1, i + r);
            currentStations[placementCity] += needed;
        }
    }
    return true;
}
```
The main function performs binary search calling this `check` function.
### Algorithm
1. Define a search range for the minimum power, from `0` to a safe upper bound like `sum(stations) + k`.
2. 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`.
3. If `check(mid)` is true, we try for a higher power: `ans = mid`, `low = mid + 1`.
4. If `check(mid)` is false, we need a lower power: `high = mid - 1`.
5. Return the final `ans`.

## Binary Search with Efficient O(n) Check
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.
**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.
**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.
### Explanation
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:
```java
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;
}
```
### 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`.
3. If `check(mid)` is true, try for a higher power: `ans = mid`, `low = mid + 1`.
4. If `check(mid)` is false, we need a lower power: `high = mid - 1`.
5. Return the final `ans`.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
class Solution {
public:
  long long maxPower(vector<int> &stations, int r, int k) {
    int n = stations.size();
    long d[n + 1];
    memset(d, 0, sizeof d);
    for (int i = 0; i < n; ++i) {
      int left = max(0, i - r), right = min(i + r, n - 1);
      d[left] += stations[i];
      d[right + 1] -= stations[i];
    }
    long s[n + 1];
    s[0] = d[0];
    for (int i = 1; i < n + 1; ++i) {
      s[i] = s[i - 1] + d[i];
    }
    auto check = [&](long x, int k) {
      memset(d, 0, sizeof d);
      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 = min(i + r, n - 1);
          int left = max(0, j - r), right = min(j + r, n - 1);
          d[left] += dist;
          d[right + 1] -= dist;
          t += dist;
        }
      }
      return true;
    };
    long left = 0, right = 1e12;
    while (left < right) {
      long mid = (left + right + 1) >> 1;
      if (check(mid, k)) {
        left = mid;
      } else {
        right = mid - 1;
      }
    }
    return left;
  }
};

```

### Python

```python
class Solution:
    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

```