Maximize the Minimum Powered City

Hard
1384.

Maximize the Minimum Powered City

Maximize the Minimum Powered City is a hard coding problem on arrays, greedy and binary search, asked in Amazon and Google interviews.

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.length
  • 1 <= n <= 10^5
  • 0 <= stations[i] <= 10^4
  • 0 <= r <= n - 1
  • 0 <= k <= 10^9
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} stations
 * @param {number} r
 * @param {number} k
 * @return {number}
 */
var maxPower = function(stations, r, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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.length
  • 1 <= n <= 10^5
  • 0 <= stations[i] <= 10^4
  • 0 <= r <= n - 1
  • 0 <= k <= 10^9

Hints for Maximize the Minimum Powered City

  1. Hint 1

    Flip it: can every city reach power at least x with at most k new stations? Bigger x only gets harder.

  2. Hint 2

    Sweep cities left to right. When city i is short, any new station must cover it; placing it as far right as possible (city min(n - 1, i + r)) also helps the most future cities.

  3. 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

  1. Compute each city's starting power with prefix sums over the window [i - r, i + r].
  2. feasible(x): sweep i = 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 city p + r).
  3. If city i has power cur < x, add x - cur stations at p = min(n - 1, i + r); fail once the total added exceeds k.
  4. Binary-search x between the current minimum power and that minimum plus k, 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 k by up to x before 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 - 1 every station powers every city, so the answer is simply the total plus k — 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 lo

Java

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