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

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

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

1
2
3
4

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.length
  • 1 <= n <= 10^5
  • 0 <= stations[i] <= 10^5
  • 0 <= r <= n - 1
  • 0 <= k <= 10^9

Solution

Method 1 – Binary Search with Sliding Window Greedy

Intuition

To maximize the minimum power of any city, we can use binary search on the answer. For each candidate minimum, we check if it’s possible to achieve at least that much power in every city by optimally placing up to k new stations. We use a sliding window to efficiently track the current power in each city and greedily add stations where needed.

Approach

  1. Use binary search for the answer between 0 and the sum of all stations plus k.
  2. For each mid value, check if it’s possible to achieve at least mid power in every city:
    • Use a sliding window to maintain the current power for each city.
    • If a city has less than mid power, add stations at the farthest possible position within range to maximize coverage, and update the window.
    • Track the number of stations added; if it exceeds k, it’s not possible.
  3. If possible, try a higher value; otherwise, try lower.
  4. Return the largest value for which it is possible.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

class Solution {
public:
    bool can(vector<int>& st, int r, long long k, long long minP) {
        int n = st.size();
        vector<long long> a(st.begin(), st.end());
        vector<long long> diff(n+1, 0);
        long long add = 0, sum = 0;
        for (int i = 0; i < n; ++i) {
            if (i > 0) diff[i] += diff[i-1];
            long long cur = a[i] + diff[i];
            if (cur < minP) {
                long long need = minP - cur;
                if (need > k) return false;
                k -= need;
                int idx = min(n-1, i + r);
                diff[i] += need;
                if (idx+1 < n) diff[idx+1] -= need;
            }
        }
        return true;
    }
    long long maxPower(vector<int>& st, int r, int k) {
        long long l = 0, rgt = accumulate(st.begin(), st.end(), 0LL) + k, ans = 0;
        while (l <= rgt) {
            long long m = (l + rgt) / 2;
            if (can(st, r, k, m)) { ans = m; l = m + 1; }
            else rgt = m - 1;
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

func maxPower(st []int, r, k int) int64 {
    n := len(st)
    l, h := int64(0), int64(0)
    for _, x := range st { h += int64(x) }
    h += int64(k)
    var can func(int64) bool
    can = func(minP int64) bool {
        diff := make([]int64, n+1)
        add := int64(0)
        for i := 0; i < n; i++ {
            if i > 0 { diff[i] += diff[i-1] }
            cur := int64(st[i]) + diff[i]
            if cur < minP {
                need := minP - cur
                if need > int64(k)-add { return false }
                add += need
                idx := i + r
                if idx >= n { idx = n-1 }
                diff[i] += need
                if idx+1 < n { diff[idx+1] -= need }
            }
        }
        return true
    }
    var ans int64
    for l <= h {
        m := (l + h) / 2
        if can(m) { ans = m; l = m + 1 } else { h = m - 1 }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

class Solution {
    public long maxPower(int[] st, int r, int k) {
        long l = 0, h = 0;
        for (int x : st) h += x;
        h += k;
        long ans = 0;
        while (l <= h) {
            long m = (l + h) / 2;
            if (can(st, r, k, m)) { ans = m; l = m + 1; }
            else h = m - 1;
        }
        return ans;
    }
    private boolean can(int[] st, int r, int k, long minP) {
        int n = st.length;
        long[] diff = new long[n+1];
        long add = 0;
        for (int i = 0; i < n; i++) {
            if (i > 0) diff[i] += diff[i-1];
            long cur = st[i] + diff[i];
            if (cur < minP) {
                long need = minP - cur;
                if (need > k - add) return false;
                add += need;
                int idx = Math.min(n-1, i + r);
                diff[i] += need;
                if (idx+1 < n) diff[idx+1] -= need;
            }
        }
        return true;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution {
    fun maxPower(st: IntArray, r: Int, k: Int): Long {
        var l = 0L
        var h = st.map { it.toLong() }.sum() + k
        var ans = 0L
        fun can(minP: Long): Boolean {
            val n = st.size
            val diff = LongArray(n+1)
            var add = 0L
            for (i in 0 until n) {
                if (i > 0) diff[i] += diff[i-1]
                val cur = st[i] + diff[i]
                if (cur < minP) {
                    val need = minP - cur
                    if (need > k - add) return false
                    add += need
                    val idx = minOf(n-1, i + r)
                    diff[i] += need
                    if (idx+1 < n) diff[idx+1] -= need
                }
            }
            return true
        }
        while (l <= h) {
            val m = (l + h) / 2
            if (can(m)) { ans = m; l = m + 1 } else { h = m - 1 }
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution:
    def maxPower(self, stations: list[int], r: int, k: int) -> int:
        n = len(stations)
        def can(x: int) -> bool:
            diff = [0] * (n + 1)
            add = 0
            for i in range(n):
                if i > 0:
                    diff[i] += diff[i-1]
                cur = stations[i] + diff[i]
                if cur < x:
                    need = x - cur
                    if need > k - add:
                        return False
                    add += need
                    idx = min(n-1, i + r)
                    diff[i] += need
                    if idx+1 < n:
                        diff[idx+1] -= need
            return True
        l, h, ans = 0, sum(stations) + k, 0
        while l <= h:
            m = (l + h) // 2
            if can(m):
                ans = m
                l = m + 1
            else:
                h = m - 1
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

impl Solution {
    pub fn max_power(stations: Vec<i64>, r: i64, k: i64) -> i64 {
        let n = stations.len();
        let mut l = 0;
        let mut h = stations.iter().sum::<i64>() + k;
        let mut ans = 0;
        while l <= h {
            let m = (l + h) / 2;
            let mut diff = vec![0; n+1];
            let mut add = 0;
            let mut ok = true;
            for i in 0..n {
                if i > 0 { diff[i] += diff[i-1]; }
                let cur = stations[i] + diff[i];
                if cur < m {
                    let need = m - cur;
                    if need > k - add { ok = false; break; }
                    add += need;
                    let idx = (i as i64 + r).min(n as i64 - 1) as usize;
                    diff[i] += need;
                    if idx+1 < n { diff[idx+1] -= need; }
                }
            }
            if ok { ans = m; l = m + 1; } else { h = m - 1; }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution {
    maxPower(stations: number[], r: number, k: number): number {
        const n = stations.length;
        let l = 0, h = stations.reduce((a, b) => a + b, 0) + k, ans = 0;
        function can(x: number): boolean {
            const diff = new Array(n+1).fill(0);
            let add = 0;
            for (let i = 0; i < n; i++) {
                if (i > 0) diff[i] += diff[i-1];
                const cur = stations[i] + diff[i];
                if (cur < x) {
                    const need = x - cur;
                    if (need > k - add) return false;
                    add += need;
                    const idx = Math.min(n-1, i + r);
                    diff[i] += need;
                    if (idx+1 < n) diff[idx+1] -= need;
                }
            }
            return true;
        }
        while (l <= h) {
            const m = Math.floor((l + h) / 2);
            if (can(m)) { ans = m; l = m + 1; } else { h = m - 1; }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n log X) — where n is the number of cities and X is the search range (up to sum(stations)+k).
  • 🧺 Space complexity: O(n) — for the difference array.