Choose K Elements With Maximum Sum — Problem & Solution
Choose K Elements With Maximum Sum solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Choose K Elements With Maximum Sum is a medium coding problem on arrays, sorting and heap, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Sorting, Heap
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given two arrays nums1 and nums2 of length n and an integer k.
For every index i, look at all indices j with nums1[j] < nums1[i] (strictly smaller). From the values nums2[j] at those indices, pick at most k so that their sum is as large as possible. That maximum sum is answer[i] (it is 0 when no index qualifies).
Return answer.
Constraint note: nums2 values are capped at 10^4 (the original allows 10^6) so every answer fits in a 32-bit integer.
Example 1
Input: nums1 = [3,1,3,2], nums2 = [5,9,4,7], k = 1
Output: [9,0,9,9]
Explanation: For both 3s the candidates are indices 1 and 3, and the single best value is 9; for the 2 only index 1 qualifies.
Example 2
Input: nums1 = [4,2,1,5,3], nums2 = [10,20,30,40,50], k = 2
Output: [80,30,0,80,50]
Example 3
Input: nums1 = [2,2,2], nums2 = [3,1,2], k = 2
Output: [0,0,0]
Explanation: Equal values do not count — the comparison is strict.
Constraints
n == nums1.length == nums2.length1 <= n <= 10^51 <= nums1[i] <= 10^61 <= nums2[i] <= 10^41 <= k <= n
Hints for Choose K Elements With Maximum Sum
Hint 1
Process the indices in increasing order of
nums1; the candidates for an index are exactly the ones processed before it — minus those with an equalnums1.Hint 2
Maintain the
klargestnums2values seen so far and their sum with a min-heap of sizek.Hint 3
Handle a run of equal
nums1values as a group: answer all of them first, then add theirnums2values to the heap.
How to solve Choose K Elements With Maximum Sum
Sorted by nums1, the candidate set of each index is a prefix of the order. So keep a running "best k of the prefix" — a size-k min-heap whose root is the weakest value kept — and its sum.
Approach
- Sort the indices by
nums1. - Walk the order in groups of equal
nums1. For every index of a group, the answer is the current heap sum. - Then push each
nums2of the group into the min-heap, adding it to the sum; whenever the heap exceedskelements, pop the smallest and subtract it.
Why it works
When a group is answered, the heap has seen exactly the indices with strictly smaller nums1. A size-k min-heap that always evicts its minimum holds the k largest values seen (or all of them if fewer), and since every nums2 is positive, taking as many as allowed is optimal.
Complexity
- Time —
O(n log n) - Space —
O(n)
Pitfalls
- Answer a group before inserting it, or equal
nums1values count each other. - The answers must be placed at the original indices.
- With the original limits the sums exceed 32 bits; this version caps
nums2so they do not.
Reference solution
Python
from typing import List
import heapq
def findMaxSum(nums1: List[int], nums2: List[int], k: int) -> List[int]:
n = len(nums1)
order = sorted(range(n), key=lambda i: nums1[i])
ans = [0] * n
heap = [] # the k largest nums2 values among strictly smaller nums1
total = 0
i = 0
while i < n:
j = i
while j < n and nums1[order[j]] == nums1[order[i]]:
ans[order[j]] = total
j += 1
for t in range(i, j):
v = nums2[order[t]]
heapq.heappush(heap, v)
total += v
if len(heap) > k:
total -= heapq.heappop(heap)
i = j
return ansJava
public static int[] findMaxSum(int[] nums1, int[] nums2, int k) {
int n = nums1.length;
Integer[] order = new Integer[n];
for (int x = 0; x < n; x++) order[x] = x;
Arrays.sort(order, (a, b) -> Integer.compare(nums1[a], nums1[b]));
int[] ans = new int[n];
PriorityQueue<Integer> heap = new PriorityQueue<>(); // the k largest nums2 values so far
long total = 0;
int i = 0;
while (i < n) {
int j = i;
while (j < n && nums1[order[j]] == nums1[order[i]]) {
ans[order[j]] = (int) total;
j++;
}
for (int t = i; t < j; t++) {
int v = nums2[order[t]];
heap.add(v);
total += v;
if (heap.size() > k) total -= heap.poll();
}
i = j;
}
return ans;
}C++
vector<int> findMaxSum(vector<int>& nums1, vector<int>& nums2, int k) {
int n = nums1.size();
vector<int> order(n);
for (int x = 0; x < n; x++) order[x] = x;
sort(order.begin(), order.end(), [&](int a, int b) { return nums1[a] < nums1[b]; });
vector<int> ans(n, 0);
priority_queue<int, vector<int>, greater<int>> heap; // the k largest nums2 values so far
long long total = 0;
int i = 0;
while (i < n) {
int j = i;
while (j < n && nums1[order[j]] == nums1[order[i]]) {
ans[order[j]] = (int) total;
j++;
}
for (int t = i; t < j; t++) {
int v = nums2[order[t]];
heap.push(v);
total += v;
if ((int) heap.size() > k) {
total -= heap.top();
heap.pop();
}
}
i = j;
}
return ans;
}JavaScript
var findMaxSum = function(nums1, nums2, k) {
var n = nums1.length;
var order = [];
for (var x = 0; x < n; x++) order.push(x);
order.sort(function(a, b) { return nums1[a] - nums1[b]; });
var ans = [];
for (var z = 0; z < n; z++) ans.push(0);
var heap = []; // the k largest nums2 values among strictly smaller nums1
var total = 0;
var i = 0;
while (i < n) {
var j = i;
while (j < n && nums1[order[j]] === nums1[order[i]]) {
ans[order[j]] = total;
j++;
}
for (var t = i; t < j; t++) {
var v = nums2[order[t]];
heapPush(heap, v);
total += v;
if (heap.length > k) total -= heapPop(heap);
}
i = j;
}
return ans;
};
var heapPush = function(h, v) {
h.push(v);
var i = h.length - 1;
while (i > 0) {
var p = (i - 1) >> 1;
if (h[p] <= h[i]) break;
var t = h[p]; h[p] = h[i]; h[i] = t;
i = p;
}
};
var heapPop = function(h) {
var top = h[0];
var last = h.pop();
if (h.length > 0) {
h[0] = last;
var j = 0;
for (;;) {
var l = 2 * j + 1, r = l + 1, s = j;
if (l < h.length && h[l] < h[s]) s = l;
if (r < h.length && h[r] < h[s]) s = r;
if (s === j) break;
var t = h[s]; h[s] = h[j]; h[j] = t;
j = s;
}
}
return top;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms