2530. Maximal Score After Applying K Operations
Problem Description
You are presented with an integer array nums
and an integer k
, and you start with a score of 0
. In a single operation:
- Choose an index
i
such that0 <= i < nums.length
. - Increase your score by
nums[i]
. - Replace
nums[i]
withceil(nums[i] / 3)
.
The goal is to find the maximum score you can achieve after exactly k
operations. Note that ceil(val)
is the smallest integer greater than or equal to val
.
Here's what you need to remember:
- You can apply operations only
k
times. - You want to maximize your score with these
k
operations.
Intuition
The intuition behind solving this problem comes from the need to maximize the score gained from each operation. To do this, you should always choose the maximum number currently in the array because that will give you the highest possible addition to your score before it gets reduced.
To efficiently track and extract the maximum number at every step, a max heap is ideal. A max heap is a data structure that always allows you to access and remove the largest element in constant time. In Python, you use a min heap by negating the values, as the standard library heapq
module supports only min heap.
Here's the step-by-step reasoning:
- Negate all the values in the array and build a min heap, which simulates a max heap.
- For
k
iterations, do the following:- Pop the heap's top element (the smallest negative number, which is the max in the original array).
- Add the negation of the popped value to your total score (since the heap contains negatives, you negate again to get the original positive value).
- Calculate
ceil(v / 3)
for the popped valuev
, negate it and then push it back to the heap.
By repeating this process k
times, you are each time taking the current maximum value, getting the points from it, and then reducing its value before putting it back into the heap. This allows you to maximize the score at each of the k
steps.
Learn more about Greedy and Heap (Priority Queue) patterns.
Solution Approach
The solution leverages a priority queue, particularly a max heap, to efficiently manage the elements while performing the operations. Since Python's built-in heapq
module provides a min heap implementation, the elements are negated before being added to the heap so that retrieving the element with the maximum value (min heap for the negated values) can be done in constant time.
Here's a breakdown of the solution approach:
-
Initialization: Transform
nums
into a heap in-place by negating its values, effectively creating a max heap. The negative sign is necessary because Python doesn't have a built-in max heap, so this workaround is used (h = [-v for v in nums]
). Then, theheapify
function converts the array into a heap (heapify(h)
). -
Iteration: Repeat the following steps
k
times, corresponding to the number of operations allowed:- Extract (
heappop
) the root of the heap, which is the smallest negative number or the largest number before negation. Then negate it (v = -heappop(h)
) to get back to the original value. - Add this value to
ans
, which keeps track of the score after each operation. - Compute the new value to be inserted back into the heap. The new value is the ceiling of
v / 3
, negated to maintain the correct heap order (heappush(h, -(ceil(v / 3)))
).
- Extract (
-
Scoring & Updating: Each iteration increases the score by the max element's value, and then the heap is updated to reflect the change in the selected element's value post-operation.
By following these steps, the solution ensures that we are always picking the maximum available element, thereby maximizing the score with each operation. After k
iterations, the score ans
is returned, which is the maximum possible score after performing exactly k
operations.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's go through the process with a small example:
Suppose nums = [4, 5, 6]
and k = 2
.
Before we start any operations, we will first negate all the values in nums
to simulate a max heap: [-4, -5, -6]
. Then we convert this array into a heap.
Step 1: Build a Heap
We transform the array into a heap in-place: heapify(h)
makes h = [-6, -5, -4]
.
Step 2: Perform the First Operation
a. We pop the largest element (which is the smallest when negated): v = -heappop(h) => v = 6
(since heappop(h)
gives -6
).
b. We add this value to our score ans
: ans = 0 + 6 = 6
.
c. We calculate the new value for the next heap insert, which is the ceiling of v / 3
and then negate it to maintain the max heap property: heappush(h, -(ceil(6/3))) => heappush(h, -2)
, so h
becomes [-5, -2, -4]
.
Step 3: Perform the Second Operation
a. Again, we pop the largest element from h
: v = -heappop(h) => v = 5
.
b. We add the value to our score: ans = 6 + 5 = 11
.
c. We calculate the new value for the next heap insert: heappush(h, -(ceil(5/3))) => heappush(h, -2)
, and h
now becomes [-4, -2, -2]
.
At this point, we have performed 2
operations, which is our limit k
, so we are done.
Result:
The maximum score that can be achieved after exactly k = 2
operations is 11
. This result comes from choosing the operations that maximize the score at each step, using the heap to efficiently select these operations.
Solution Implementation
1from heapq import heapify, heappop, heappush
2from math import ceil
3from typing import List
4
5class Solution:
6 def maxKElements(self, nums: List[int], k: int) -> int:
7 # Invert the values of the nums array to use the heapq as a min-heap,
8 # since Python's heapq module implements a min-heap instead of a max-heap.
9 min_heap = [-value for value in nums]
10 heapify(min_heap) # Convert the list into a heap
11
12 total_sum = 0 # Initialize the sum of the max 'k' elements
13
14 # Extract 'k' elements from the heap
15 for _ in range(k):
16 # Pop the smallest (inverted largest) element from the heap
17 # and revert it to its original value
18 value = -heappop(min_heap)
19 total_sum += value # Add the element to the sum
20
21 # Calculate the new value by taking the ceiling division by 3
22 # and push its inverted value onto the heap
23 new_value = -(ceil(value / 3))
24 heappush(min_heap, new_value)
25
26 return total_sum # Return the sum of the extracted elements
27
28# Example usage:
29# solution = Solution()
30# print(solution.maxKElements([4, 5, 6], 3))
31
1class Solution {
2 // Method to find the maximum sum of k elements with each element replaced by a third of its value.
3 public long maxKelements(int[] nums, int k) {
4 // Create a max heap using PriorityQueue to store the elements in descending order.
5 PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
6
7 // Add all elements from the array to the max heap.
8 for (int value : nums) {
9 maxHeap.offer(value);
10 }
11
12 // Initialize a variable to store the sum of the maximum k elements.
13 long sum = 0;
14 // Iterate k times to get the sum of the maximum k elements.
15 while (k-- > 0) {
16 // Poll the top element from the max heap (the maximum element).
17 int maxElement = maxHeap.poll();
18 // Add the maximum element to the sum.
19 sum += maxElement;
20 // Replace the maximum element with a third of its value and add it back to the max heap.
21 maxHeap.offer((maxElement + 2) / 3);
22 }
23
24 // Return the sum of the maximum k elements.
25 return sum;
26 }
27}
28
1#include <vector>
2#include <queue>
3
4class Solution {
5public:
6 // Function to calculate the sum of the max 'k' elements following a specific rule
7 long long maxKelements(vector<int>& nums, int k) {
8 // Creating a max priority queue using the elements of 'nums'
9 priority_queue<int> maxHeap(nums.begin(), nums.end());
10
11 // This variable will store the sum of the max 'k' elements
12 long long sum = 0;
13
14 // Iterate 'k' times
15 while (k > 0) {
16 // Retrieve the top element from the max heap (which is the current maximum)
17 int currentValue = maxHeap.top();
18 maxHeap.pop(); // Remove the top element
19
20 sum += currentValue; // Add the current maximum to the sum
21
22 // Apply the rule: replace the extracted value with (value + 2) / 3
23 int newValue = (currentValue + 2) / 3;
24 maxHeap.push(newValue); // Push the new value back into the max heap
25
26 k--; // Decrement the counter
27 }
28
29 // Return the calculated sum
30 return sum;
31 }
32};
33
1import { MaxPriorityQueue } from '@datastructures-js/priority-queue'; // assuming required package is imported
2
3/**
4 * Function to compute the sum of the 'k' maximum elements after each is replaced
5 * with the flooring result of that element plus two, divided by three.
6 *
7 * @param nums Array of numbers from which we are finding the max 'k' elements.
8 * @param k The number of maximum elements we want to sum.
9 * @return The sum of the 'k' maximum elements.
10 */
11function maxKElements(nums: number[], k: number): number {
12 // Initialize a priority queue to store the numbers.
13 const priorityQueue = new MaxPriorityQueue<number>();
14
15 // Iterate over the array of numbers and enqueue each element into the priority queue.
16 nums.forEach(num => priorityQueue.enqueue(num));
17
18 // Initialize the answer variable to accumulate the sum of max 'k' elements.
19 let sum = 0;
20
21 // Loop to process 'k' elements.
22 while (k > 0) {
23 // Dequeue the largest element from the priority queue.
24 const currentValue = priorityQueue.dequeue().element;
25 // Add the value to the sum.
26 sum += currentValue;
27 // Compute the new value using the specified formula and enqueue it back to the priority queue.
28 priorityQueue.enqueue(Math.floor((currentValue + 2) / 3));
29 // Decrement 'k' to move to the next element.
30 k--;
31 }
32
33 // Return the accumulated sum.
34 return sum;
35}
36
Time and Space Complexity
The time complexity of this function primarily comes from two operations: the heapification of the nums
list and the operations within the loop that runs k
times.
- The
heapify(h)
function takesO(n)
time to create a heap from an array ofn
elements. - Inside the loop, each
heappop(h)
andheappush(h, -(ceil(v / 3)))
operation has a time complexity ofO(log n)
because both operations involve maintaining the heap invariant, which requires a restructuring of the heap. Since these operations are calledk
times, the complexity within the loop isO(k * log n)
.
So, the total time complexity of the function is O(n + k * log n)
, where n
is the length of the nums
list.
Now, let's consider the space complexity. The function uses additional memory for the heap, which is h
in the code. This copy of the list adds a space complexity of O(n)
. If we consider auxiliary space complexity (i.e., not counting space taken up by the input itself), it could be argued that the space complexity is O(1)
because we are reusing the space of the given input list nums
to create the heap h
.
Thus, the space complexity can be O(n)
considering the total space used, including input, or O(1)
if considering only auxiliary space, without the input.
Learn more about how to find time and space complexity quickly using problem constraints.
You are given an array of intervals where intervals[i] = [start_i, end_i]
represent the start and end of the ith
interval. You need to merge all overlapping intervals and return an array of the non-overlapping intervals that cover all the intervals in the input.
Recommended Readings
Greedy Introduction div class responsive iframe iframe src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you to calculate the max min of some value Commonly you may see this phrased in the problem as max min longest shortest largest smallest etc These keywords can be identified by just scanning
https algomonster s3 us east 2 amazonaws com cover_photos heap svg Priority Queue and Heap What is the relationship between priority queue and heap Priority Queue is an Abstract Data Type and Heap is the concrete data structure we use to implement a priority queue Priority Queue A priority queue
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.