2528. Maximize the Minimum Powered City

HardGreedyQueueArrayBinary SearchPrefix SumSliding Window

Problem Description

You have n cities arranged in a line (indexed from 0 to n-1), and each city has some number of power stations given by the array stations, where stations[i] represents the number of power stations in city i.

Each power station can provide power to cities within a fixed range r. Specifically, a power station located in city i can provide power to all cities j where |i - j| <= r. The power of a city is defined as the total number of power stations that can provide power to it.

The government wants to build k additional power stations. Each new power station:

Can be built in any city
Has the same range r as existing power stations
Multiple power stations can be built in the same city

Your task is to find the maximum possible minimum power among all cities after optimally placing the k additional power stations.

In other words, you want to maximize the power of the weakest city by strategically placing the new power stations.

Example:

If you have cities with initial power values and you can add k stations, you want to place them such that the city with the least power has as much power as possible.
The goal is to maximize the minimum value across all cities.

Constraints:

The range r determines how far a power station's influence extends
You have exactly k new power stations to place
You need to return the highest achievable minimum power level among all cities

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

The key insight is that we're trying to maximize the minimum power across all cities. This is a classic "maximize the minimum" optimization problem, which naturally leads us to think about binary search.

Why binary search? Consider this: if we can achieve a minimum power of x across all cities with k additional stations, then we can definitely achieve any minimum power less than x. Conversely, if we cannot achieve a minimum power of x, then we cannot achieve any value greater than x either. This monotonic property makes binary search the perfect tool.

The next question is: given a target minimum power x, how do we check if it's achievable with k additional stations?

We can use a greedy approach. As we traverse each city from left to right:

If a city's current power is less than x, we need to add power stations
Where should we place them? Since we're going left to right, we want to place new stations as far right as possible while still covering the current city. This way, each new station can potentially help future cities too
The optimal position is at min(i + r, n - 1) - as far right as we can go while still covering city i

To efficiently track how many power stations affect each city, we use a difference array technique. This allows us to:

Initially compute how many existing stations cover each city using range updates
During our check, efficiently add new stations and update the power coverage for multiple cities at once

The difference array is powerful here because adding a power station at position j affects all cities in the range [j - r, j + r]. Instead of updating each city individually, we can mark the start and end of this range in the difference array, then use prefix sums to get the actual values.

The combination of binary search (to find the optimal minimum power) + greedy placement (to minimize stations needed) + difference arrays (for efficient range updates) gives us an elegant solution to this complex optimization problem.

Learn more about Greedy, Queue, Binary Search, Prefix Sum and Sliding Window patterns.

Solution Implementation

