Maximize the minimum powered city

Array Binary Search Greedy Queue Sliding Window Prefix Sum

61.8% acceptance

Feb 25, 2026

868

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. 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.

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn max_power(stations: Vec<i32>, r: i32, k: i32) -> i64 {
    let n = stations.len();
    let r = r as usize;
    let k = k as i64;

    let mut prefix = vec![0i64; n + 1];
    for i in 0..n {
      prefix[i + 1] = prefix[i] + stations[i] as i64;
    }

    let check = |min_power: i64| -> bool {
      let mut add_diff = vec![0i64; n + 2];
      let mut add_extra = 0i64;
      let mut remaining = k;
      for i in 0..n {
        add_extra += add_diff[i];
        let l = if i >= r { i - r } else { 0 };
        let rr = (i + r).min(n - 1);
        let power = prefix[rr + 1] - prefix[l] + add_extra;
        if power < min_power {
          let need = min_power - power;
          if need > remaining {
            return false;
          }
          remaining -= need;
          let place = (i + r).min(n - 1);
          add_extra += need;
          let end_effect = (place + r + 1).min(n);
          add_diff[end_effect] -= need;
        }
      }
      true
    };

    let total: i64 = stations.iter().map(|&x| x as i64).sum();
    let mut lo = 0i64;
    let mut hi = total + k;
    while lo < hi {
      let mid = (lo + hi + 1) / 2;
      if check(mid) {
        lo = mid;
      } else {
        hi = mid - 1;
      }
    }
    lo
  }
}