2542. Maximum Subsequence Score

Description

The maxScore function aims to find the maximum possible score by selecting exactly k elements from nums1 and multiplying the sum of these elements by the corresponding maximum value from nums2. The task involves efficiently managing the selection of elements from nums1 while maximizing the product with elements from nums2.

Intuition

The problem can be approached by first understanding that selecting the top k elements from nums1 will maximize the sum, but these elements should be multiplied by the largest possible value from nums2. Hence, sorting the pairs of elements from nums1 and nums2 based on nums2 values in descending order allows for efficient selection.

Approach

1. Pairing and Sorting: Pair each element in nums1 with its corresponding element in nums2. Sort these pairs based on the nums2 values in descending order.
2. Heap to Track Minimum Values: Use a min-heap to keep track of the smallest values from nums1 while iterating through the sorted pairs. This helps in efficiently maintaining the sum of the top k elements.
3. Calculate Maximum Score: For each pair, if the heap size reaches k, calculate the score by multiplying the current sum of the top k elements by the current nums2 value. Update the result if this score is higher than the previous scores.

Complexity

Time Complexity:

O(n log n) due to the sorting step, where n is the length of nums1 or nums2. The heap operations are logarithmic, but sorting dominates the time complexity.

Space Complexity:

O(n) for storing the pairs and the heap. The space complexity is linear concerning the number of elements.

Code

C++

class Solution {
public:
    long long maxScore(vector& nums1, vector& nums2, int k) {
        long long result = 0;
        long long totalSum = 0;
        priority_queue, greater> heap;

        vector> merged;
        for (int i = 0; i < nums1.size(); i++) {
            merged.push_back({nums2[i], nums1[i]});
        }
        sort(merged.begin(), merged.end(), greater>());

        for (const auto& [maxOf2, num1Val] : merged) {
            if (heap.size() == k) {
                totalSum -= heap.top();
                heap.pop();
            }

            totalSum += num1Val;
            heap.push(num1Val);

            if (heap.size() == k) {
                result = max(result, totalSum * static_cast(maxOf2));
            }
        }

        return result;
    }
};

Python

class Solution:
    def maxScore(self, nums1, nums2, k):
        result = 0
        totalSum = 0
        heap = []

        merged = [(nums2[i], nums1[i]) for i in range(len(nums1))]
        merged.sort(reverse=True)

        for maxOf2, num1Val in merged:
            if len(heap) == k:
                totalSum -= heapq.heappop(heap)

            totalSum += num1Val
            heapq.heappush(heap, num1Val)

            if len(heap) == k:
                result = max(result, totalSum * maxOf2)

        return result

Java

class Solution {
    public long maxScore(int[] nums1, int[] nums2, int k) {
        long result = 0;
        long totalSum = 0;
        PriorityQueue heap = new PriorityQueue<>();

        List merged = new ArrayList<>();
        for (int i = 0; i < nums1.length; i++) {
            merged.add(new int[]{nums2[i], nums1[i]});
        }
        merged.sort((a, b) -> Integer.compare(b[0], a[0]));

        for (int[] pair : merged) {
            int maxOf2 = pair[0];
            int num1Val = pair[1];

            if (heap.size() == k) {
                totalSum -= heap.poll();
            }

            totalSum += num1Val;
            heap.offer(num1Val);

            if (heap.size() == k) {
                result = Math.max(result, totalSum * (long)maxOf2);
            }
        }

        return result;
    }
}

JavaScript

var maxScore = function(nums1, nums2, k) {

    let result = 0;
    let totalSum = 0;
    let heap = new MinPriorityQueue({priority: (element) => element})

    const merged = nums1.map((nums1Val, i) => [nums2[i], nums1Val])
    merged.sort((a,b) => b[0] - a[0])

    for (const [maxOf2, num1Val] of merged){
        if(heap.size() === k){
            totalSum -= heap.dequeue().element
        }

        totalSum += num1Val
        heap.enqueue(num1Val)

        if(heap.size() === k){
            result = Math.max(result, totalSum * maxOf2)
        }

    }

return result
};