Choose K Elements With Maximum Sum

Choose K Elements With Maximum Sum

What is this problem about?

You are given two arrays, nums1 and nums2, and an integer $k$. For each index $i$, you want to find the maximum possible sum of at most $k$ values from nums2 at indices $j$ such that nums1[j] is strictly less than nums1[i]. This is a range-query problem where the "range" is defined by values in one array and the "sum" is taken from another.

Why is this asked in interviews?

Bloomberg asks this to test your ability to coordinate multiple constraints using Sorting and Heaps. It’s a "top-k" problem with a dynamic threshold. It evaluates your skill in processing data in a specific order (based on nums1) and maintaining a sliding set of the largest values seen so far using a Min-Heap.

Algorithmic pattern used

This problem uses the Sorting and Min-Heap (Priority Queue) pattern. First, group (nums1[i], nums2[i], original_index) and sort by nums1. Iterate through the sorted items. For each item, the "sum of at most $k$ largest nums2 values" can be calculated using a Min-Heap that stores the $k$ largest nums2 values seen so far. By using a running sum, you can answer the query in $O(\log k)$ time per element.

Example explanation

nums1 = [4, 2, 4], nums2 = [10, 20, 30], $k = 1$

1. Sort by nums1: (2, 20, idx 1), (4, 10, idx 0), (4, 30, idx 2).
2. Item 1 (val 2): No items have nums1 < 2. Sum = 0. Add 20 to heap.
3. Item 2 (val 4): Items with nums1 < 4 is index 1 (val 20). Top-1 sum = 20.
4. Item 3 (val 4): Items with nums1 < 4 is still just index 1. Top-1 sum = 20. Result: [20, 0, 20].

Common mistakes candidates make

The most frequent mistake is not handling duplicate values in nums1 correctly. If multiple indices have the same nums1 value, they cannot be counted in each other's sums. Another error is using a Max-Heap instead of a Min-Heap; to maintain the largest $k$ elements, you need a Min-Heap so you can easily discard the smallest of those $k$ elements.

Interview preparation tip

For any problem that involves "largest $k$ elements encountered so far," a Min-Heap of size $k$ is the standard tool. If you need to answer for every index, sort the input first to transform the "any $j$ such that $A[j] < A[i]$" condition into a simple linear scan.