2528. Maximize the Minimum Powered City
Approach
Binary search on minimum power; prefix sums + greedy placement of added stations.
Key Techniques
Array problems involve manipulating elements stored in a contiguous block of memory. Key techniques include two-pointer traversal, prefix sums, sliding windows, and in-place partitioning. In C#, arrays are zero-indexed and fixed in size — use List<T> when you need dynamic resizing.
Binary search reduces search space by half each step, giving O(log n) time. Beyond sorted arrays, apply it on the answer space ("binary search on result") when you can define a monotonic predicate — e.g., "can we achieve X with k resources?"
Greedy algorithms make locally optimal choices at each step, hoping to reach a global optimum. Greedy works when a problem has the "greedy choice property" and "optimal substructure". Common applications: interval scheduling, activity selection, Huffman coding, and jump game.
// Approach: Binary search on minimum power; prefix sums + greedy placement of added stations.
// Time: O(n log(sum)) Space: O(n)
public class Solution
{
public long MaxPower(int[] stations, int r, int k)
{
long left = stations.Min();
long right = stations.Select(s => (long)s).Sum() + k + 1;
while (left < right)
{
long mid = (left + right) / 2;
if (Check((int[])stations.Clone(), r, k, mid))
left = mid + 1;
else
right = mid;
}
return left - 1;
}
// Returns true if each city can have at least `minPower`.
private bool Check(int[] stations, int r, int additionalStations, long minPower)
{
int n = stations.Length;
long power = 0;
for (int i = 0; i < r; ++i)
power += stations[i];
for (int i = 0; i < n; ++i)
{
if (i + r < n)
power += stations[i + r]; // power = sum(stations[i - r..i + r])
if (power < minPower)
{
long requiredPower = minPower - power;
if (requiredPower > additionalStations)
return false;
stations[Math.Min(n - 1, i + r)] += (int)requiredPower;
additionalStations -= (int)requiredPower;
power += requiredPower;
}
if (i - r >= 0)
power -= stations[i - r];
}
return true;
}
}