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] <= 109By 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.
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.
C#
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.
| 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. |
Maximal Score After Applying K Operations - Leetcode 2530 - Python • NeetCodeIO • 7,034 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