Watch 10 video solutions for Maximize the Minimum Powered City, a hard level problem involving Array, Binary Search, Greedy. This walkthrough by codestorywithMIK has 7,120 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |