Maximum Sum With Exactly K Elements - Solution & Explanation
Problem Statement
You are given a 0-indexed integer array nums and an integer k. Your task is to perform the following operation exactly k times in order to maximize your score:
- Select an element
mfromnums. - Remove the selected element
mfrom the array. - Add a new element with a value of
m + 1to the array. - Increase your score by
m.
Return the maximum score you can achieve after performing the operation exactly k times.
Example 1:
Input: nums = [1,2,3,4,5], k = 3 Output: 18 Explanation: We need to choose exactly 3 elements from nums to maximize the sum. For the first iteration, we choose 5. Then sum is 5 and nums = [1,2,3,4,6] For the second iteration, we choose 6. Then sum is 5 + 6 and nums = [1,2,3,4,7] For the third iteration, we choose 7. Then sum is 5 + 6 + 7 = 18 and nums = [1,2,3,4,8] So, we will return 18. It can be proven, that 18 is the maximum answer that we can achieve.
Example 2:
Input: nums = [5,5,5], k = 2 Output: 11 Explanation: We need to choose exactly 2 elements from nums to maximize the sum. For the first iteration, we choose 5. Then sum is 5 and nums = [5,5,6] For the second iteration, we choose 6. Then sum is 5 + 6 = 11 and nums = [5,5,7] So, we will return 11. It can be proven, that 11 is the maximum answer that we can achieve.
Constraints:
1 <= nums.length <= 1001 <= nums[i] <= 1001 <= k <= 100
Approach Overview
Problem Overview: You receive an integer array nums and an integer k. In each of the k operations, pick the maximum element, add it to the score, then increase that element by 1 and place it back. The goal is to maximize the total score after exactly k picks.
Approach 1: Greedy with Sorting (O(n log n) time, O(1) extra space)
The optimal move each step is always the current maximum number. Sort the array and take the largest value m. Because the chosen value increases by 1 after every pick, the next best value becomes m + 1, then m + 2, and so on. Instead of re-sorting or scanning each time, treat the sequence as an arithmetic progression: m + (m+1) + ... + (m+k-1). This greedy observation eliminates repeated searches. Sorting is used only to find the initial maximum element. This approach works well when the array is static and you only need the largest starting value. It relies on the greedy property that selecting the current maximum always leads to the optimal sum. Related ideas often appear in Greedy and Array problems.
Approach 2: Priority Queue / Max Heap (O(k log n) time, O(n) space)
A more direct simulation uses a max heap. Insert all numbers from nums into a priority queue. For each of the k operations, extract the largest value, add it to the score, increment it by 1, and push it back into the heap. The heap guarantees O(log n) insertion and removal while always exposing the maximum element. This approach closely follows the problem statement and is easier to reason about during interviews when the arithmetic pattern is not immediately obvious. Priority queues are a standard tool for repeatedly accessing the largest or smallest element, commonly seen in Heap and greedy-style optimization problems.
Recommended for interviews: Interviewers typically expect the greedy insight. Recognizing that the maximum element grows linearly after each selection lets you compute the sum directly instead of simulating every step. Showing the heap simulation first demonstrates understanding of the problem mechanics, while the greedy arithmetic approach shows optimization skills and stronger algorithmic thinking.
Approach 1: Greedy Approach with Sorting
The problem can be approached using a greedy strategy. The idea is to always maximize the immediate gain by selecting the largest number available, increasing it by 1 to continue keeping it as a valuable pick for future iterations. By maintaining a sorted list and always taking from the largest element, we can ensure that every selection maximizes the score increment.
This Python function implements the greedy approach. It sorts the array in descending order and iteratively chooses the maximum number, updates the score, increases the number, and sorts again to maintain order.
Complexity
Time Complexity: O(k * n log n) due to the repeated sorting operations.
Space Complexity: O(1) since sorting is done in-place.
Approach 2: Priority Queue Approach
To avoid continuous sorting, use a priority queue (max-heap) to always fetch the largest element efficiently. By using a max-heap, the selection of the maximum element and the subsequent insertion of the incremented element can be performed in logarithmic time, optimizing the execution for scenarios with larger inputs or iterations.
This C++ solution uses a max-heap to efficiently keep track of the largest number, incrementing it and inserting it back to maintain the largest selection available for the next iterations.
Code
C++
JavaScript
Complexity
Time Complexity: O(k log n) because each heap operation takes logarithmic time.
Space Complexity: O(n) for storing elements in the heap.
Approach 3: Greedy + Mathematics
We notice that to make the final score maximum, we should make each choice as large as possible. Therefore, we select the largest element x in the array for the first time, x+1 for the second time, x+2 for the third time, and so on, until the kth time we select x+k-1. This way of selection ensures that the element selected each time is the largest in the current array, so the final score is also the largest. The answer is k x sum plus 0+1+2+cdots+(k-1), that is, k times x + (k - 1) times k / 2.
Time complexity is O(n), where n is the length of the array. Space complexity is O(1).
Approach 4: Default Approach
Code
Rust
Complexity Comparison
| Approach | Complexity |
|---|---|
| Greedy Approach with Sorting | Time Complexity: O(k * n log n) due to the repeated sorting operations. |
| Priority Queue Approach | Time Complexity: O(k log n) because each heap operation takes logarithmic time. |
| Greedy + Mathematics | — |
| Default Approach | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy with Sorting | O(n log n) | O(1) | When you only need the maximum element and want a direct greedy or mathematical solution |
| Priority Queue (Max Heap) | O(k log n) | O(n) | When simulating each operation or when repeatedly retrieving and updating the maximum element |
Video Solution
Leetcode 2656 Maximum Sum With Exactly K Elements - Greedy Approach & Solution Explained! • AlgorithmicIQ • 898 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Maximum Sum With Exactly K Elements easy or hard?
Maximum Sum With Exactly K Elements Python/Java solution
How to solve Maximum Sum With Exactly K Elements in O(n)?
Is Maximum Sum With Exactly K Elements asked at Google/Amazon/Meta?
What is the best approach for Maximum Sum With Exactly K Elements ?
What data structure is used in Maximum Sum With Exactly K Elements ?
What is the time complexity of Maximum Sum With Exactly K Elements ?
Ready to solve this problem?
Practice Maximum Sum With Exactly K Elements with our built-in code editor and test cases.
Practice on FleetCode