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.
|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.
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 <= 1050 <= stations[i] <= 1050 <= r <= n - 10 <= k <= 109Problem Overview: You are given an array where stations[i] represents the number of power stations in city i. Each station powers cities within distance r. You can build k additional stations anywhere. The goal is to maximize the minimum power received by any city after optimally placing the new stations.
Approach 1: Binary Search with Sliding Window (O(n log M) time, O(n) space)
The key observation: instead of directly deciding where to place stations, you can binary search the answer — the maximum possible minimum power across all cities. For a candidate value x, check if it is possible to ensure every city has at least x power using at most k new stations. Compute the initial power for each city using a range contribution technique similar to prefix sum. While scanning cities from left to right, maintain the current effective power with a sliding window. If a city’s power is below x, add the required number of stations as far right as possible so their coverage extends forward. Track added stations with a difference array or queue to expire their influence once the range ends. If total additions exceed k, the candidate value is impossible. Binary searching this feasibility check yields the optimal answer.
Approach 2: Greedy Placement to Maximize Minimum Power (O(n log M) time, O(n) space)
This approach follows the same binary search framework but focuses on a pure greedy placement strategy during the feasibility check. When a city lacks enough power to meet the target minimum, immediately place the required stations at the farthest city within coverage (i + r). This greedy choice maximizes future coverage and minimizes the number of stations needed later. A running sum tracks active station effects, and a queue or difference array removes their contribution once they move outside the coverage window. The greedy placement ensures each added station benefits the largest possible range of upcoming cities.
Both approaches rely heavily on binary search over the answer space. Instead of constructing the final configuration directly, you repeatedly check feasibility and tighten the search bounds. The feasibility step runs in linear time, making the overall complexity O(n log M), where M is the possible range of power values.
Recommended for interviews: The binary search with sliding window feasibility check is the expected solution. Interviewers look for the insight that the minimum power can be optimized via binary search, combined with a greedy placement strategy to maintain the required threshold. Explaining the feasibility check clearly shows strong understanding of range updates and greedy optimization.
The idea is to use binary search to find the maximum possible minimum power. Define a function that uses a sliding window to check if it's possible to achieve a certain power level. For each mid value (current candidate for maximum minimum power), try to distribute the additional stations optimally to ensure that every city has at least this power level.
This approach defines a binary search on the value of the possible minimum power, and uses a helper function, canAchieve, to check if a given power level can be achieved using the sliding window technique and a temporary array add to track changes.
Time complexity: O(n log(maxStations)) where n is the number of cities and maxStations is the initial range considered.
Space complexity: O(n) for the additional working space.
In this approach, consider iterating from the city with the lowest current power. Utilizing a greedy strategy, try to place power stations in such a way that you're filling the "gaps". Adjust the current power array as stations are added, and track the distribution to maintain a greedy but strategic placement of available stations to maximize the power efficiently.
This simple greedy implementation uses a sorting mechanism to adjust city powers by placing new stations where they're most needed. The adjustment aims to keep all cities as balanced as possible as early as possible.
Time complexity: O(n log n) due to sorting.
Space complexity: O(1) as changes are made directly on the input array.
According to the problem description, the minimum number of power stations increases as the value of k increases. Therefore, we can use binary search to find the largest minimum number of power stations, ensuring that the additional power stations needed do not exceed k.
First, we use a difference array and prefix sum to calculate the initial number of power stations in each city, recording it in the array s, where s[i] represents the number of power stations in the i-th city.
Next, we define the left boundary of the binary search as 0 and the right boundary as 2^{40}. Then, we implement a function check(x, k) to determine whether the minimum number of power stations in the cities can be x, ensuring that the additional power stations needed do not exceed k.
The implementation logic of the function check(x, k) is as follows:
Traverse each city. If the number of power stations in the current city i is less than x, we can greedily build a power station at the rightmost possible position, j = min(i + r, n - 1), to cover as many cities as possible. During this process, we can use the difference array to add a certain value to a continuous segment. If the number of additional power stations needed exceeds k, then x does not meet the condition, and we return false. Otherwise, after the traversal, return true.
The time complexity is O(n times log M), and the space complexity is O(n). Here, n is the number of cities, and M is fixed at 2^{40}.
| Approach | Complexity |
|---|---|
| Approach 1: Binary Search with Sliding Window | Time complexity: O(n log(maxStations)) where n is the number of cities and maxStations is the initial range considered. |
| Approach 2: Greedy Placement to Maximize Minimum Power | Time complexity: O(n log n) due to sorting. |
| Binary Search + Difference Array + Greedy | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Binary Search with Sliding Window | O(n log M) | O(n) | General optimal solution when maximizing a minimum value with range influence |
| Greedy Placement with Binary Search | O(n log M) | O(n) | When implementing a clearer feasibility check using greedy station placement |
Maximize the Minimum Powered City | Deep Dive | Dry Run | Intuition | Leetcode 2528 | MIK • codestorywithMIK • 7,120 views views
Watch 9 more video solutions →Practice Maximize the Minimum Powered City with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor