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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Choose K Elements With Maximum Sum

Difficulty: Medium

Problem Description

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, find all indices j where nums1[j] is less than nums1[i]. Choose at most 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.

Key Insights

  • For each element in nums1, we need to identify indices of elements that are smaller.
  • We can use a max-heap (or priority queue) to efficiently select the largest k elements from nums2 corresponding to the valid indices.
  • The problem can be solved in a time-efficient manner by leveraging sorting and data structures.

Space and Time Complexity

Time Complexity: O(n log n)
Space Complexity: O(n)

Solution

To solve the problem, we can follow these steps:

  1. Pair each element in nums1 with its corresponding element in nums2 and their indices.
  2. Sort these pairs based on the values in nums1.
  3. Use a max-heap to keep track of the largest k elements from nums2 as we iterate through the sorted list.
  4. For each index in the original list, calculate the sum of the largest k elements that can be chosen based on the condition.
  5. Store the results in the output array.

Code Solutions

import heapq

def chooseKElementsWithMaximumSum(nums1, nums2, k):
    n = len(nums1)
    answer = [0] * n
    pairs = sorted((num1, num2, i) for i, (num1, num2) in enumerate(zip(nums1, nums2)))
    
    max_heap = []
    total = 0
    j = 0
    
    for num1, num2, index in pairs:
        while j < n and pairs[j][0] < num1:
            heapq.heappush(max_heap, -pairs[j][1])  # Push negative for max-heap
            total += pairs[j][1]
            j += 1
        # Get the sum of the largest k elements
        if len(max_heap) > k:
            total += -heapq.heappop(max_heap)  # Remove the smallest element (largest in negative)
        answer[index] = total
    
    return answer
← Back to All Questions