Watch 7 video solutions for Choose K Elements With Maximum Sum, a medium level problem involving Array, Sorting, Heap (Priority Queue). This walkthrough by codestorywithMIK has 5,946 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given two integer arrays, nums1 and nums2, both of length n, along with a positive integer k.
For each index i from 0 to n - 1, perform the following:
j where nums1[j] is less than nums1[i].k values of nums2[j] at these indices to maximize the total sum.Return an array answer of size n, where answer[i] represents the result for the corresponding index i.
Example 1:
Input: nums1 = [4,2,1,5,3], nums2 = [10,20,30,40,50], k = 2
Output: [80,30,0,80,50]
Explanation:
i = 0: Select the 2 largest values from nums2 at indices [1, 2, 4] where nums1[j] < nums1[0], resulting in 50 + 30 = 80.i = 1: Select the 2 largest values from nums2 at index [2] where nums1[j] < nums1[1], resulting in 30.i = 2: No indices satisfy nums1[j] < nums1[2], resulting in 0.i = 3: Select the 2 largest values from nums2 at indices [0, 1, 2, 4] where nums1[j] < nums1[3], resulting in 50 + 30 = 80.i = 4: Select the 2 largest values from nums2 at indices [1, 2] where nums1[j] < nums1[4], resulting in 30 + 20 = 50.Example 2:
Input: nums1 = [2,2,2,2], nums2 = [3,1,2,3], k = 1
Output: [0,0,0,0]
Explanation:
Since all elements in nums1 are equal, no indices satisfy the condition nums1[j] < nums1[i] for any i, resulting in 0 for all positions.
Constraints:
n == nums1.length == nums2.length1 <= n <= 1051 <= nums1[i], nums2[i] <= 1061 <= k <= nProblem Overview: You are given two arrays where each index represents a pair of values. For every position i, compute the maximum possible sum of up to k values from other indices whose first value is strictly smaller than nums1[i]. The goal is to efficiently track the best k candidates while scanning the array.
Approach 1: Brute Force with Heap per Index (O(n² log k) time, O(k) space)
For each index i, iterate through the entire array and collect elements where nums1[j] < nums1[i]. Maintain a min-heap of size at most k containing the largest nums2[j] values seen so far. Each candidate pushes into the heap and the smallest element is removed if the size exceeds k. The sum of the heap gives the best result for that index. This method is straightforward but expensive because the full scan repeats for every element.
Approach 2: Sorting + Priority Queue (Min-Heap) (O(n log n + n log k) time, O(n + k) space)
Sort indices by nums1 so elements with smaller values are processed first. As you iterate through the sorted order, maintain a running min-heap storing the largest k values from nums2 that have already been seen. Also track the current sum of the heap. For each group of indices with the same nums1 value, compute their answers using the current sum before inserting their nums2 values into the heap. This ensures only elements with strictly smaller nums1 contribute to the result. Each insertion or removal from the heap costs O(log k), keeping the overall runtime efficient.
The key insight: sorting transforms the "smaller value" condition into a prefix problem. Once elements are processed in increasing order, every previously visited element automatically satisfies the constraint.
This pattern appears frequently when combining sorting with incremental state tracking using a heap (priority queue). The input itself is just a standard array, but ordering it unlocks a much more efficient solution.
Recommended for interviews: The sorting + min-heap approach is the expected solution. It demonstrates recognition of ordering constraints and efficient top-k maintenance. Mentioning the brute force approach first shows you understand the problem space, but implementing the O(n log n + n log k) method proves strong algorithmic judgment.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force with Heap per Index | O(n² log k) | O(k) | Useful for understanding the problem or when n is very small |
| Sorting + Min-Heap (Priority Queue) | O(n log n + n log k) | O(n + k) | Best general solution; efficiently maintains top k candidates while processing sorted elements |