Skip to content

2618. Maximize The Minimum Powered City

Array Binary Search Greedy Queue Sliding Window Prefix Sum

Problem - Maximize The Minimum Powered City

Hard

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.

 

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.length
  • 1 <= n <= 105
  • 0 <= stations[i] <= 105
  • 0 <= r <= n - 1
  • 0 <= k <= 109

Solutions

 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
33
34
35
36
class Solution:
    def maxPower(self, stations: List[int], r: int, k: int) -> int:
        n = len(stations)
        f = [0] * (n + 1)
        for i, val in enumerate(stations):
            left, right = max(0, i - r), min(i + r, n - 1)
            f[left] += val
            f[right + 1] -= val

        s = list(accumulate(f))

        def checker(x, k):
            f = [0] * (n + 1)
            t = 0
            for i in range(n):
                t += f[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)
                    f[left] += dist
                    f[right + 1] -= dist
                    t += dist
            return True

        left, right = 0, 1 << 40
        while right > left:
            mid = (left + right + 1) // 2
            if checker(mid, k):
                left = mid
            else:
                right = mid - 1
        return left

Submission Stats:

  • Runtime: 1476 ms (60.83%)
  • Memory: 33.3 MB (41.24%)