
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
- Pairing and Sorting: Pair each element in
nums1
with its corresponding element innums2
. Sort these pairs based on thenums2
values in descending order. - 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 topk
elements. - Calculate Maximum Score: For each pair, if the heap size reaches
k
, calculate the score by multiplying the current sum of the topk
elements by the currentnums2
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
};