2528. Maximize the Minimum Powered City

HardGreedyQueueArrayBinary SearchPrefix SumSliding Window
Leetcode Link

Problem Description

In this problem, we are given an array stations that represents the number of power stations in each city of a series of cities indexed from 0 to n-1. Every power station has a range r that determines the cities it can supply power to. A power station in city i can supply power to any city j such that the absolute difference |i - j| is less than or equal to r.

The power of a city is defined as the sum of power stations providing power to it, considering the range of the power stations. We are given a number k representing the number of additional power stations that can be built.

Our task is to find the maximum possible minimum power across all cities after building k additional power stations in the most optimal manner. In simpler terms, we want to increase the minimum power of the cities to the highest possible value by strategically placing the new power stations.

Intuition

To solve this problem, we're going to use a binary search algorithm that tries to find the minimum power value that can be achieved after optimally placing k new power stations. Here's the intuition behind the approach:

  1. Defining the Search Space: The search space will be between 0 and a maximum possible value, which is a large number since the exact upper limit isn't clearly defined in the problem.

  2. Binary Search: Within this search space, we can use binary search to find the maximum possible minimum power. For each attempt (mid value in binary search), we check if we can achieve this minimum power by optimally placing k new power stations.

  3. Feasibility Check: The check function determines if a given minimum power x can be achieved using k additional power stations. This involves, for each city, checking if the existing power plus the power from the new stations meets the target power x. If a city does not meet the target, we add more stations within its range until it does, without exceeding the limit of k new stations.

The solution uses a greedy approach within the check function, always placing new power stations where they are needed most (where the deficit is greatest). If we ever require more than k additional stations to meet the target power for all cities, we know the chosen target power x is not feasible.

  1. Adjusting the Binary Search: If we find that a certain target minimum power x is achievable, it means we might be able to achieve an even higher minimum power, so we go higher in our binary search. On the other hand, if x is not achievable, we need to try a lower value.

  2. Determining the Result: The binary search continues until the range has been narrowed down to the highest minimum power that can be achieved with k additional power stations. This value is then returned as the result.

Learn more about Greedy, Queue, Binary Search, Prefix Sum and Sliding Window patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which of the following shows the order of node visit in a Breadth-first Search?

Solution Approach

The solution uses a combination of binary search and greedy algorithm principles to find the maximum possible minimum power of a city:

  1. Initialization: We first create an additional list d of the same size as the number of cities n. This d list is used to apply a difference array pattern which makes range updates efficient.

  2. Prepare Prefix Sum Array: We then convert d into a prefix sum array s by using the accumulate function from the itertools module in Python. This prefix sum array s allows us to quickly calculate the power of each city from the existing stations.

  3. Binary Search Setup: A binary search is set up with the left (low) boundary as 0 and the right (high) boundary as a large number 1 << 40 to account for the upper limit of the power that can be achieved.

  4. Binary Search Execution: In each iteration of binary search, we calculate the middle value mid between the current left and right boundaries, and we then check if it's possible to achieve this middle value as the minimum power, using the check function.

  5. Check Function: The check function attempts to distribute the k new power stations among the cities in a way that each city at least gets power equal to x. It uses the strategy of greedily placing new power stations in the cities that are further away from the target power. A running total t represents the extra power provided on top of what the prefix sum array s provides. The function updates the difference array d to account for the new stations, effectively spreading their range over the cities.

  6. Adjust the Search Range: If the check function confirms that x is achievable, the left (low) boundary of the search range is updated to mid. If not, the right (high) boundary is updated to mid - 1. This narrows down the search space to find the highest minimum power that is achievable.

  7. Finding the Result: Once the binary search is completed, and the left and right boundaries have converged, the solution returns the left boundary, which represents the maximum possible minimum power after the additional k power stations are optimally distributed.

The solution extensively uses the difference array pattern to efficiently handle range updates and queries by converting the initial array into a differential array and using a prefix sum to maintain the range updates. This combination with binary search solves the problem by repeatedly trying different power values until the highest possible minimum power is found to be achievable with k new power stations.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

The three-steps of Depth First Search are:

  1. Identify states;
  2. Draw the state-space tree;
  3. DFS on the state-space tree.

Example Walkthrough

