Choose K Elements With Maximum Sum

Medium
1433.

Choose K Elements With Maximum Sum

MediumArraySortingHeap (Priority Queue)AmazonGoogle

Choose K Elements With Maximum Sum is a medium coding problem on arrays, sorting and heap, asked in Amazon and Google interviews.

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.length
  • 1 <= n <= 10^5
  • 1 <= nums1[i] <= 10^6
  • 1 <= nums2[i] <= 10^4
  • 1 <= k <= n
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @param {number} k
 * @return {number[]}
 */
var findMaxSum = function(nums1, nums2, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.length
  • 1 <= n <= 10^5
  • 1 <= nums1[i] <= 10^6
  • 1 <= nums2[i] <= 10^4
  • 1 <= k <= n

Hints for Choose K Elements With Maximum Sum

  1. 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 equal nums1.

  2. Hint 2

    Maintain the k largest nums2 values seen so far and their sum with a min-heap of size k.

  3. Hint 3

    Handle a run of equal nums1 values as a group: answer all of them first, then add their nums2 values 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

  1. Sort the indices by nums1.
  2. Walk the order in groups of equal nums1. For every index of a group, the answer is the current heap sum.
  3. Then push each nums2 of the group into the min-heap, adding it to the sum; whenever the heap exceeds k elements, 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 nums1 values count each other.
  • The answers must be placed at the original indices.
  • With the original limits the sums exceed 32 bits; this version caps nums2 so 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 ans

Java

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