We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Choose K Elements With Maximum Sum

Number: 3759

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

Given two arrays nums1 and nums2 of equal length, and an integer k, for each index i you must consider all indices j where nums1[j] < nums1[i]. From these eligible indices, pick at most k elements (based on their nums2 values) that maximize the sum. The answer for index i is this maximum sum. Return an array of answers for every index.

Key Insights

  • Process elements by increasing nums1 so that when handling an element, all previously processed elements have smaller or equal nums1 values.
  • To ensure that only elements with strictly smaller nums1 values contribute, process groups with equal nums1 values separately: first record the answer for all elements in the group (using contributions from previously processed groups) and only then add the current group’s nums2 values.
  • Use a min-heap to maintain the top k nums2 values seen so far and maintain their cumulative sum.
  • Maintaining a heap of size at most k ensures that adding each new number and occasionally removing the smallest (to preserve the best k) is efficient.

Space and Time Complexity

Time Complexity: O(n log k) – Sorting takes O(n log n) but grouping and heap operations over n elements with a heap of size at most k lead to O(n log k). Space Complexity: O(n) – for storing the answer, sorted array and heap.

Solution

To solve the problem, combine sorting with a min-heap (priority queue):

  1. Create an array of tuples where each tuple consists of (nums1[i], nums2[i], original_index). Sort this array by nums1.
  2. Iterate over the sorted array while grouping elements with the same nums1 value.
  3. For each group, prior to adding current elements, use the current heap sum as the answer for each element in that group (ensuring we only use elements with strictly smaller nums1).
  4. Then, add each current element’s nums2 to the heap. If the heap size exceeds k, pop the smallest element from the heap and update the cumulative sum.
  5. Finally, the answer array, indexed by original indices, contains the required sums.

This technique efficiently tracks the best k values among valid candidates for each index.

Code Solutions

import heapq

def chooseKElementsWithMaximumSum(nums1, nums2, k):
    n = len(nums1)
    # Prepare tuples for sorting: (nums1 value, nums2 value, original index)
    elements = [(nums1[i], nums2[i], i) for i in range(n)]
    # Sort elements by nums1
    elements.sort(key=lambda x: x[0])
    
    answer = [0] * n
    current_heap = []  # min-heap to store at most k nums2 values
    current_sum = 0
    
    i = 0
    # Process groups with the same nums1 value together
    while i < n:
        group = []
        current_val = elements[i][0]
        # Collect all elements in the group with the same nums1 value
        while i < n and elements[i][0] == current_val:
            group.append(elements[i])
            i += 1
        
        # For every element in this group, assign answer as the current heap sum
        for _, _, original_index in group:
            answer[original_index] = current_sum
        
        # Now, add each element's nums2 into the heap.
        for _, num2, _ in group:
            heapq.heappush(current_heap, num2)
            current_sum += num2
            # If heap exceeds k, pop the smallest value to maintain top k
            if len(current_heap) > k:
                removed = heapq.heappop(current_heap)
                current_sum -= removed
                
    return answer

# Example usage:
print(chooseKElementsWithMaximumSum([4,2,1,5,3], [10,20,30,40,50], 2))
← Back to All Questions