Skip to main content
Talentd

Maximal Score After Applying K Operations - Solution & Explanation

MediumArrayGreedyHeap (Priority Queue)12 min readAsked at: Amazon, Visa, Google +3
Practice this problem

Problem Statement

You are given a 0-indexed integer array nums and an integer k. You have a starting score of 0.

In one operation:

  1. choose an index i such that 0 <= i < nums.length,
  2. increase your score by nums[i], and
  3. replace nums[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 <= 105
  • 1 <= nums[i] <= 109

Approach Overview

Problem 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.

Approach 1: Heap (Priority Queue) Method

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.

Code

PythonJavaScriptC++

Python

JavaScript

C++

Complexity

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.

Try this approach in the editor →

Approach 2: Sort and Greedy Method

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.

Code

JavaC#

Java

C#

Complexity

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.

Try this approach in the editor →

Approach 3: Priority Queue (Max Heap)

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.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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.
Space Complexity: O(n) - Due to the heap storage.

Sort and Greedy Method

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.

Priority Queue (Max Heap)—

Detailed Complexity Analysis

ApproachTimeSpaceWhen 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 GreedyO(n log n + kn)O(1)–O(n)Works for smaller inputs or when avoiding additional data structures

Video Solution

Maximal Score After Applying K Operations - Leetcode 2530 - Python • NeetCodeIO • 7,522 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Maximal Score After Applying K Operations easy or hard?
The problem is rated Medium on LeetCode with an acceptance rate around 63%. The greedy idea is straightforward, but recognizing that a max heap is needed to efficiently repeat the operation k times is the key insight.
Maximal Score After Applying K Operations Python/Java solution
Most implementations use a priority queue. Python typically uses heapq with negated values to simulate a max heap, while Java uses PriorityQueue with a custom comparator. JavaScript and C++ also provide efficient heap structures for the same O(k log n) approach.
How to solve Maximal Score After Applying K Operations in O(k log n)?
Use a max heap to always access the largest value in the array. Push all elements into the heap, repeat k times: pop the maximum, add it to the score, compute ceil(value / 3), and push the result back. Each iteration takes O(log n).
What is the best approach for Maximal Score After Applying K Operations?
The optimal approach uses a max heap (priority queue). Insert all numbers into the heap, repeatedly extract the largest value, add it to the score, then push back ceil(value / 3). Each operation costs O(log n), so the overall complexity is O((n + k) log n).
Is Maximal Score After Applying K Operations asked at Google/Amazon/Meta?
Greedy + heap problems similar to this appear frequently in interviews at companies like Amazon, Google, and Meta. The pattern of repeatedly selecting the maximum element with a priority queue is a common interview theme.
What data structure is used in Maximal Score After Applying K Operations?
A max heap (priority queue) is the primary data structure. It allows efficient extraction of the largest value and reinsertion after updating the element, keeping operations at O(log n).
What is the time complexity of Maximal Score After Applying K Operations?
The heap-based solution runs in O((n + k) log n) time because building the heap takes O(n) and each of the k operations performs a pop and push, both O(log n). Space complexity is O(n) for storing elements in the heap.

Ready to solve this problem?

Practice Maximal Score After Applying K Operations with our built-in code editor and test cases.

Practice on FleetCode
Previous

Remove Stones to Minimize the Total

Next

Sliding Window Maximum