Maximize the Minimum Powered City — LeetCode 2528 Python Solution
HardGreedyQueueArrayBinary SearchPrefix SumSliding Window
- Problem
- #2528
- Pattern
- Sliding Window
- Reading time
- 6 min
- Source
- leetcode.com
The problem
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.
Example
- 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.
Python solution
Python
class Solution:
def maxPower(self, stations: List[int], r: int, k: int) -> int:
def check(x, k):
d = [0] * (n + 1)
t = 0
for i in range(n):
t += d[i]
dist = x - (s[i] + t)
if dist > 0:
if k < dist:
return False
k -= dist
j = min(i + r, n - 1)
left, right = max(0, j - r), min(j + r, n - 1)
d[left] += dist
d[right + 1] -= dist
t += dist
return True
n = len(stations)
d = [0] * (n + 1)
for i, v in enumerate(stations):
left, right = max(0, i - r), min(i + r, n - 1)
d[left] += v
d[right + 1] -= v
s = list(accumulate(d))
left, right = 0, 1 << 40
while left < right:
mid = (left + right + 1) >> 1
if check(mid, k):
left = mid
else:
right = mid - 1
return leftComplexity
| Measure | Complexity |
|---|---|
| Time | O(n \times \log M) |
| Space | O(n) auxiliary |
Pattern: Sliding Window
Collapse a nested loop over every subarray into a single pass with two indices. LeetCode 2528. Maximize the Minimum Powered City is filed here because LeetCode tags it Sliding Window, which is the vocabulary this hub collects.
The sliding window guide has the Python template for the pattern and the 116 LeetCode problems that use it.
Related problems
LeetCode 1838Frequency of the Most Frequent ElementMediumLeetCode 2271Maximum White Tiles Covered by a CarpetMediumLeetCode 1703Minimum Adjacent Swaps for K Consecutive OnesHardLeetCode 2071Maximum Number of Tasks You Can AssignHardLeetCode 2234Maximum Total Beauty of the GardensHardLeetCode 611Valid Triangle NumberMedium
Frequently asked questions
- How hard is LeetCode 2528. Maximize the Minimum Powered City?
- LeetCode 2528. Maximize the Minimum Powered City is rated Hard on LeetCode.
- What is the time complexity of LeetCode 2528. Maximize the Minimum Powered City?
- The Python solution on this page runs in O(n \times \log M).
- What is the space complexity of LeetCode 2528. Maximize the Minimum Powered City?
- The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 2528. Maximize the Minimum Powered City cover?
- LeetCode 2528. Maximize the Minimum Powered City is tagged Greedy, Queue, Array, Binary Search, Prefix Sum and Sliding Window on LeetCode.