Maximize the Minimum Powered City
HardUpdated: Aug 2, 2025
Practice on:
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| = 2and|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 themaximum 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.
Examples
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.length1 <= n <= 10^50 <= stations[i] <= 10^50 <= r <= n - 10 <= k <= 10^9
Solution
Method 1 – Binary Search with Sliding Window Greedy
Intuition
To maximize the minimum power of any city, we can use binary search on the answer. For each candidate minimum, we check if it's possible to achieve at least that much power in every city by optimally placing up to k new stations. We use a sliding window to efficiently track the current power in each city and greedily add stations where needed.
Approach
- Use binary search for the answer between 0 and the sum of all stations plus
k. - For each mid value, check if it's possible to achieve at least
midpower in every city:- Use a sliding window to maintain the current power for each city.
- If a city has less than
midpower, add stations at the farthest possible position within range to maximize coverage, and update the window. - Track the number of stations added; if it exceeds
k, it's not possible.
- If possible, try a higher value; otherwise, try lower.
- Return the largest value for which it is possible.
Code
C++
typedef long long ll;
class Solution {
bool isPossible(ll min_power, const vector<ll>& default_powers, int extra_stations, int r, int n) {
vector<ll> extra_power(n+1, 0);
for (int j = 0; j < n; ++j) {
extra_power[j] += (j > 0 ? extra_power[j-1] : 0);
ll cur_power = default_powers[j] + extra_power[j];
ll required = max(0LL, min_power - cur_power);
if (required == 0) continue;
if (required > extra_stations) return false;
extra_stations -= required;
extra_power[j] += required;
extra_power[min(n, j+2*r+1)] -= required;
}
return true;
}
public:
long long maxPower(vector<int>& stations, int r, int k) {
int n = stations.size();
vector<ll> station_powers(n+1, 0);
for (int j = 0; j < n; ++j) {
station_powers[max(0, j-r)] += stations[j];
station_powers[min(n, j+r+1)] -= stations[j];
}
for (int j = 1; j <= n; ++j) station_powers[j] += station_powers[j-1];
ll l = 0, rgt = 1e11;
while (l < rgt) {
ll m = (l + rgt) >> 1;
if (isPossible(m+1, station_powers, k, r, n)) l = m+1;
else rgt = m;
}
return l;
}
};
Go
func maxPower(st []int, r, k int) int64 {
n := len(st)
stationPowers := make([]int64, n+1)
for j, v := range st {
left := max(0, j-r)
right := min(n, j+r+1)
stationPowers[left] += int64(v)
stationPowers[right] -= int64(v)
}
for j := 1; j <= n; j++ {
stationPowers[j] += stationPowers[j-1]
}
isPossible := func(minPower int64) bool {
extraPower := make([]int64, n+1)
extraStations := int64(k)
for j := 0; j < n; j++ {
if j > 0 {
extraPower[j] += extraPower[j-1]
}
curPower := stationPowers[j] + extraPower[j]
required := minPower - curPower
if required <= 0 {
continue
}
if required > extraStations {
return false
}
extraStations -= required
extraPower[j] += required
idx := min(n, j+2*r+1)
extraPower[idx] -= required
}
return true
}
l, rgt := int64(0), int64(1e11)
for l < rgt {
m := (l + rgt) >> 1
if isPossible(m+1) {
l = m + 1
} else {
rgt = m
}
}
return l
}
func min(a, b int) int { if a < b { return a } else { return b } }
func max(a, b int) int { if a > b { return a } else { return b } }
Java
class Solution {
public long maxPower(int[] stations, int r, int k) {
int n = stations.length;
long[] stationPowers = new long[n+1];
for (int j = 0; j < n; ++j) {
stationPowers[Math.max(0, j-r)] += stations[j];
stationPowers[Math.min(n, j+r+1)] -= stations[j];
}
for (int j = 1; j <= n; ++j) stationPowers[j] += stationPowers[j-1];
long l = 0, rgt = (long)1e11;
while (l < rgt) {
long m = (l + rgt) >> 1;
if (isPossible(m+1, stationPowers, k, r, n)) l = m+1;
else rgt = m;
}
return l;
}
private boolean isPossible(long minPower, long[] stationPowers, int k, int r, int n) {
long[] extraPower = new long[n+1];
int extraStations = k;
for (int j = 0; j < n; ++j) {
extraPower[j] += (j > 0 ? extraPower[j-1] : 0);
long curPower = stationPowers[j] + extraPower[j];
long required = Math.max(0, minPower - curPower);
if (required == 0) continue;
if (required > extraStations) return false;
extraStations -= required;
extraPower[j] += required;
int idx = Math.min(n, j+2*r+1);
extraPower[idx] -= required;
}
return true;
}
}
Kotlin
class Solution {
fun maxPower(st: IntArray, r: Int, k: Int): Long {
var l = 0L
var h = st.map { it.toLong() }.sum() + k
var ans = 0L
fun can(minP: Long): Boolean {
val n = st.size
val diff = LongArray(n+1)
var add = 0L
for (i in 0 until n) {
if (i > 0) diff[i] += diff[i-1]
val cur = st[i] + diff[i]
if (cur < minP) {
val need = minP - cur
if (need > k - add) return false
add += need
val idx = minOf(n-1, i + r)
diff[i] += need
if (idx+1 < n) diff[idx+1] -= need
}
}
return true
}
while (l <= h) {
val m = (l + h) / 2
if (can(m)) { ans = m; l = m + 1 } else { h = m - 1 }
}
return ans
}
}
Python
class Solution:
def maxPower(self, stations: list[int], r: int, k: int) -> int:
n = len(stations)
station_powers = [0] * (n+1)
for j, v in enumerate(stations):
left = max(0, j-r)
right = min(n, j+r+1)
station_powers[left] += v
station_powers[right] -= v
for j in range(1, n+1):
station_powers[j] += station_powers[j-1]
def is_possible(min_power: int) -> bool:
extra_power = [0] * (n+1)
extra_stations = k
for j in range(n):
extra_power[j] += extra_power[j-1] if j > 0 else 0
cur_power = station_powers[j] + extra_power[j]
required = max(0, min_power - cur_power)
if required == 0:
continue
if required > extra_stations:
return False
extra_stations -= required
extra_power[j] += required
idx = min(n, j+2*r+1)
extra_power[idx] -= required
return True
l, rgt = 0, int(1e11)
while l < rgt:
m = (l + rgt) >> 1
if is_possible(m+1):
l = m + 1
else:
rgt = m
return l
Rust
impl Solution {
pub fn max_power(stations: Vec<i64>, r: i64, k: i64) -> i64 {
let n = stations.len();
let mut station_powers = vec![0i64; n+1];
for (j, &v) in stations.iter().enumerate() {
let left = std::cmp::max(0, j as i64 - r) as usize;
let right = std::cmp::min(n as i64, j as i64 + r + 1) as usize;
station_powers[left] += v;
station_powers[right] -= v;
}
for j in 1..=n {
station_powers[j] += station_powers[j-1];
}
let is_possible = |min_power: i64| -> bool {
let mut extra_power = vec![0i64; n+1];
let mut extra_stations = k;
for j in 0..n {
if j > 0 { extra_power[j] += extra_power[j-1]; }
let cur_power = station_powers[j] + extra_power[j];
let required = std::cmp::max(0, min_power - cur_power);
if required == 0 { continue; }
if required > extra_stations { return false; }
extra_stations -= required;
extra_power[j] += required;
let idx = std::cmp::min(n, j + 2 * r as usize + 1);
extra_power[idx] -= required;
}
true
};
let mut l = 0i64;
let mut rgt = 1e11 as i64;
while l < rgt {
let m = (l + rgt) >> 1;
if is_possible(m+1) {
l = m + 1;
} else {
rgt = m;
}
}
l
}
}
TypeScript
class Solution {
maxPower(stations: number[], r: number, k: number): number {
const n = stations.length;
const stationPowers = new Array(n+1).fill(0);
for (let j = 0; j < n; ++j) {
const left = Math.max(0, j - r);
const right = Math.min(n, j + r + 1);
stationPowers[left] += stations[j];
stationPowers[right] -= stations[j];
}
for (let j = 1; j <= n; ++j) stationPowers[j] += stationPowers[j-1];
function isPossible(minPower: number): boolean {
const extraPower = new Array(n+1).fill(0);
let extraStations = k;
for (let j = 0; j < n; ++j) {
extraPower[j] += j > 0 ? extraPower[j-1] : 0;
const curPower = stationPowers[j] + extraPower[j];
const required = Math.max(0, minPower - curPower);
if (required === 0) continue;
if (required > extraStations) return false;
extraStations -= required;
extraPower[j] += required;
const idx = Math.min(n, j + 2*r + 1);
extraPower[idx] -= required;
}
return true;
}
let l = 0, rgt = 1e11;
while (l < rgt) {
const m = (l + rgt) >> 1;
if (isPossible(m+1)) l = m + 1;
else rgt = m;
}
return l;
}
}
Complexity
- ⏰ Time complexity:
O(n log X)— where n is the number of cities and X is the search range (up to sum(stations)+k). - 🧺 Space complexity:
O(n)— for the difference array.