2618. Maximize the Minimum Powered City
My accepted Python solution to LeetCode problem 2618, Maximize the Minimum Powered City, running in 2737ms.
- Difficulty: Hard
- Python
- Runtime 2737ms
- Memory 40.7MB
- Updated
Read the problem on LeetCode View on GitHub
The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.
Python
Accepted on LeetCode — runtime 2737ms, memory 40.7MB, accepted 2025-12-31.
class Solution:
def maxPower(self, stations: List[int], r: int, k: int) -> int:
n = len(stations)
# Pre-calculate power for each city using prefix sum
prefix = [0] * (n + 1)
for i in range(n):
prefix[i + 1] = prefix[i] + stations[i]
def getPower(i):
left = max(0, i - r)
right = min(n - 1, i + r)
return prefix[right + 1] - prefix[left]
# Initial power for each city
power = [getPower(i) for i in range(n)]
def canAchieve(minPower):
# Check if we can achieve minimum power 'minPower' for all cities
p = power[:] # Copy of power array
added = 0
diff = [0] * (n + 1) # Difference array for range updates
for i in range(n):
p[i] += diff[i]
if i > 0:
diff[i] += diff[i - 1] - (diff[i - 1] if i == 0 else 0)
p[i] = power[i] + diff[i]
if p[i] < minPower:
need = minPower - p[i]
added += need
if added > k:
return False
# Add at position min(i + r, n - 1), affects [i, min(i + 2*r, n-1)]
p[i] += need
rightEnd = min(i + 2 * r + 1, n)
diff[i] += need
if rightEnd < n:
diff[rightEnd] -= need
return added <= k
# Binary search
left, right = min(power), max(power) + k
while left < right:
mid = (left + right + 1) // 2
if canAchieve(mid):
left = mid
else:
right = mid - 1
return left