Dare2Solve
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
.
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.
nums1
with its corresponding element in nums2
. Sort these pairs based on the nums2
values in descending order.nums1
while iterating through the sorted pairs. This helps in efficiently maintaining the sum of the top k
elements.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.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.
O(n) for storing the pairs and the heap. The space complexity is linear concerning the number of elements.
class Solution {
public:
long long maxScore(vector<int>& nums1, vector<int>& nums2, int k) {
long long result = 0;
long long totalSum = 0;
priority_queue<int, vector<int>, greater<int>> heap;
vector<pair<int, int>> merged;
for (int i = 0; i < nums1.size(); i++) {
merged.push_back({nums2[i], nums1[i]});
}
sort(merged.begin(), merged.end(), greater<pair<int, int>>());
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<long long>(maxOf2));
}
}
return result;
}
};
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
class Solution {
public long maxScore(int[] nums1, int[] nums2, int k) {
long result = 0;
long totalSum = 0;
PriorityQueue<Integer> heap = new PriorityQueue<>();
List<int[]> 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;
}
}
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
};