Maximize the Minimum Powered City solution and explanation
Google
9 more videos on this problem
Maximize the Minimum Powered City | Deep Dive | Dry Run | Intuition | Leetcode 2528 | MIKcodestorywithMIK · 59:31 · 7K views
Maximize the Minimum Powered City - Leetcode 2528 - PythonNeetCodeIO · 31:27 · 6K views
Maximize the Minimum Powered City | LeetCode 2528 | Complete Intuition ExplainedSanyam IIT Guwahati · 32:41 · 1K views
Maximize the Minimum Powered City - Binary Search / Sliding Window - PythonCheatCode Ninja · 8:10 · 1K views
Maximize the Minimum Powered City | Leetcode 2528 | Leetcode BiWeekly contest 95Tech Courses · 13:15 · 1K views
2528 Maximize the Minimum Powered City | LeetCode | C++ | Beginner Friendly ExplanationDeep Tech · 20:46 · 1K views
2528. Maximize the Minimum Powered City (Leetcode Hard)Programming Live with Larry · 50:42 · 864 views
LeetCode 2528 🔥 Maximize the Minimum Powered City | DCC | Binary Search + Sliding Window + Dry Run Study Placement · 22:10 · 642 views
【每日一题】LeetCode 2528. Maximize the Minimum Powered CityHuifeng Guan · 15:23 · 524 views
2528. Maximize the Minimum Powered City | Leetcode Daily - PythonLeetcode Daily · 9:27 · 475 views
The problem
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 <= 1050 <= stations[i] <= 1050 <= r <= n - 10 <= k <= 109
Approach overview
Problem 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 1: Approach 1: Binary Search with Sliding Window
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.
def can_achieve(stations, n, r, k, min_power):
add = [0] * n
needed = sum_ = 0
for i in range(n):
if i > 0:
sum_ += add[i-1]
current_power = stations[i] + sum_
if current_power < min_power:
increase = min_power - current_power
needed += increase
if needed > k:
return False
sum_ += increase
if i + 2 * r + 1 < n:
add[i + 2 * r + 1] -= increase
return True
def max_min_power(stations, r, k):
n = len(stations)
left, right = 0, int(1e9)
answer = 0
while left <= right:
mid = (left + right) // 2
if can_achieve(stations, n, r, k, mid):
answer = mid
left = mid + 1
else:
right = mid - 1
return answer
stations = [1, 2, 4, 5, 0]
r = 1
k = 2
print(max_min_power(stations, r, k))import java.util.*;
class Solution {
public boolean canAchieve(int[] stations, int r, int k, int minPower) {
int n = stations.length;
int[] add = new int[n];
int needed = 0, sum = 0;
for (int i = 0; i < n; ++i) {
if (i > 0) sum += add[i-1];
int currentPower = stations[i] + sum;
if (currentPower < minPower) {
int increase = minPower - currentPower;
needed += increase;
if (needed > k) return false;
sum += increase;
if (i + 2 * r + 1 < n) add[i + 2 * r + 1] -= increase;
}
}
return true;
}
public int maxMinPower(int[] stations, int r, int k) {
int left = 0, right = 1000000000, answer = 0;
while (left <= right) {
int mid = left + (right - left) / 2;
if (canAchieve(stations, r, k, mid)) {
answer = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
return answer;
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] stations = {1, 2, 4, 5, 0};
int r = 1, k = 2;
System.out.println(solution.maxMinPower(stations, r, k));
}
}#include <iostream>
#include <vector>
using namespace std;
bool canAchieve(vector<int>& stations, int n, int r, int k, int minPower) {
vector<int> add(n, 0);
int needed = 0, sum = 0;
for (int i = 0; i < n; ++i) {
if (i > 0) sum += add[i-1];
int currentPower = stations[i] + sum;
if (currentPower < minPower) {
int increase = minPower - currentPower;
needed += increase;
if (needed > k) return false;
sum += increase;
if (i + 2 * r + 1 < n) add[i + 2 * r + 1] -= increase;
}
}
return true;
}
int maxMinPower(vector<int>& stations, int r, int k) {
int n = stations.size();
int left = 0, right = 1e9, answer = 0;
while (left <= right) {
int mid = left + (right - left) / 2;
if (canAchieve(stations, n, r, k, mid)) {
answer = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
return answer;
}
int main() {
vector<int> stations = {1, 2, 4, 5, 0};
int r = 1, k = 2;
cout << maxMinPower(stations, r, k) << endl;
return 0;
}function canAchieve(stations, n, r, k, minPower) {
let add = Array(n).fill(0);
let needed = 0, sum = 0;
for (let i = 0; i < n; ++i) {
if (i > 0) sum += add[i - 1];
let currentPower = stations[i] + sum;
if (currentPower < minPower) {
let increase = minPower - currentPower;
needed += increase;
if (needed > k) return false;
sum += increase;
if (i + 2 * r + 1 < n) add[i + 2 * r + 1] -= increase;
}
}
return true;
}
function maxMinPower(stations, r, k) {
let n = stations.length;
let left = 0, right = 1e9, answer = 0;
while (left <= right) {
let mid = Math.floor((left + right) / 2);
if (canAchieve(stations, n, r, k, mid)) {
answer = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
return answer;
}
let stations = [1, 2, 4, 5, 0];
let r = 1, k = 2;
console.log(maxMinPower(stations, r, k));#include <stdio.h>
#include <stdbool.h>
bool canAchieve(int *stations, int n, int r, int k, int minPower) {
int add[n];
for (int i = 0; i < n; ++i) add[i] = 0;
int needed = 0, sum = 0;
for (int i = 0; i < n; ++i) {
if (i > 0) sum += add[i-1];
int currentPower = stations[i] + sum;
if (currentPower < minPower) {
int increase = minPower - currentPower;
needed += increase;
if (needed > k) return false;
sum += increase;
if (i + 2 * r + 1 < n) add[i + 2 * r + 1] -= increase;
}
}
return true;
}
int maxMinPower(int* stations, int n, int r, int k) {
int left = 0, right = 1e9, answer = 0;
while (left <= right) {
int mid = left + (right - left) / 2;
if (canAchieve(stations, n, r, k, mid)) {
answer = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
return answer;
}
int main() {
int stations[] = {1, 2, 4, 5, 0};
int n = 5, r = 1, k = 2;
printf("%d\n", maxMinPower(stations, n, r, k));
return 0;
}using System;
class Solution {
public bool CanAchieve(int[] stations, int r, int k, long minPower) {
int n = stations.Length;
int[] add = new int[n];
long needed = 0, sum = 0;
for (int i = 0; i < n; ++i) {
if (i > 0) sum += add[i-1];
long currentPower = stations[i] + sum;
if (currentPower < minPower) {
long increase = minPower - currentPower;
needed += increase;
if (needed > k) return false;
sum += increase;
if (i + 2 * r + 1 < n) add[i + 2 * r + 1] -= (int)increase;
}
}
return true;
}
public int MaxMinPower(int[] stations, int r, int k) {
int left = 0, right = 1000000000, answer = 0;
while (left <= right) {
int mid = left + (right - left) / 2;
if (CanAchieve(stations, r, k, mid)) {
answer = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
return answer;
}
static void Main(string[] args) {
Solution solution = new Solution();
int[] stations = {1, 2, 4, 5, 0};
int r = 1, k = 2;
Console.WriteLine(solution.MaxMinPower(stations, r, k));
}
}This Python implementation efficiently checks with a binary search approach to determine if a feasible minimum power level can be reached. Helper function can_achieve is used for validation.
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 add list.
Approach 2: Approach 2: Greedy Placement to Maximize Minimum Power
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.
def max_min_power(stations, r, k):
stations.sort()
for i in range(len(stations)):
if k > 0 and stations[i] < stations[0] + k:
delta = stations[0] + k - stations[i]
stations[i] += delta
k -= delta
return stations[0]
stations = [1, 2, 4, 5, 0]
r = 1
k = 2
print(max_min_power(stations, r, k))import java.util.*;
class Solution {
public int maxMinPower(int[] stations, int r, int k) {
Arrays.sort(stations);
for (int i = 0; i < stations.length; i++) {
if (k > 0 && stations[i] < stations[0] + k) {
int delta = stations[0] + k - stations[i];
stations[i] += delta;
k -= delta;
}
}
return stations[0];
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] stations = {1, 2, 4, 5, 0};
int r = 1, k = 2;
System.out.println(solution.maxMinPower(stations, r, k));
}
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int maxMinPower(vector<int>& stations, int r, int k) {
sort(stations.begin(), stations.end());
for (int& power : stations) {
if (k > 0 && power < stations[0] + k) {
int delta = stations[0] + k - power;
power += delta;
k -= delta;
}
}
return stations[0];
}
int main() {
vector<int> stations = {1, 2, 4, 5, 0};
int r = 1, k = 2;
cout << maxMinPower(stations, r, k) << endl;
return 0;
}function maxMinPower(stations, r, k) {
stations.sort((a, b) => a - b);
for (let i = 0; i < stations.length; i++) {
if (k > 0 && stations[i] < stations[0] + k) {
let delta = stations[0] + k - stations[i];
stations[i] += delta;
k -= delta;
}
}
return stations[0];
}
let stations = [1, 2, 4, 5, 0];
let r = 1, k = 2;
console.log(maxMinPower(stations, r, k));#include <stdio.h>
#include <stdlib.h>
int cmp(const void* a, const void* b) {
return (*(int*)a - *(int*)b);
}
int maxMinPower(int* stations, int n, int r, int k) {
qsort(stations, n, sizeof(int), cmp);
for (int i = 0; i < n; ++i) {
if (k > 0 && stations[i] < stations[0] + k) {
int delta = stations[0] + k - stations[i];
stations[i] += delta;
k -= delta;
}
}
return stations[0];
}
int main() {
int stations[] = {1, 2, 4, 5, 0};
int n = 5, r = 1, k = 2;
printf("%d\n", maxMinPower(stations, n, r, k));
return 0;
}using System;
using System.Linq;
class Solution {
public int MaxMinPower(int[] stations, int r, int k) {
Array.Sort(stations);
for (int i = 0; i < stations.Length; i++) {
if (k > 0 && stations[i] < stations[0] + k) {
int delta = stations[0] + k - stations[i];
stations[i] += delta;
k -= delta;
}
}
return stations[0];
}
static void Main(string[] args) {
Solution solution = new Solution();
int[] stations = {1, 2, 4, 5, 0};
int r = 1, k = 2;
Console.WriteLine(solution.MaxMinPower(stations, r, k));
}
}The Python greedy approach involves sorting stations and redistributing additional power to manage balancing across existing city power levels effectively.
Time complexity: O(n log n), due to sorting operations primarily. The in-place work keeps space overhead at O(1).
Approach 3: Binary Search + Difference Array + Greedy
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}.
function maxPower(stations: number[], r: number, k: number): number {
function check(x: bigint, k: bigint): boolean {
d.fill(0n);
let t = 0n;
for (let i = 0; i < n; ++i) {
t += d[i];
const dist = x - (s[i] + t);
if (dist > 0) {
if (k < dist) {
return false;
}
k -= dist;
const j = Math.min(i + r, n - 1);
const left = Math.max(0, j - r);
const right = Math.min(j + r, n - 1);
d[left] += dist;
d[right + 1] -= dist;
t += dist;
}
}
return true;
}
const n = stations.length;
const d: bigint[] = new Array(n + 1).fill(0n);
const s: bigint[] = new Array(n + 1).fill(0n);
for (let i = 0; i < n; ++i) {
const left = Math.max(0, i - r);
const right = Math.min(i + r, n - 1);
d[left] += BigInt(stations[i]);
d[right + 1] -= BigInt(stations[i]);
}
s[0] = d[0];
for (let i = 1; i < n + 1; ++i) {
s[i] = s[i - 1] + d[i];
}
let left = 0n,
right = 1n << 40n;
while (left < right) {
const mid = (left + right + 1n) >> 1n;
if (check(mid, BigInt(k))) {
left = mid;
} else {
right = mid - 1n;
}
}
return Number(left);
}func maxPower(stations []int, r int, k int) int64 {
n := len(stations)
d := make([]int, n+1)
s := make([]int, n+1)
for i, v := range stations {
left, right := max(0, i-r), min(i+r, n-1)
d[left] += v
d[right+1] -= v
}
s[0] = d[0]
for i := 1; i < n+1; i++ {
s[i] = s[i-1] + d[i]
}
check := func(x, k int) bool {
d := make([]int, n+1)
t := 0
for i := range stations {
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
}
left, right := 0, 1<<40
for left < right {
mid := (left + right + 1) >> 1
if check(mid, k) {
left = mid
} else {
right = mid - 1
}
}
return int64(left)
}impl Solution {
pub fn max_power(stations: Vec<i32>, r: i32, k: i32) -> i64 {
let n = stations.len();
let mut d = vec![0i64; n + 2];
for i in 0..n {
let left = i.saturating_sub(r as usize);
let right = (i + r as usize).min(n - 1);
d[left] += stations[i] as i64;
d[right + 1] -= stations[i] as i64;
}
let mut s = vec![0i64; n + 1];
s[0] = d[0];
for i in 1..=n {
s[i] = s[i - 1] + d[i];
}
let check = |x: i64, mut k: i64| -> bool {
let mut d = vec![0i64; n + 2];
let mut t = 0i64;
for i in 0..n {
t += d[i];
let dist = x - (s[i] + t);
if dist > 0 {
if k < dist {
return false;
}
k -= dist;
let j = (i + r as usize).min(n - 1);
let left = j.saturating_sub(r as usize);
let right = (j + r as usize).min(n - 1);
d[left] += dist;
d[right + 1] -= dist;
t += dist;
}
}
true
};
let (mut left, mut right) = (0i64, 1_000_000_000_000i64);
while left < right {
let mid = (left + right + 1) >> 1;
if check(mid, k as i64) {
left = mid;
} else {
right = mid - 1;
}
}
left
}
}Complexity comparison
| 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 operations primarily. The in-place work keeps space overhead at O(1). |
| Binary Search + Difference Array + Greedy | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Maximize the Minimum Powered City easy or hard?
Maximize the Minimum Powered City is classified as Hard on LeetCode. The challenge comes from recognizing the binary-search-on-answer pattern and implementing an efficient range update strategy to simulate adding stations within O(n) time per check.
How to solve Maximize the Minimum Powered City in O(n)?
A full O(n) solution is not feasible because the answer must be searched over a range of possible power values. The standard approach performs binary search over the minimum power and uses an O(n) feasibility check, resulting in O(n log M) overall complexity.
Maximize the Minimum Powered City Python or Java solution
Python, Java, C++, and other languages implement the same strategy: binary search the minimum power and run a greedy feasibility check with range updates. The core logic involves maintaining a running power sum and dynamically adding stations when a city falls below the target.
What is the best approach for Maximize the Minimum Powered City?
The best approach is binary search on the minimum power combined with a greedy feasibility check using a sliding window. For each candidate minimum value, simulate adding stations while scanning the cities and maintain active power contributions with a difference array or queue. This reduces the search to O(n log M) time, where M is the possible power range.
Is Maximize the Minimum Powered City asked at Google/Amazon/Meta?
Problems combining binary search on the answer with greedy range updates frequently appear in interviews at companies like Google, Amazon, and Meta. Variations of maximizing a minimum value under constraints are common in senior-level algorithm interviews.
What data structure is used in Maximize the Minimum Powered City?
The solution typically uses arrays with prefix-sum or difference-array techniques to track active power contributions. A sliding window or queue is used to expire the effect of newly added stations once their coverage range ends.
What is the time complexity of Maximize the Minimum Powered City?
The optimal solution runs in O(n log M) time and O(n) space. The binary search tries different minimum power values, and each feasibility check scans the cities once while applying range updates with a sliding window technique.