We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximize the Minimum Powered City

Number: 2618

Difficulty: Hard

Paid? No

Companies: N/A

Problem Description

Given an array stations where each element represents the number of power stations in a city, and an integer r representing the range of each station, each power station provides power to every city within distance r. The power of a city is the total number of stations that supply power to it. You are allowed to build k additional power stations at any cities. Your goal is to maximize the minimum power across all cities after optimally installing these additional stations.

Key Insights

  • Use a sliding window (via prefix sum) to efficiently compute the initial power available at each city.
  • Binary search over the possible minimum power values to decide the achievable power level.
  • For each candidate power value, simulate the augmentation using a greedy approach combined with a difference array to add stations in the range where needed.
  • Ensure the simulation updates the window contributions efficiently to maintain an overall O(n) check per candidate value.

Space and Time Complexity

Time Complexity: O(n * log(max_possible_power)), where n is the number of cities. Space Complexity: O(n) for the extra arrays (prefix/difference arrays).

Solution

The solution involves two main steps:

  1. Precompute the initial power for each city using a sliding window approach. This gives the sum of contributions from stations affecting that city.
  2. Use binary search to determine the maximum achievable minimum power. For each candidate minimum power, simulate placing additional stations greedily:
    • Use a difference array to apply the effect of added stations quickly over the relevant range.
    • If a city's power (initial power plus cumulative additions) falls short of the target, then add enough stations locally and propagate their effect using the difference array.
    • If the total extra added stations exceed k, the candidate minimum power is infeasible; otherwise, it is feasible. Adjust the binary search range accordingly to find the maximum minimum power achievable.

Code Solutions

# Python solution for "Maximize the Minimum Powered City"
class Solution:
    def maxPower(self, stations, r, k):
        n = len(stations)
        # Compute initial power for each city using a sliding window approach.
        window = [0] * n
        total = 0
        # Initialize the sum for the first window [0, r]
        for i in range(min(n, r + 1)):
            total += stations[i]
        for i in range(n):
            # Include station at the right end of the window if in bounds.
            if i + r < n:
                total += stations[i + r] if (i + r) < n else 0
            # Subtract station that goes out of range on the left.
            if i - r - 1 >= 0:
                total -= stations[i - r - 1]
            window[i] = total

        # Define the helper function that checks if a candidate min power is feasible.
        def is_feasible(min_power):
            used = 0  # Count of additional stations used
            cur_add = 0  # Running sum of applied additional stations effect
            diff = [0] * (n + 1)  # Difference array for additional stations effects
            for i in range(n):
                cur_add += diff[i]
                current_power = window[i] + cur_add
                if current_power < min_power:
                    needed = min_power - current_power
                    used += needed
                    if used > k:
                        return False
                    cur_add += needed
                    # Mark the endpoint where the effect of these added stations ends
                    if i + 2 * r + 1 < n:
                        diff[i + 2 * r + 1] -= needed
            return True

        # Binary search for the maximum achievable minimum power.
        low, high = min(window), min(window) + k
        result = low
        while low <= high:
            mid = (low + high) // 2
            if is_feasible(mid):
                result = mid
                low = mid + 1
            else:
                high = mid - 1
        return result

# Sample run:
# sol = Solution()
# print(sol.maxPower([1,2,4,5,0], 1, 2))  # Expected output: 5
← Back to All Questions