Maximize the Minimum Powered City - Practice Coding Problems

Maximize the Minimum Powered City - Problem

Array Binary Search Greedy Queue Sliding Window Prefix Sum Hard

You are given a 0-indexed integer array stations of length n, where stations[i] represents the number of power stations in the i^th 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: |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.

Input & Output

Example 1 — Basic Case

$ Input: stations = [1,2,4,5,0], r = 1, k = 3

› Output: 5

💡 Note: Initial powers: [3,7,11,9,5]. With k=3 stations optimally placed, we can achieve minimum power of 5 across all cities.

Example 2 — Small Range

$ Input: stations = [4,4,4,4], r = 0, k = 3

› Output: 4

💡 Note: With r=0, each station only powers its own city. We have 3 additional stations to distribute, but can't improve minimum power beyond 4.

Example 3 — Large Range

$ Input: stations = [1,2,4,5,6], r = 2, k = 5

› Output: 11

💡 Note: With r=2, each station covers 5 cities. Strategic placement of 5 additional stations can achieve minimum power of 11.

Constraints

n == stations.length
1 ≤ n ≤ 10⁵
0 ≤ stations[i] ≤ 10⁵
0 ≤ r ≤ n - 1
0 ≤ k ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Cities with stations: [1,2,4,5,0], range r=1, additional k=3

Coverage

Each station covers cities within distance r

Optimization

Place k stations to maximize minimum city power

Key Takeaway

🎯 Key Insight: Binary search the minimum power value, then greedily verify if achievable by placing stations as far right as possible within range

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is to binary search on the answer (minimum power value) and use a greedy strategy to verify if it's achievable. For each candidate minimum power, greedily place additional stations as far right as possible within range when cities fall below the target. Best approach is Binary Search + Greedy with Time: O(n log(sum+k)), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Binary Search on Answer + Greedy Verification	O(n log(sum+k))	O(n)	Binary search the minimum power value, use greedy strategy to check if achievable with k stations
Brute Force - Try All Placements	O(n^k × n × r)	O(k)	Try all possible combinations of placing k stations and find maximum minimum power

Binary Search on Answer + Greedy Verification — Algorithm Steps

Calculate initial power for each city using sliding window
Binary search on minimum power value (0 to sum+k)
For each mid value, greedily place stations and check feasibility

Visualization

Tap to expand

Step-by-Step Walkthrough

Binary Search

Search for maximum achievable minimum power

Greedy Check

For each candidate, place stations greedily

Optimal Result

Find highest feasible minimum power

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef long long ll;

int canAchieve(ll* powers, int r, ll k, int n, ll minPower) {
    ll* additional = (ll*)calloc(n, sizeof(ll));
    ll used = 0;
    ll currentAdditional = 0;
    
    for (int i = 0; i < n; i++) {
        if (i - r - 1 >= 0) {
            currentAdditional -= additional[i - r - 1];
        }
        
        ll currentPower = powers[i] + currentAdditional;
        
        if (currentPower < minPower) {
            ll need = minPower - currentPower;
            int pos = (i + r < n) ? i + r : n - 1;
            additional[pos] += need;
            currentAdditional += need;
            used += need;
            
            if (used > k) {
                free(additional);
                return 0;
            }
        }
    }
    
    free(additional);
    return 1;
}

ll solution(int* stations, int n, int r, ll k) {
    // Calculate initial power for each city
    ll* powers = (ll*)malloc(n * sizeof(ll));
    ll windowSum = 0;
    int end = (r >= n) ? n - 1 : r;
    for (int i = 0; i <= end; i++) {
        windowSum += stations[i];
    }
    powers[0] = windowSum;
    
    for (int i = 1; i < n; i++) {
        if (i + r < n) {
            windowSum += stations[i + r];
        }
        if (i - r - 1 >= 0) {
            windowSum -= stations[i - r - 1];
        }
        powers[i] = windowSum;
    }
    
    ll left = 0, right = 0;
    for (int i = 0; i < n; i++) {
        right += stations[i];
    }
    right += k;
    
    ll result = 0;
    
    while (left <= right) {
        ll mid = (left + right) / 2;
        if (canAchieve(powers, r, k, n, mid)) {
            result = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    free(powers);
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int stations[100000];
    int n = 0;
    char* ptr = strchr(line, '[') + 1;
    char* token = strtok(ptr, ",]");
    while (token != NULL) {
        stations[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int r;
    ll k;
    scanf("%d", &r);
    scanf("%lld", &k);
    
    ll result = solution(stations, n, r, k);
    printf("%lld\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log(sum+k))

Binary search has log(sum+k) iterations, each iteration takes O(n) to verify with greedy placement

⚡ Linearithmic

Space Complexity

O(n)

Arrays to store initial powers and additional stations placed during verification

⚡ Linearithmic Space

15.2K Views

Medium Frequency

~35 min Avg. Time

487 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Binary Search on Answer + Greedy Verification — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler