Choose K Elements With Maximum Sum
01 · Problem
You are given two integer arrays nums1 and nums2, both of length n, and a positive integer k.
For every index i, look at all indices j where nums1[j] is strictly less than nums1[i]. From those indices, pick at most k values of nums2[j] so that their sum is as large as possible. If fewer than k such indices exist, take all of them; if none exist, the sum is 0.
Return an array answer of length n where answer[i] is that maximum sum for index i.
02 · Examples
nums1 = [4,2,1,5,3], nums2 = [10,20,30,40,50], k = 2
[80,30,0,80,50]
For i=0 (nums1=4) the candidates are indices 1, 2, 4 with nums2 values 20, 30, 50; the two largest sum to 80. Index 2 has the smallest nums1 so it gets 0. Index 3 (nums1=5) can use every other index; its two largest are 50 and 30, giving 80.
nums1 = [2,2,2,2], nums2 = [3,1,2,3], k = 1
[0,0,0,0]
All nums1 values are equal, so no index has a strictly smaller partner and every answer is 0.
nums1 = [1,3,2], nums2 = [5,1,7], k = 3
[0,12,5]
Index 1 (nums1=3) can use indices 0 and 2, which is fewer than k, so it takes both: 5 + 7 = 12. Index 2 (nums1=2) can only use index 0, giving 5.
03 · Constraints
- 01n == nums1.length == nums2.length
- 021 <= n <= 105
- 031 <= nums1[i], nums2[i] <= 106
- 041 <= k <= n
04 · Optimal complexity
- Time
- O(n log n)
- Space
- O(n)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.