Maximize the Minimum Powered City

Maximize the Minimum Powered City

What is this problem about?

You are given an array representing cities, where stations[i] is the number of power stations in city i. A power station provides power to its own city and to all cities within a range r. You are given k extra power stations to build. Your goal is to strategically place these k stations to maximize the minimum power received by any single city.

Why is this asked in interviews?

This is a Hard-level optimization problem that combines Binary Search on the Answer with a Sliding Window / Queue. It tests a candidate's ability to layer algorithms. Finding if a target power is possible requires a greedy approach, but because power spans a range r, adding a station affects future cities. Tracking this overlapping power efficiently without $O(N^2)$ recalculations is the true test of engineering capability.

Algorithmic pattern used

This problem uses Binary Search coupled with a Greedy Sliding Window.

1. Precalculate the initial power of each city using a sliding window of size 2r + 1.
2. Binary search the answer (target minimum power).
3. For a guessed target: Iterate left-to-right. Maintain a sliding window of newly added stations. If city i's current power (initial + new stations in range) is less than target, you must add stations.
4. Greedily, the best place to build a new station to cover city i and maximize coverage for future rightward cities is at i + r (the furthest right edge of i's range). Add the deficit to a queue/array and subtract from budget k.

Example explanation

Cities: [1, 2, 4, 5, 0], range r = 1, budget k = 2. Initial power (sum of [i-1, i+1]): [3, 7, 11, 9, 5]. Guess target min_power = 5.

• City 0 has 3. Needs 2 more. Budget $k=2 \to 0$. We build 2 stations at index 0 + 1 = 1.
• New stations at index 1 will affect cities 0, 1, and 2.
• City 1 has 7 + 2 (from new) = 9. $\ge 5$. OK.
• City 2 has 11 + 2 = 13. OK.
• City 3 has 9. OK.
• City 4 has 5. OK. Target 5 is achievable! We search higher. Target 6 will fail because we run out of budget trying to boost City 0 and City 4. Max minimum power is 5.

Common mistakes candidates make

A major pitfall is placing required new stations directly at index i when city i is deficient. Placing it at i covers [i-r, i+r]. But since you are scanning left-to-right, everything to the left of i is already satisfied! Placing the station at i + r still covers i, but it covers [i, i+2r], drastically maximizing the benefit for upcoming cities. Failing to be greedy in this placement will result in suboptimal usage of k.

Interview preparation tip

For the Maximize the Minimum Powered City interview pattern, the hardest part is maintaining the sliding window of newly added power inside the binary search validation. Use a queue or a separate array to track new_stations[placement_index]. As your scanner i moves forward, subtract stations that fall out of the i - r window from your running power total. This keeps your validation function strictly $O(N)$.