2528. Maximize the Minimum Powered City LeetCode Solution
In this guide, you will get 2528. Maximize the Minimum Powered City LeetCode Solution with the best time and space complexity. The solution to Maximize the Minimum Powered City problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Maximize the Minimum Powered City
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| = 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: 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.length
1 <= n <= 105
0 <= stations[i] <= 105
0 <= r <= n – 1
0 <= k <= 109
Complexity Analysis
Time Complexity: O(n(\Sigma |\texttt{stations[i]}| + k))
Space Complexity: O(n)
2528. Maximize the Minimum Powered City LeetCode Solution in C++
class Solution {
public:
long long maxPower(vector<int>& stations, int r, int k) {
long left = ranges::min(stations);
long right = accumulate(stations.begin(), stations.end(), 0L) + k + 1;
while (left < right) {
const long mid = (left + right) / 2;
if (check(stations, r, k, mid))
left = mid + 1;
else
right = mid;
}
return left - 1;
}
private:
// Returns true if each city can have at least `minPower`.
bool check(vector<int> stations, int r, int additionalStations,
long minPower) {
const int n = stations.size();
// Initilaize `power` as the 0-th city's power - stations[r].
long power = accumulate(stations.begin(), stations.begin() + r, 0L);
for (int i = 0; i < n; ++i) {
if (i + r < n)
power += stations[i + r]; // `power` = sum(stations[i - r..i + r]).
if (power < minPower) {
const long requiredPower = minPower - power;
// There're not enough stations to plant.
if (requiredPower > additionalStations)
return false;
// Greedily plant `requiredPower` power stations in the farthest place
// to cover as many cities as possible.
stations[min(n - 1, i + r)] += requiredPower;
additionalStations -= requiredPower;
power += requiredPower;
}
if (i - r >= 0)
power -= stations[i - r];
}
return true;
}
}; /* code provided by PROGIEZ */
2528. Maximize the Minimum Powered City LeetCode Solution in Java
class Solution {
public long maxPower(int[] stations, int r, int k) {
long left = Arrays.stream(stations).min().getAsInt();
long right = Arrays.stream(stations).asLongStream().sum() + k + 1;
while (left < right) {
final long mid = (left + right) / 2;
if (check(stations.clone(), r, k, mid))
left = mid + 1;
else
right = mid;
}
return left - 1;
}
// Returns true if each city can have at least `minPower`.
boolean check(int[] stations, int r, int additionalStations, long minPower) {
final int n = stations.length;
// Initilaize `power` as the 0-th city's power - stations[r].
long power = 0;
for (int i = 0; i < r; ++i)
power += stations[i];
for (int i = 0; i < n; ++i) {
if (i + r < n)
power += stations[i + r]; // `power` = sum(stations[i - r..i + r]).
if (power < minPower) {
final long requiredPower = minPower - power;
// There're not enough stations to plant.
if (requiredPower > additionalStations)
return false;
// Greedily plant `requiredPower` power stations in the farthest place
// to cover as many cities as possible.
stations[Math.min(n - 1, i + r)] += requiredPower;
additionalStations -= requiredPower;
power += requiredPower;
}
if (i - r >= 0)
power -= stations[i - r];
}
return true;
}
} // code provided by PROGIEZ
2528. Maximize the Minimum Powered City LeetCode Solution in Python
class Solution:
def maxPower(self, stations: list[int], r: int, k: int) -> int:
n = len(stations)
left = min(stations)
right = sum(stations) + k + 1
def check(
stations: list[int],
additionalStations: int, minPower: int) -> bool:
"""Returns True if each city can have at least `minPower`."""
# Initilaize `power` as the 0-th city's power - stations[r].
power = sum(stations[:r])
for i in range(n):
if i + r < n:
power += stations[i + r] # `power` = sum(stations[i - r..i + r]).
if power < minPower:
requiredPower = minPower - power
# There're not enough stations to plant.
if requiredPower > additionalStations:
return False
# Greedily plant `requiredPower` power stations in the farthest place
# to cover as many cities as possible.
stations[min(n - 1, i + r)] += requiredPower
additionalStations -= requiredPower
power += requiredPower
if i - r >= 0:
power -= stations[i - r]
return True
while left < right:
mid = (left + right) // 2
if check(stations.copy(), k, mid):
left = mid + 1
else:
right = mid
return left - 1 # code by PROGIEZ