1class Solution: 2 def maxPower(self, stations: List[int], r: int, k: int) -> int: 3 def can_achieve_min_power(target_min_power: int, available_stations: int) -> bool: 4 """ 5 Check if we can achieve at least target_min_power for all cities 6 using at most available_stations additional power stations. 7 8 Uses a greedy approach: place new stations as far right as possible 9 when a city needs more power. 10 """ 11 # Track power additions using difference array 12 power_additions = [0] * (num_cities + 1) 13 current_added_power = 0 14 15 for city_idx in range(num_cities): 16 # Update current added power based on difference array 17 current_added_power += power_additions[city_idx] 18 19 # Calculate power deficit for current city 20 current_city_power = initial_power[city_idx] + current_added_power 21 power_deficit = target_min_power - current_city_power 22 23 if power_deficit > 0: 24 # Check if we have enough stations to cover the deficit 25 if available_stations < power_deficit: 26 return False 27 28 # Greedily place new stations as far right as possible 29 # while still covering the current city 30 available_stations -= power_deficit 31 32 # Find the rightmost position to place new stations 33 rightmost_position = min(city_idx + r, num_cities - 1) 34 35 # Calculate the range affected by stations at rightmost_position 36 affected_start = max(0, rightmost_position - r) 37 affected_end = min(rightmost_position + r, num_cities - 1) 38 39 # Update difference array to add power to affected range 40 power_additions[affected_start] += power_deficit 41 power_additions[affected_end + 1] -= power_deficit 42 43 # Update current added power for this city 44 current_added_power += power_deficit 45 46 return True 47 48 num_cities = len(stations) 49 50 # Calculate initial power for each city using difference array technique 51 # Each station affects cities within range r 52 power_diff = [0] * (num_cities + 1) 53 54 for station_idx, station_power in enumerate(stations): 55 # Calculate the range of cities affected by this station 56 left_bound = max(0, station_idx - r) 57 right_bound = min(station_idx + r, num_cities - 1) 58 59 # Update difference array 60 power_diff[left_bound] += station_power 61 power_diff[right_bound + 1] -= station_power 62 63 # Convert difference array to actual power values using prefix sum 64 initial_power = list(accumulate(power_diff)) 65 66 # Binary search for the maximum achievable minimum power 67 left, right = 0, 1 << 40 # Upper bound is 2^40 (large enough for the problem) 68 69 while left < right: 70 # Use upper mid to maximize the result 71 mid = (left + right + 1) >> 1 72 73 if can_achieve_min_power(mid, k): 74 # Can achieve mid, try for higher minimum power 75 left = mid 76 else: 77 # Cannot achieve mid, try lower values 78 right = mid - 1 79 80 return left 81

