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.

Maximal Score After Applying K Operations — LeetCode 2530 Python Solution

MediumGreedyArrayHeap (Priority Queue)

Problem: #2530
Pattern: 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

Python

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 ans

Complexity

Measure	Complexity
Time	O(n + k \times \log n)
Space	O(n) or O(1) auxiliary

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.

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.