You are given a 0-indexed integer array nums and an integer k. You have a starting score of 0.
In one operation:
i such that 0 <= i < nums.length,nums[i], andnums[i] with ceil(nums[i] / 3).Return the maximum possible score you can attain after applying exactly k operations.
The ceiling function ceil(val) is the least integer greater than or equal to val.
Example 1:
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.
Example 2:
Input: nums = [1,10,3,3,3], k = 3 Output: 17 Explanation: You can do the following operations: Operation 1: Select i = 1, so nums becomes [1,4,3,3,3]. Your score increases by 10. Operation 2: Select i = 1, so nums becomes [1,2,3,3,3]. Your score increases by 4. Operation 3: Select i = 2, so nums becomes [1,2,1,3,3]. Your score increases by 3. The final score is 10 + 4 + 3 = 17.
Constraints:
1 <= nums.length, k <= 1051 <= nums[i] <= 109Problem Overview: You are given an integer array nums and an integer k. For exactly k operations, choose the largest value in the array, add it to the score, then replace that value with ceil(value / 3). The goal is to maximize the total score after all operations.
Approach 1: Heap (Priority Queue) Method (Time: O((n + k) log n), Space: O(n))
This problem naturally fits a greedy strategy: always take the largest available number because it contributes the most to the score at that moment. A max heap makes this efficient. First push all elements of nums into a max heap. Then repeat k times: extract the largest value, add it to the running score, compute ceil(value / 3), and push the reduced value back into the heap. Each extraction and insertion costs O(log n), so the total work for k operations is O(k log n). The heap stores at most n elements, giving O(n) space usage. This approach handles large k efficiently and keeps the largest candidate accessible at all times. See related concepts in Heap (Priority Queue) and Greedy.
Approach 2: Sort and Greedy Method (Time: O(n log n + kn), Space: O(1) or O(n))
Another way is to keep the array sorted so the largest element is always at the end. Start by sorting nums in ascending order. For each of the k operations, take the largest element, add it to the score, replace it with ceil(value / 3), then reinsert the new value into the correct sorted position. Finding the position can be done with binary search in O(log n), but shifting elements to maintain sorted order costs O(n). Over k iterations, this leads to O(kn) time after the initial sort. Space complexity stays O(1) if sorting in place. This method works for moderate input sizes but becomes inefficient when k is large.
The greedy insight is straightforward: delaying the use of the largest value never increases the final score because every operation reduces the chosen value. Using the maximum immediately always yields the best marginal gain.
Recommended for interviews: The heap-based solution is the expected answer. It shows you recognize a repeated “extract max and update” pattern and apply a priority queue to keep operations efficient. Mentioning the sorted-array alternative demonstrates understanding of the greedy idea, but the heap implementation proves you can optimize it properly.
By using a max-heap (priority queue), we can efficiently select the largest element from the array in each operation. This strategy maximizes the immediate score increase. Once an element is chosen, reinsert it into the heap with its updated value (after applying the ceiling function of division by 3) so it can be considered for future operations.
The code uses a max-heap to choose the current largest value in each of the k operations, updating the score and reinserting the modified element efficiently.
Python
JavaScript
C++
Time Complexity: O(k log n) - Each heap operation (insert/extract) takes O(log n) and we perform it 'k' times.
Space Complexity: O(n) - Due to the heap storage.
Sort the array in descending order and apply the operation greedily by always picking elements from the start of the array for maximum immediate score increase. Re-insert the updated elements after processing through their div-3 transformation.
In Java, we utilize a priority queue configured for descending order to ensure the extraction of the current highest integer for scoring before updating and reinserting it.
Time Complexity: O(k log n) - Efficient dealing with priorities during extraction and insertion.
Space Complexity: O(n) - Storing elements in the priority queue for processing.
To maximize the sum of scores, we need to select the element with the maximum value at each step. Therefore, we can use a priority queue (max heap) to maintain the element with the maximum value.
At each step, we take out the element with the maximum value v from the priority queue, add v to the answer, and replace v with \lceil \frac{v}{3} \rceil, and then add it to the priority queue. After repeating this process k times, we return the answer.
The time complexity is O(n + k times log n), and the space complexity is O(n) or O(1). Here, n is the length of the array nums.
| Approach | Complexity |
|---|---|
| Heap (Priority Queue) Method | Time Complexity: O(k log n) - Each heap operation (insert/extract) takes O(log n) and we perform it 'k' times. |
| Sort and Greedy Method | Time Complexity: O(k log n) - Efficient dealing with priorities during extraction and insertion. |
| Priority Queue (Max Heap) | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Heap (Priority Queue) | O((n + k) log n) | O(n) | Best general solution when repeatedly extracting and updating the maximum value |
| Sort and Greedy | O(n log n + kn) | O(1)–O(n) | Works for smaller inputs or when avoiding additional data structures |
Maximal Score After Applying K Operations - Leetcode 2530 - Python • NeetCodeIO • 7,408 views views
Watch 9 more video solutions →Practice Maximal Score After Applying K Operations with our built-in code editor and test cases.
Practice on FleetCode