Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Break down a hard problem into reliable checkpoints, edge-case handling, and complexity trade-offs.
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 summary: 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Array · Binary Search · Greedy · Sliding Window
[1,2,4,5,0] 1 2
[4,4,4,4] 0 3
maximum-number-of-tasks-you-can-assign)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #2528: Maximize the Minimum Powered City
class Solution {
private long[] s;
private long[] d;
private int n;
public long maxPower(int[] stations, int r, int k) {
n = stations.length;
d = new long[n + 1];
s = new long[n + 1];
for (int i = 0; i < n; ++i) {
int left = Math.max(0, i - r), right = Math.min(i + r, n - 1);
d[left] += stations[i];
d[right + 1] -= stations[i];
}
s[0] = d[0];
for (int i = 1; i < n + 1; ++i) {
s[i] = s[i - 1] + d[i];
}
long left = 0, right = 1l << 40;
while (left < right) {
long mid = (left + right + 1) >>> 1;
if (check(mid, r, k)) {
left = mid;
} else {
right = mid - 1;
}
}
return left;
}
private boolean check(long x, int r, int k) {
Arrays.fill(d, 0);
long t = 0;
for (int i = 0; i < n; ++i) {
t += d[i];
long dist = x - (s[i] + t);
if (dist > 0) {
if (k < dist) {
return false;
}
k -= dist;
int j = Math.min(i + r, n - 1);
int left = Math.max(0, j - r), right = Math.min(j + r, n - 1);
d[left] += dist;
d[right + 1] -= dist;
t += dist;
}
}
return true;
}
}
// Accepted solution for LeetCode #2528: Maximize the Minimum Powered City
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)
}
# Accepted solution for LeetCode #2528: Maximize the Minimum Powered City
class Solution:
def maxPower(self, stations: List[int], r: int, k: int) -> int:
def check(x, k):
d = [0] * (n + 1)
t = 0
for i in range(n):
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
n = len(stations)
d = [0] * (n + 1)
for i, v in enumerate(stations):
left, right = max(0, i - r), min(i + r, n - 1)
d[left] += v
d[right + 1] -= v
s = list(accumulate(d))
left, right = 0, 1 << 40
while left < right:
mid = (left + right + 1) >> 1
if check(mid, k):
left = mid
else:
right = mid - 1
return left
// Accepted solution for LeetCode #2528: Maximize the Minimum Powered City
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
}
}
// Accepted solution for LeetCode #2528: Maximize the Minimum Powered City
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);
}
Use this to step through a reusable interview workflow for this problem.
Check every element from left to right until we find the target or exhaust the array. Each comparison is O(1), and we may visit all n elements, giving O(n). No extra space needed.
Each comparison eliminates half the remaining search space. After k comparisons, the space is n/2ᵏ. We stop when the space is 1, so k = log₂ n. No extra memory needed — just two pointers (lo, hi).
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Wrong move: Setting `lo = mid` or `hi = mid` can stall and create an infinite loop.
Usually fails on: Two-element ranges never converge.
Fix: Use `lo = mid + 1` or `hi = mid - 1` where appropriate.
Wrong move: Locally optimal choices may fail globally.
Usually fails on: Counterexamples appear on crafted input orderings.
Fix: Verify with exchange argument or monotonic objective before committing.
Wrong move: Using `if` instead of `while` leaves the window invalid for multiple iterations.
Usually fails on: Over-limit windows stay invalid and produce wrong lengths/counts.
Fix: Shrink in a `while` loop until the invariant is valid again.