#2528

Hard

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Maximize the Minimum Powered City

Determine the maximum minimum power a city can achieve by strategically adding power stations using binary search and prefix sums.

array binary search greedy queue sliding window

Problem Statement

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 station can supply power to cities within a fixed range r, meaning a station at city i powers all cities j such that |i - j| <= r and 0 <= i, j <= n - 1. The power of a city is defined as the total number of stations supplying it.

Your task is to determine the maximum possible minimum power across all cities after adding at most k additional power stations to any cities. Each added station increases the city's count and its effect spreads across its range. Return the highest achievable minimum city power under these constraints.

Examples

Example 1

Input: stations = [1,2,4,5,0], r = 1, k = 2

Output: 5

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

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

Solution Approach

Compute initial city powers using prefix sums

Use a prefix sum array to calculate the power each city currently receives from existing stations. This precomputation allows O(1) range queries when evaluating the effect of adding stations, aligning with the problem's binary search pattern.

Binary search over minimum achievable power

Apply binary search to test possible minimum city power values. For each candidate, simulate adding stations greedily with a line sweep to check feasibility. If the minimum can be met, move the search range higher; otherwise, lower it. This method leverages the exact pattern of searching over valid answer space for optimal city power.

Greedy line sweep for station placement

While testing each candidate minimum power, use a sliding window approach to track added stations efficiently. Increase stations at the farthest point in the range that helps maintain the minimum, ensuring O(n) processing per check. This prevents exceeding time limits and directly addresses the failure mode of naive iteration.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n log(max_possible_power)), where each binary search iteration scans the array with a line sweep in O(n). Space complexity is O(n) for prefix sums and temporary arrays used during the sweep.

What Interviewers Usually Probe

Ask how to efficiently calculate the total power received by each city without recomputing every range repeatedly.
Check if the candidate understands binary search over the valid answer space instead of simulating all possibilities.
Look for recognition of greedy station placement to meet minimum power constraints in linear time per check.

Common Pitfalls or Variants

Common pitfalls

Simulating station addition naively for each candidate minimum power, leading to TLE for large n.
Misunderstanding the range effect of a station, resulting in incorrect city power calculations.
Failing to track cumulative added stations efficiently, causing wrong feasibility checks in binary search.

Follow-up variants

Change the range r dynamically per station and determine the maximum minimum city power.
Limit station addition to specific cities instead of allowing placement anywhere.
Compute the maximum minimum power when some stations have fixed locations and cannot be moved or increased.

FAQ

What is the main pattern to solve Maximize the Minimum Powered City?

The problem follows a binary search over the valid answer space pattern, checking feasibility of minimum power using greedy line sweep.

How do I efficiently compute city powers after adding stations?

Use a prefix sum array to handle range effects of stations, combined with a line sweep for added stations in O(n) per binary search iteration.

Why can't I simulate every addition of stations naively?

Naive simulation is too slow for large n and k, leading to time limit exceeded; binary search plus line sweep is required.

How does station range r affect the solution?

Each station affects cities within |i - j| <= r; this determines the sliding window for power updates and is critical in feasibility checks.

Can GhostInterview handle different station ranges or constraints?

Yes, it adapts the prefix sum and line sweep logic to variable ranges or restricted placement while maintaining the binary search over minimum power pattern.

terminal

Solution

Solution 1: 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$.

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

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

Continue Practicing

#2398 maximum number of robots within budget #2271 maximum white tiles covered by a carpet #1838 frequency of the most frequent element