This content originally appeared on DEV Community and was authored by MD ARIFUL HAQUE
2528. Maximize the Minimum Powered City
Difficulty: Hard
Topics: Array, Binary Search, Greedy, Queue, Sliding Window, Prefix Sum, Biweekly Contest 95
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 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.
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⁵0 <= stations[i] <= 10⁵0 <= r <= n - 10 <= k <= 10⁹
Hint:
- Pre calculate the number of stations on each city using Line Sweep.
- Use binary search to maximize the minimum.
Solution:
We need to find the maximum possible minimum power across all cities after optimally placing k additional power stations.
Approach:
Understanding the power calculation: Each power station at position
iprovides power to all cities within[i-r, i+r]. So the power of a city is the sum of all stations that can reach it.Key insight: This is a classic "maximize the minimum" problem, which suggests using binary search. I'll binary search on the possible minimum power values.
Preprocessing: First, I need to calculate the initial power for each city. I can use a prefix sum/difference array technique to efficiently compute how many stations cover each city.
Checking feasibility: For a candidate minimum power
x, I need to check if I can place at mostkstations to make all cities have at leastxpower. I'll use a greedy approach with a sliding window.
Let's implement this solution in PHP: 2528. Maximize the Minimum Powered City
<?php
/**
* @param Integer[] $stations
* @param Integer $r
* @param Integer $k
* @return Integer
*/
function maxPower($stations, $r, $k) {
...
...
...
/**
* go to ./solution.php
*/
}
/**
* @param $initialPower
* @param $r
* @param $k
* @param $target
* @return bool
*/
function isPossible($initialPower, $r, $k, $target) {
...
...
...
/**
* go to ./solution.php
*/
}
// Test cases
echo maxPower([1, 2, 4, 5, 0], 1, 2) . PHP_EOL; // Output: 5
echo maxPower([4, 4, 4, 4], 0, 3) . PHP_EOL; // Output: 4
?>
Explanation:
Initial Power Calculation: I use a difference array technique where
prefix[left] += stations[i]andprefix[right + 1] -= stations[i]. Then I compute the prefix sum to get the actual power for each city.Binary Search: I search for the maximum minimum power between
0andmax(initial power) + k.-
Feasibility Check: For a candidate
target:- I maintain a sliding window of additions using a difference array
- For each city, if its current power (initial + additions) is less than target, I add stations at the farthest possible position (
i + r) to cover as many future cities as possible - I track if I exceed the available
kstations
Time Complexity: O(n log(max_power + k)), where n is the number of cities
Space Complexity: O(n) for the auxiliary arrays
Contact Links
If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!
If you want more helpful content like this, feel free to follow me:
This content originally appeared on DEV Community and was authored by MD ARIFUL HAQUE
MD ARIFUL HAQUE | Sciencx (2025-11-07T13:06:14+00:00) 2528. Maximize the Minimum Powered City. Retrieved from https://www.scien.cx/2025/11/07/2528-maximize-the-minimum-powered-city/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.