Maximize the Minimum Powered City — Problem & Solution
Maximize the Minimum Powered City solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Maximize the Minimum Powered City is a hard coding problem on arrays, greedy and binary search, asked in Amazon and Google interviews.
- Difficulty: Hard
- Topics: Arrays, Greedy, Binary Search, Prefix Sum
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
n cities stand in a row; stations[i] is the number of power stations in city i. A station in city j supplies every city i with |i - j| <= r. The power of a city is the number of stations that supply it.
The grid operator may build k more stations, each in any city (several may go in the same city). Return the largest possible value of the minimum power over all cities after building them optimally.
CodeKairo bounds: the original allows stations[i] up to 10^5, which needs a 64-bit answer. Here stations[i] <= 10^4, so every city's power plus k stays within a 32-bit integer.
Example 1
Input: stations = [1,2,4,5,0], r = 1, k = 2
Output: 5
Explanation: Powers start as 3, 7, 11, 9, 5; two stations in city 1 lift them to 5, 9, 13, 9, 5.
Example 2
Input: stations = [4,4,4,4], r = 0, k = 3
Output: 4
Explanation: Each city only powers itself, and three stations cannot raise all four.
Example 3
Input: stations = [0,0,0], r = 2, k = 7
Output: 7
Constraints
n == stations.length1 <= n <= 10^50 <= stations[i] <= 10^40 <= r <= n - 10 <= k <= 10^9
Hints for Maximize the Minimum Powered City
Hint 1
Flip it: can every city reach power at least
xwith at mostknew stations? Biggerxonly gets harder.Hint 2
Sweep cities left to right. When city
iis short, any new station must cover it; placing it as far right as possible (citymin(n - 1, i + r)) also helps the most future cities.Hint 3
Track the effect of the stations you add with a difference array (or a sliding window) so the sweep stays linear; binary-search the largest feasible
x.
How to solve Maximize the Minimum Powered City
Binary search the answer x. Feasibility is a greedy sweep: walk the cities in order and, whenever one falls short of x, build exactly the missing stations at the rightmost city that still reaches it.
Approach
- Compute each city's starting power with prefix sums over the window
[i - r, i + r]. feasible(x): sweepi = 0..n-1, keeping the extra power contributed by stations already added (a running sum plus a difference array that removes a station's effect after cityp + r).- If city
ihas powercur < x, addx - curstations atp = min(n - 1, i + r); fail once the total added exceedsk. - Binary-search
xbetween the current minimum power and that minimum plusk, keeping the largest feasible value.
Why it works
When the sweep reaches the first short city, cities to its left are already satisfied, so a new station only needs to help this city and the ones after it. Among the positions that reach city i, the rightmost one covers a superset of the future cities any other would cover — so it is never worse, and the minimum number of stations is forced. The predicate is monotone in x, so the binary search returns the optimum.
Complexity
- Time —
O(n log k) - Space —
O(n)
Pitfalls
- Use 64-bit counters inside the check: the stations requested can exceed
kby up toxbefore you bail out. - Get the starting powers from prefix sums (or a sliding window); recomputing every window from scratch costs O(n · r) per check.
- With
r = n - 1every station powers every city, so the answer is simply the total plusk— a good sanity check.
Reference solution
Python
from typing import List
def maxPower(stations: List[int], r: int, k: int) -> int:
n = len(stations)
pre = [0] * (n + 1)
for i in range(n):
pre[i + 1] = pre[i] + stations[i]
base = [pre[min(n - 1, i + r) + 1] - pre[max(0, i - r)] for i in range(n)]
def feasible(x):
expire = [0] * (n + 1)
running = 0
used = 0
for i in range(n):
running -= expire[i]
cur = base[i] + running
if cur < x:
need = x - cur
used += need
if used > k:
return False
running += need
stop = min(n - 1, i + r) + r + 1
if stop < n:
expire[stop] += need
return True
lo = min(base)
hi = lo + k
while lo < hi:
mid = (lo + hi + 1) // 2
if feasible(mid):
lo = mid
else:
hi = mid - 1
return loJava
public static int maxPower(int[] stations, int r, int k) {
int n = stations.length;
long[] pre = new long[n + 1];
for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + stations[i];
long[] base = new long[n];
long low = Long.MAX_VALUE;
for (int i = 0; i < n; i++) {
base[i] = pre[Math.min(n - 1, i + r) + 1] - pre[Math.max(0, i - r)];
low = Math.min(low, base[i]);
}
long lo = low, hi = low + k;
while (lo < hi) {
long mid = lo + (hi - lo + 1) / 2;
if (canReach(base, r, k, mid)) lo = mid; else hi = mid - 1;
}
return (int) lo;
}
static boolean canReach(long[] base, int r, long k, long x) {
int n = base.length;
long[] expire = new long[n + 1];
long running = 0, used = 0;
for (int i = 0; i < n; i++) {
running -= expire[i];
long cur = base[i] + running;
if (cur < x) {
long need = x - cur;
used += need;
if (used > k) return false;
running += need;
long stop = (long) Math.min(n - 1, i + r) + r + 1;
if (stop < n) expire[(int) stop] += need;
}
}
return true;
}C++
bool canReachPower(const vector<long long>& base, int r, long long k, long long x) {
int n = base.size();
vector<long long> expire(n + 1, 0);
long long running = 0, used = 0;
for (int i = 0; i < n; i++) {
running -= expire[i];
long long cur = base[i] + running;
if (cur < x) {
long long need = x - cur;
used += need;
if (used > k) return false;
running += need;
long long stop = (long long)min(n - 1, i + r) + r + 1;
if (stop < n) expire[stop] += need;
}
}
return true;
}
int maxPower(vector<int>& stations, int r, int k) {
int n = stations.size();
vector<long long> pre(n + 1, 0);
for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + stations[i];
vector<long long> base(n);
long long low = LLONG_MAX;
for (int i = 0; i < n; i++) {
base[i] = pre[min(n - 1, i + r) + 1] - pre[max(0, i - r)];
low = min(low, base[i]);
}
long long lo = low, hi = low + k;
while (lo < hi) {
long long mid = lo + (hi - lo + 1) / 2;
if (canReachPower(base, r, k, mid)) lo = mid; else hi = mid - 1;
}
return (int)lo;
}JavaScript
var maxPower = function(stations, r, k) {
var n = stations.length;
var pre = [0];
for (var i = 0; i < n; i++) pre.push(pre[i] + stations[i]);
var base = [];
var low = Infinity;
for (var c = 0; c < n; c++) {
var p = pre[Math.min(n - 1, c + r) + 1] - pre[Math.max(0, c - r)];
base.push(p);
if (p < low) low = p;
}
var feasible = function(x) {
var expire = new Array(n + 1).fill(0);
var running = 0, used = 0;
for (var i = 0; i < n; i++) {
running -= expire[i];
var cur = base[i] + running;
if (cur < x) {
var need = x - cur;
used += need;
if (used > k) return false;
running += need;
var stop = Math.min(n - 1, i + r) + r + 1;
if (stop < n) expire[stop] += need;
}
}
return true;
};
var lo = low, hi = low + k;
while (lo < hi) {
var mid = lo + Math.floor((hi - lo + 1) / 2);
if (feasible(mid)) lo = mid; else hi = mid - 1;
}
return lo;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Greedy Algorithms