Let's consider an example where the array stations is [1,0,2,0,1], representing the number of power stations in five cities, and each power station has a range r of 1. Additionally, we are given k = 2, meaning we can build 2 additional power stations.

  • Step 1: Initialization Begin with a difference array (which we'll call d) of the same size: [1, 0, 2, 0, 1].

  • Step 2: Prepare Prefix Sum Array Convert d into a prefix sum array s. In our case, s would be [1, 1, 3, 3, 4]. This represents the total number of power stations affecting each city.

  • Step 3: Binary Search Setup Set the search space: left = 0 and right = 1 << 40 (a large number).

  • Step 4 & 5: Binary Search Execution and Check Function Perform binary search:

    • First Iteration:
      • mid = (left + right) / 2 is very large; assume it's larger than the sum of all power stations plus k.
      • The check function will find that this mid value is not achievable with k = 2.
      • Set right = mid - 1.
    • Second Iteration:
      • Find a new mid.
      • Binary search narrows down to a reasonable guess, say mid = 3.
      • The check function tries to achieve at least 3 power for each city with the aid of k = 2 additional stations:
        • For city 0, already has power = 1; needs 2 more (deficit is 2).
        • For city 1, already has power = 1; needs 2 more (deficit is 2).
        • We place one additional station in city 1 (with range r = 1), augmenting the power of cities 0, 1, and 2.
        • Now, cities 0, 1, 2 all have power at least 3, so no deficit. Remaining k = 1.
        • For city 3, has power = 3; needs 0 more (no deficit).
        • For city 4, has power = 4; already meets the requirement.
      • The check function confirms that each city has a power of at least 3 with 1 additional station remaining. This is achievable.
      • Set left = mid.

Continue the binary search adjusting left and right until they converge, finding the highest achievable minimum power value with the addition of k stations.

  • Step 6 & 7: Adjust the Search Range and Find the Result Once the binary search is conclusive:
    • left and right converge to the maximum minimum power achievable. Let's say in our example, it converges at 3. So, 3 is the maximum possible minimum power that can be achieved by optimally placing 2 additional power stations.

Thus, if the problem asked for the maximum possible minimum power of a city after building 2 additional power stations with a range of 1, our answer, in this case, would be 3.

Solution Implementation

1from itertools import accumulate
2
3class Solution:
4    def max_power(self, stations: List[int], range_limit: int, power_units: int) -> int:
5        # Helper function to check if it's possible to achieve at least 'target_power' using
6        # at most 'available_units' of power units.
7        def is_feasible(target_power: int, available_units: int) -> bool:
8            delta = [0] * (total_stations + 1)
9            total_power = 0
10            for i in range(total_stations):
11                total_power += delta[i]
12                required_power = target_power - (current_power[i] + total_power)
13                if required_power > 0:
14                    if available_units < required_power:
15                        return False
16                    available_units -= required_power
17                    j = min(i + range_limit, total_stations - 1)
18                    left, right = max(0, j - range_limit), min(j + range_limit, total_stations - 1)
19                    delta[left] += required_power
20                    delta[right + 1] -= required_power
21                    total_power += required_power
22            return True
23
24        total_stations = len(stations)
25        delta = [0] * (total_stations + 1)
26      
27        # Precompute the power at each station after applying the initial power units
28        for i, power in enumerate(stations):
29            left, right = max(0, i - range_limit), min(i + range_limit, total_stations - 1)
30            delta[left] += power
31            delta[right + 1] -= power
32        current_power = list(accumulate(delta))
33      
34        # Binary search for the maximum power that can be achieved using given power units
35        left, right = 0, 1 << 40  # Using a large right value to ensure it's greater than the maximum achievable power
36        while left < right:
37            mid = (left + right + 1) >> 1  # Calculate mid and round up to ensure we don't get stuck in an infinite loop
38            if is_feasible(mid, power_units):
39                left = mid
40            else:
41                right = mid - 1
42      
43        # The final answer, which is the maximum power that can be achieved
44        return left
45
1class Solution {
2    private long[] prefixSum; // To hold the running prefix sums of power values.
3    private long[] diff; // To represent the difference array for doing range updates.
4    private int stationCount; // The number of stations.
5
6    // Primary function to calculate the maximum power using binary search.
7    public long maxPower(int[] stations, int radius, int k) {
8        stationCount = stations.length;
9        diff = new long[stationCount + 1];
10        prefixSum = new long[stationCount + 1];
11        // Initialize the differencing array based on the power ranges of each station.
12        for (int i = 0; i < stationCount; ++i) {
13            int left = Math.max(0, i - radius), right = Math.min(i + radius, stationCount - 1);
14            diff[left] += stations[i];
15            diff[right + 1] -= stations[i];
16        }
17        // Construct the prefixSum array from the diff array.
18        prefixSum[0] = diff[0];
19        for (int i = 1; i < stationCount + 1; ++i) {
20            prefixSum[i] = prefixSum[i - 1] + diff[i];
21        }
22        // Binary search to determine the maximum power.
23        long left = 0, right = 1L << 40;
24        while (left < right) {
25            long mid = (left + right + 1) >>> 1; // unsigned division by 2.
26            // If the current power level is possible, explore higher power.
27            if (check(mid, radius, k)) {
28                left = mid;
29            } else {
30                // Otherwise, explore lower power.
31                right = mid - 1;
32            }
33        }
34        return left;
35    }
36
37    // Helper function to check if the given power level is attainable.
38    private boolean check(long power, int radius, int k) {
39        // Reset the difference array for this check.
40        Arrays.fill(diff, 0);
41        long tempSum = 0; // To keep track of the current increments.
42      
43        for (int i = 0; i < stationCount; ++i) {
44            tempSum += diff[i];
45            // Calculate how much more power is needed to reach the "power" target.
46            long requiredPower = power - (prefixSum[i] + tempSum);
47            // If additional power is required.
48            if (requiredPower > 0) {
49                // Check if we have enough power bombs to meet the requirement.
50                if (k < requiredPower) {
51                    return false;
52                }
53                // Use the power bombs to increase the power of the range.
54                k -= requiredPower;
55                // Update the effective range in the difference array.
56                int j = Math.min(i + radius, stationCount - 1);
57                int left = Math.max(0, j - radius);
58                int right = Math.min(j + radius, stationCount - 1);
59                diff[left] += requiredPower;
60                diff[right + 1] -= requiredPower;
61                // Update the current sum with the additional power.
62                tempSum += requiredPower;
63            }
64        }
65        // If we've made it through the loop, the power level is attainable.
66        return true;
67    }
68}
69
1#include <vector>
2#include <cstring> // for memset
3#include <algorithm> // for max and min functions
4
5class Solution {
6public:
7    long long maxPower(std::vector<int>& stations, int radius, int limit) {
8        int stationCount = stations.size();
9        std::vector<long long> delta(stationCount + 1, 0);
10        // Calculate the initial power distribution with the given stations
11        for (int i = 0; i < stationCount; ++i) {
12            int leftBoundary = std::max(0, i - radius);
13            int rightBoundary = std::min(i + radius, stationCount - 1);
14            delta[leftBoundary] += stations[i];
15            delta[rightBoundary + 1] -= stations[i];
16        }
17        // Compute the prefix sum to get the power at each station
18        std::vector<long long> prefixSum(stationCount + 1, 0);
19        prefixSum[0] = delta[0];
20        for (int i = 1; i <= stationCount; ++i) {
21            prefixSum[i] = prefixSum[i - 1] + delta[i];
22        }
23        // Lambda function to check if a certain power level x is achievable
24        auto checkFeasibility = [&](long long x, int remainingBoosts) {
25            std::vector<long long> adjustments(delta.size(), 0);
26            long long appliedAdjustment = 0;
27            for (int i = 0; i < stationCount; ++i) {
28                appliedAdjustment += adjustments[i];
29                long long shortfall = x - (prefixSum[i] + appliedAdjustment);
30                if (shortfall > 0) {
31                    // If we don't have enough boosts to meet the shortfall, return false
32                    if (remainingBoosts < shortfall) {
33                        return false;
34                    }
35                    // Allocate boosts to cover the shortfall
36                    remainingBoosts -= shortfall;
37                    int boostEnd = std::min(i + radius, stationCount - 1);
38                    int adjLeft = std::max(0, boostEnd - radius);
39                    int adjRight = std::min(boostEnd + radius, stationCount - 1);
40                    adjustments[adjLeft] += shortfall;
41                    adjustments[adjRight + 1] -= shortfall;
42                    appliedAdjustment += shortfall;
43                }
44            }
45            return true;
46        };
47        // Binary search to find the maximum power level achievable
48        long long low = 0, high = 1e12;
49        while (low < high) {
50            long long mid = (low + high + 1) >> 1;
51            if (checkFeasibility(mid, limit)) {
52                low = mid; // If achievable, we can go higher
53            } else {
54                high = mid - 1; // Otherwise, we need to go lower
55            }
56        }
57        return low;
58    }
59};
60
1// Importing required functions from lodash
2import { max, min } from 'lodash';
3
4// Function to compute the maximum power possible given stations, radius, and limit
5function maxPower(stations: number[], radius: number, limit: number): number {
6    const stationCount: number = stations.length;
7    const delta: number[] = new Array(stationCount + 1).fill(0);
8
9    // Calculate the initial power distribution with the given stations
10    for (let i = 0; i < stationCount; ++i) {
11        const leftBoundary = max([0, i - radius]);
12        const rightBoundary = min([i + radius, stationCount - 1]);
13        delta[leftBoundary] += stations[i];
14        delta[rightBoundary + 1] -= stations[i];
15    }
16
17    // Compute the prefix sum to get the power at each station
18    const prefixSum: number[] = new Array(stationCount + 1).fill(0);
19    prefixSum[0] = delta[0];
20    for (let i = 1; i <= stationCount; ++i) {
21        prefixSum[i] = prefixSum[i - 1] + delta[i];
22    }
23
24    // Lambda function to check if a certain power level `x` is achievable
25    const checkFeasibility = (x: number, remainingBoosts: number): boolean => {
26        const adjustments: number[] = new Array(delta.length).fill(0);
27        let appliedAdjustment: number = 0;
28        for (let i = 0; i < stationCount; ++i) {
29            appliedAdjustment += adjustments[i];
30            const shortfall = x - (prefixSum[i] + appliedAdjustment);
31            if (shortfall > 0) {
32                // If we don't have enough boosts to meet the shortfall, return false
33                if (remainingBoosts < shortfall) {
34                    return false;
35                }
36                // Allocate boosts to cover the shortfall
37                remainingBoosts -= shortfall;
38                const boostEnd = min([i + radius, stationCount - 1]);
39                const adjLeft = max([0, boostEnd - radius]);
40                const adjRight = min([boostEnd + radius, stationCount - 1]);
41                adjustments[adjLeft] += shortfall;
42                adjustments[adjRight + 1] -= shortfall;
43                appliedAdjustment += shortfall;
44            }
45        }
46        return true;
47    };
48
49    // Binary search to find the maximum power level achievable
50    let low: number = 0;
51    let high: number = 1e12;
52    while (low < high) {
53        const mid: number = Math.floor((low + high + 1) / 2);
54        if (checkFeasibility(mid, limit)) {
55            low = mid; // If achievable, we can go higher
56        } else {
57            high = mid - 1; // Otherwise, we need to go lower
58        }
59    }
60    return low;
61}
62
63// Example usage
64const result = maxPower([1, 2, 3], 1, 2);
65console.log(result);
66
Not Sure What to Study? Take the 2-min Quiz：

Which of the following is equvalent to O(3*2^n + n^3 + n!+ log n)?

Time and Space Complexity

Time Complexity

The time complexity of the code is determined by the operations performed in each function. Let's break them down:

  1. The check function: It has a loop that runs n times, where n is the number of stations. Within the loop, there are constant-time operations except for the calculations for j, left, and right. These are also constant-time since they involve arithmetic operations. The inner loop essentially simulates the process r times in the worst case for each station. So the complexity for the check function is O(n).

  2. The binary search loop: The code uses a binary search to find the maximum power x. This binary search runs until left becomes equal to right. In each iteration, it calls the check function which has O(n) complexity. The binary search will at most execute log2(1 << 40) times, which simplifies to log2(2^40) = 40 times. Hence, overall the time complexity for this part is O(n * logC), where logC represents the logarithm of the constant 1 << 40, which is the upper bound of the search space.

Therefore, the total time complexity of the code is O(n * logC).

Space Complexity

The space complexity mainly involves space for the list d of length n + 1, the accumulated sum list s, and some constant space for variables. We do not count the input size towards space complexity. Therefore, the space complexity is O(n).

In summary, the time complexity is O(n * logC) and the space complexity is O(n).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following shows the order of node visit in a Breadth-first Search?

Recommended Readings

Greedy Introduction

Greedy Introduction iframe width 560 height 315 src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you

Queue Intro

Queue Intro Think of the last time you stood in line to buy movie tickets The first person in line gets their ticket first and any newcomers join the end of the line This system where the first person to arrive is the first to be served is a queue in real

Binary Search Speedrun

Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