1class Solution { 2 private long[] prefixSum; // Prefix sum array for power stations 3 private long[] differenceArray; // Difference array for range updates 4 private int cityCount; // Total number of cities 5 6 public long maxPower(int[] stations, int r, int k) { 7 cityCount = stations.length; 8 differenceArray = new long[cityCount + 1]; 9 prefixSum = new long[cityCount + 1]; 10 11 // Convert initial stations to difference array for range coverage 12 // Each station at position i covers cities from [i-r, i+r] 13 for (int i = 0; i < cityCount; ++i) { 14 int rangeStart = Math.max(0, i - r); 15 int rangeEnd = Math.min(i + r, cityCount - 1); 16 differenceArray[rangeStart] += stations[i]; 17 differenceArray[rangeEnd + 1] -= stations[i]; 18 } 19 20 // Build prefix sum from difference array to get actual power at each city 21 prefixSum[0] = differenceArray[0]; 22 for (int i = 1; i < cityCount + 1; ++i) { 23 prefixSum[i] = prefixSum[i - 1] + differenceArray[i]; 24 } 25 26 // Binary search for the maximum minimum power 27 long left = 0; 28 long right = 1L << 40; // Upper bound for binary search 29 30 while (left < right) { 31 long mid = (left + right + 1) >>> 1; // Avoid overflow with unsigned right shift 32 if (canAchieveMinPower(mid, r, k)) { 33 left = mid; // Can achieve this minimum, try higher 34 } else { 35 right = mid - 1; // Cannot achieve, try lower 36 } 37 } 38 39 return left; 40 } 41 42 /** 43 * Check if we can achieve minimum power of targetMinPower for all cities 44 * @param targetMinPower The target minimum power for all cities 45 * @param range The range that each station can cover 46 * @param additionalStations The number of additional stations we can build 47 * @return true if achievable, false otherwise 48 */ 49 private boolean canAchieveMinPower(long targetMinPower, int range, int additionalStations) { 50 // Reset difference array for tracking additional stations 51 Arrays.fill(differenceArray, 0); 52 long additionalPower = 0; // Running sum of additional power from new stations 53 54 // Greedily place stations from left to right 55 for (int i = 0; i < cityCount; ++i) { 56 additionalPower += differenceArray[i]; 57 long currentPower = prefixSum[i] + additionalPower; 58 long powerDeficit = targetMinPower - currentPower; 59 60 if (powerDeficit > 0) { 61 // Need to add stations to meet the target 62 if (additionalStations < powerDeficit) { 63 return false; // Not enough stations available 64 } 65 66 additionalStations -= powerDeficit; 67 68 // Place new stations as far right as possible while still covering city i 69 int optimalPosition = Math.min(i + range, cityCount - 1); 70 int coverageStart = Math.max(0, optimalPosition - range); 71 int coverageEnd = Math.min(optimalPosition + range, cityCount - 1); 72 73 // Update difference array for the new stations' coverage 74 differenceArray[coverageStart] += powerDeficit; 75 differenceArray[coverageEnd + 1] -= powerDeficit; 76 additionalPower += powerDeficit; 77 } 78 } 79 80 return true; 81 } 82} 83

1class Solution { 2public: 3 long long maxPower(vector<int>& stations, int r, int k) { 4 int n = stations.size(); 5 6 // Step 1: Calculate initial power coverage using difference array technique 7 // diff[i] represents the change in power at position i 8 long diff[n + 1]; 9 memset(diff, 0, sizeof diff); 10 11 // For each station, add its contribution to all cities in its range 12 for (int i = 0; i < n; ++i) { 13 int leftBound = max(0, i - r); 14 int rightBound = min(i + r, n - 1); 15 diff[leftBound] += stations[i]; 16 diff[rightBound + 1] -= stations[i]; 17 } 18 19 // Step 2: Build prefix sum array to get actual power at each city 20 long prefixPower[n + 1]; 21 prefixPower[0] = diff[0]; 22 for (int i = 1; i < n + 1; ++i) { 23 prefixPower[i] = prefixPower[i - 1] + diff[i]; 24 } 25 26 // Step 3: Binary search helper - check if minimum power targetPower is achievable 27 auto canAchieveMinPower = [&](long targetPower, int availableStations) { 28 // Use difference array to track additional stations placed 29 long additionalDiff[n + 1]; 30 memset(additionalDiff, 0, sizeof additionalDiff); 31 long additionalPower = 0; 32 33 // Check each city from left to right 34 for (int i = 0; i < n; ++i) { 35 // Update additional power from previously placed stations 36 additionalPower += additionalDiff[i]; 37 38 // Calculate power deficit at current city 39 long currentPower = prefixPower[i] + additionalPower; 40 long deficit = targetPower - currentPower; 41 42 if (deficit > 0) { 43 // Need to place stations to cover deficit 44 if (availableStations < deficit) { 45 return false; // Not enough stations available 46 } 47 48 // Place stations at the rightmost position that can cover city i 49 // This greedy placement maximizes coverage for future cities 50 availableStations -= deficit; 51 int placementPos = min(i + r, n - 1); 52 int coverageLeft = max(0, placementPos - r); 53 int coverageRight = min(placementPos + r, n - 1); 54 55 // Update difference array for the new stations' coverage 56 additionalDiff[coverageLeft] += deficit; 57 additionalDiff[coverageRight + 1] -= deficit; 58 additionalPower += deficit; 59 } 60 } 61 return true; 62 }; 63 64 // Step 4: Binary search for maximum achievable minimum power 65 long left = 0; 66 long right = 1e12; // Upper bound for power value 67 68 while (left < right) { 69 long mid = (left + right + 1) >> 1; // Ceiling division to avoid infinite loop 70 71 if (canAchieveMinPower(mid, k)) { 72 left = mid; // Can achieve mid, try for higher 73 } else { 74 right = mid - 1; // Cannot achieve mid, try lower 75 } 76 } 77 78 return left; 79 } 80}; 81

1/** 2 * Finds the maximum minimum power among all cities after optimally placing k additional power stations 3 * @param stations - Array where stations[i] is the number of power stations at city i 4 * @param r - Range of power stations (a station at city i can provide power to cities from i-r to i+r) 5 * @param k - Number of additional power stations that can be placed 6 * @returns The maximum possible minimum power among all cities 7 */ 8function maxPower(stations: number[], r: number, k: number): number { 9 const n = stations.length; 10 11 // Difference array for tracking power increments/decrements 12 const powerDifference: bigint[] = new Array(n + 1).fill(0n); 13 14 // Array to store the cumulative power at each city 15 const cumulativePower: bigint[] = new Array(n + 1).fill(0n); 16 17 // Initialize the difference array based on existing stations 18 // Each station at position i provides power to cities in range [i-r, i+r] 19 for (let i = 0; i < n; ++i) { 20 const leftBound = Math.max(0, i - r); 21 const rightBound = Math.min(i + r, n - 1); 22 powerDifference[leftBound] += BigInt(stations[i]); 23 powerDifference[rightBound + 1] -= BigInt(stations[i]); 24 } 25 26 // Build cumulative power array using prefix sum of difference array 27 cumulativePower[0] = powerDifference[0]; 28 for (let i = 1; i < n + 1; ++i) { 29 cumulativePower[i] = cumulativePower[i - 1] + powerDifference[i]; 30 } 31 32 /** 33 * Checks if it's possible to achieve minimum power of targetPower for all cities 34 * using at most additionalStations new stations 35 * @param targetPower - The target minimum power level to achieve 36 * @param additionalStations - Number of additional stations available 37 * @returns true if achievable, false otherwise 38 */ 39 function canAchieveMinPower(targetPower: bigint, additionalStations: bigint): boolean { 40 // Temporary difference array for tracking new station placements 41 const tempDifference: bigint[] = new Array(n + 1).fill(0n); 42 43 // Running sum of additional power from newly placed stations 44 let additionalPower = 0n; 45 46 // Greedily place new stations from left to right 47 for (let cityIndex = 0; cityIndex < n; ++cityIndex) { 48 // Update additional power at current city 49 additionalPower += tempDifference[cityIndex]; 50 51 // Calculate power deficit at current city 52 const powerDeficit = targetPower - (cumulativePower[cityIndex] + additionalPower); 53 54 if (powerDeficit > 0) { 55 // Need to place new stations to meet the target 56 if (additionalStations < powerDeficit) { 57 // Not enough stations available 58 return false; 59 } 60 61 // Place stations at the rightmost position that covers current city 62 // This maximizes coverage for future cities 63 additionalStations -= powerDeficit; 64 65 // Find the optimal position to place new stations 66 const optimalPosition = Math.min(cityIndex + r, n - 1); 67 const coverageLeft = Math.max(0, optimalPosition - r); 68 const coverageRight = Math.min(optimalPosition + r, n - 1); 69 70 // Update difference array for the new stations' coverage 71 tempDifference[coverageLeft] += powerDeficit; 72 tempDifference[coverageRight + 1] -= powerDeficit; 73 74 // Update running sum of additional power 75 additionalPower += powerDeficit; 76 } 77 } 78 79 return true; 80 } 81 82 // Binary search for the maximum achievable minimum power 83 let searchLeft = 0n; 84 let searchRight = 1n << 40n; // Upper bound for search range 85 86 while (searchLeft < searchRight) { 87 // Use upper mid to find the maximum valid value 88 const mid = (searchLeft + searchRight + 1n) >> 1n; 89 90 if (canAchieveMinPower(mid, BigInt(k))) { 91 // Can achieve this minimum power, try for higher 92 searchLeft = mid; 93 } else { 94 // Cannot achieve this minimum power, search lower values 95 searchRight = mid - 1n; 96 } 97 } 98 99 return Number(searchLeft); 100} 101

Solution Approach

The solution consists of two main parts: binary search for the answer and a greedy check function with difference arrays.

Step 1: Initial Power Calculation Using Difference Arrays

First, we need to calculate how many power stations initially cover each city. We use a difference array d to efficiently handle range updates:

For each station at position i with v stations, it affects cities in range [max(0, i - r), min(i + r, n - 1)]
We add v at the start of the range and subtract v at position right + 1
After processing all stations, we use prefix sum (accumulate) to get the actual power for each city in array s

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))

Step 2: Binary Search Setup

We search for the maximum achievable minimum power:

Left boundary: 0 (minimum possible power)
Right boundary: 1 << 40 (a sufficiently large value)
We use binary search to find the largest value x such that we can make all cities have at least x power using at most k additional stations

left, right = 0, 1 << 40 while left < right:  mid = (left + right + 1) >> 1  if check(mid, k):  left = mid  else:  right = mid - 1

Step 3: The Check Function - Greedy Placement with Difference Arrays

The check(x, k) function determines if we can achieve minimum power x for all cities:

Initialize a new difference array d to track additional power stations we place
Maintain a running sum t to track cumulative effect of new stations
For each city i:
- Update t with the difference array value at position i
- Calculate deficit: dist = x - (s[i] + t) where s[i] is initial power and t is power from new stations
- If dist > 0, we need to add stations:
  - If dist > k, we can't achieve target x, return False
  - Otherwise, greedily place dist stations at position j = min(i + r, n - 1) (rightmost position that still covers city i)
  - Update difference array for the range these new stations cover: [max(0, j - r), min(j + r, n - 1)]
  - Deduct from available stations: k -= dist
  - Update running sum: t += dist

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

The greedy strategy of placing stations as far right as possible ensures we maximize coverage for future cities while satisfying the current city's requirements. The difference array technique allows us to efficiently update power coverage for multiple cities when placing new stations, avoiding the need for nested loops.

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a concrete example to illustrate the solution approach.

Given:

stations = [1, 2, 4, 5, 0] (5 cities with initial power stations)
r = 1 (each station covers cities within distance 1)
k = 2 (we can add 2 new power stations)

Step 1: Calculate Initial Power for Each City

First, we compute how many stations initially cover each city using a difference array.

For each existing station:

Station at city 0 (1 station): covers cities [0, 1]
- d[0] += 1, d[2] -= 1
Station at city 1 (2 stations): covers cities [0, 2]
- d[0] += 2, d[3] -= 2
Station at city 2 (4 stations): covers cities [1, 3]
- d[1] += 4, d[4] -= 4
Station at city 3 (5 stations): covers cities [2, 4]
- d[2] += 5, d[5] -= 5
Station at city 4 (0 stations): no effect

Difference array: d = [3, 4, 4, -2, -4, -5]

Using prefix sum: s = [3, 7, 11, 9, 5, 0]

Initial power for each city: [3, 7, 11, 9, 5]

City 0: power = 3
City 1: power = 7
City 2: power = 11
City 3: power = 9
City 4: power = 5

Current minimum power = 3 (city 0)

Step 2: Binary Search for Maximum Minimum Power

Binary search range: [0, 1<<40]

Let's check if we can achieve minimum power = 5:

Check if minimum power = 5 is achievable:

Traverse each city from left to right:

City 0: Current power = 3, need 5 → deficit = 2
- Place 2 stations at position min(0 + 1, 4) = 1
- These stations at city 1 cover cities [0, 2]
- Update: k = 0 stations remaining
- Running power additions: city 0 gets +2, city 1 gets +2, city 2 gets +2
City 1: Current power = 7 + 2 = 9 ≥ 5 ✓
City 2: Current power = 11 + 2 = 13 ≥ 5 ✓
City 3: Current power = 9 + 0 = 9 ≥ 5 ✓
City 4: Current power = 5 + 0 = 5 ≥ 5 ✓

Result: We can achieve minimum power = 5 with exactly 2 stations.

Check if minimum power = 6 is achievable:

City 0: Current power = 3, need 6 → deficit = 3
- We only have k = 2 stations available, but need 3
- Return False

Result: Cannot achieve minimum power = 6.

Final Answer: The maximum achievable minimum power is 5.

The solution efficiently:

Uses difference arrays to track power coverage without nested loops
Greedily places new stations as far right as possible to maximize coverage
Uses binary search to find the optimal answer in O(n log(max_power)) time

Time and Space Complexity

Time Complexity: O(n × log M) where n is the length of the stations array (number of cities) and M = 2^40.

The binary search runs from left = 0 to right = 2^40, performing O(log M) iterations where M = 2^40. In each binary search iteration, the check function is called, which contains a single loop that iterates through all n cities. Within this loop, all operations (including difference array updates and accumulation) are O(1). Therefore, each call to check takes O(n) time. The initial preprocessing (creating the difference array and computing prefix sums) also takes O(n) time. Thus, the overall time complexity is O(n) + O(n × log M) = O(n × log M).

Space Complexity: O(n) where n is the number of cities.

The algorithm uses several arrays of size n+1: the difference array d (used both in preprocessing and in the check function), and the prefix sum array s. Each of these arrays requires O(n) space. The binary search and other variables use O(1) additional space. Therefore, the total space complexity is O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Greedy Placement Strategy

Pitfall: A common mistake is placing new power stations at the position of the current city that needs power, rather than at the optimal position within range.

Why it's wrong: When city i needs more power, placing stations directly at city i might not be optimal. We want to maximize coverage for future cities while still satisfying the current city's needs.

Example: If city 2 needs power and r = 2, placing a station at city 2 covers cities [0, 1, 2, 3, 4]. But placing it at city 4 (the rightmost position that still covers city 2) covers cities [2, 3, 4, 5, 6], which helps more with upcoming cities.

Solution: Always place new stations at position min(i + r, n - 1) when city i needs power. This greedy rightmost placement ensures maximum coverage for cities we haven't processed yet.

2. Difference Array Boundary Errors

Pitfall: Forgetting to allocate n + 1 size for the difference array, leading to index out of bounds errors when updating d[right + 1].

Why it happens: When updating a range [left, right] in a difference array, we need to set d[right + 1] -= value. If right = n - 1, then right + 1 = n, requiring array size of at least n + 1.

Solution: Always initialize difference arrays with size n + 1:

d = [0] * (n + 1) # Not [0] * n

3. Accumulating Power Updates Incorrectly

Pitfall: Not maintaining the running sum t correctly when checking if we can achieve a target power level. Some implementations reset t or forget to update it when placing new stations.

Why it's problematic: The variable t tracks the cumulative effect of all newly placed power stations up to the current position. If not maintained properly, the power calculation s[i] + t will be incorrect.

Solution:

Update t at the beginning of each iteration: t += d[i]
When placing new stations, immediately update t if they affect the current city: t += dist

4. Binary Search Boundary Selection

Pitfall: Using standard binary search with mid = (left + right) // 2 instead of mid = (left + right + 1) // 2 when searching for maximum value.

Why it matters: When searching for the maximum achievable value, using the lower mid can cause infinite loops when left = right - 1. The condition check(mid) being true would set left = mid, keeping us stuck.

Solution: When maximizing, use upper mid:

mid = (left + right + 1) >> 1 # Upper mid for maximization if check(mid, k):  left = mid else:  right = mid - 1

5. Modifying Initial Power Array During Check

Pitfall: Directly modifying the initial power array s inside the check function, which corrupts data for subsequent binary search iterations.

Why it's wrong: The binary search calls check() multiple times with different target values. If s is modified, subsequent checks will use corrupted initial power values.

Solution: Never modify the initial power array. Use a separate difference array and running sum to track additions:

# DON'T DO: s[j] += dist for j in range(...) # DO: Use difference array d and running sum t d[left] += dist d[right + 1] -= dist t += dist # Update running sum for current position

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

Which technique can we use to find the middle of a linked list?

Fast-slow pointers

Two pointers moving in opposite direction

Binary search

Depth first search

I don't know