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 power station can provide power to every city in a fixed range. In other words, if the range is denoted by r, then a power station at city i can provide power to all cities j such that |i - j| <= r and 0 <= i, j <= n - 1.
|x| denotes absolute value. For example, |7 - 5| = 2 and |3 - 10| = 7.The power of a city is the total number of power stations it is being provided power from.
The government has sanctioned building k more power stations, each of which can be built in any city, and have the same range as the pre-existing ones.
Given the two integers r and k, return the maximum possible minimum power of a city, if the additional power stations are built optimally.
Note that you can build the k power stations in multiple cities.
Example 1:
Input: stations = [1,2,4,5,0], r = 1, k = 2 Output: 5 Explanation: 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 Explanation: It can be proved that we cannot make the minimum power of a city greater than 4.
Constraints:
n == stations.length1 <= n <= 1050 <= stations[i] <= 1050 <= r <= n - 10 <= k <= 109The idea is to use binary search to find the maximum possible minimum power. Define a function that uses a sliding window to check if it's possible to achieve a certain power level. For each mid value (current candidate for maximum minimum power), try to distribute the additional stations optimally to ensure that every city has at least this power level.
This approach defines a binary search on the value of the possible minimum power, and uses a helper function, canAchieve, to check if a given power level can be achieved using the sliding window technique and a temporary array add to track changes.
C++
Java
Python
C#
JavaScript
Time complexity: O(n log(maxStations)) where n is the number of cities and maxStations is the initial range considered.
Space complexity: O(n) for the additional working space.
In this approach, consider iterating from the city with the lowest current power. Utilizing a greedy strategy, try to place power stations in such a way that you're filling the "gaps". Adjust the current power array as stations are added, and track the distribution to maintain a greedy but strategic placement of available stations to maximize the power efficiently.
This simple greedy implementation uses a sorting mechanism to adjust city powers by placing new stations where they're most needed. The adjustment aims to keep all cities as balanced as possible as early as possible.
C++
Java
Python
C#
JavaScript
Time complexity: O(n log n) due to sorting.
Space complexity: O(1) as changes are made directly on the input array.
| Approach | Complexity |
|---|---|
| Approach 1: Binary Search with Sliding Window | Time complexity: O(n log(maxStations)) where n is the number of cities and maxStations is the initial range considered. |
| Approach 2: Greedy Placement to Maximize Minimum Power | Time complexity: O(n log n) due to sorting. |
I solved too many Leetcode problems • NeetCodeIO • 101,495 views views
Watch 9 more video solutions →Practice Maximize the Minimum Powered City with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor