MediumNo. 2530
Maximal Score After Applying K Operations — LeetCode 2530 Python Solution
- Pattern
- Heap / Priority Queue
- Topics
- Greedy, Array, Heap (Priority Queue)
- Reading time
- 2 min
- Source
- leetcode.com
The problem
You are given a 0-indexed integer array nums and an integer k. You have a starting score of 0.
Example
- Input
- nums = [10,10,10,10,10], k = 5
- Output
- 50
- Explanation
- Apply the operation to each array element exactly once. The final score is 10 + 10 + 10 + 10 + 10 = 50.
Python solution
class Solution:
def maxKelements(self, nums: List[int], k: int) -> int:
h = [-v for v in nums]
heapify(h)
ans = 0
for _ in range(k):
v = -heappop(h)
ans += v
heappush(h, -(ceil(v / 3)))
return ansComplexity
- Time
- O(n + k × log n)
- Space · auxiliary
- O(n) or O(1)
Pattern: Heap / Priority Queue
Keep only the best k elements, or always pull the smallest, in log time. LeetCode 2530. Maximal Score After Applying K Operations is filed here because LeetCode tags it Heap (Priority Queue), which is the vocabulary this hub collects.
The heap / priority queue guide has the Python template for the pattern and the 163 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0502 | IPO | Hard |
| 0630 | Course Schedule III | Hard |
| 0857 | Minimum Cost to Hire K Workers | Hard |
| 1353 | Maximum Number of Events That Can Be Attended | Medium |
| 1383 | Maximum Performance of a Team | Hard |
| 1642 | Furthest Building You Can Reach | Medium |
Frequently asked questions
- How hard is LeetCode 2530. Maximal Score After Applying K Operations?
LeetCode 2530. Maximal Score After Applying K Operations is rated Medium on LeetCode.
- What topics does LeetCode 2530. Maximal Score After Applying K Operations cover?
LeetCode 2530. Maximal Score After Applying K Operations is tagged Greedy, Array and Heap (Priority Queue) on LeetCode.