You are given two 0-indexed integer arrays nums1 and nums2 of equal length n and a positive integer k. You must choose a subsequence of indices from nums1 of length k.
For chosen indices i0, i1, ..., ik - 1, your score is defined as:
nums1 multiplied with the minimum of the selected elements from nums2.(nums1[i0] + nums1[i1] +...+ nums1[ik - 1]) * min(nums2[i0] , nums2[i1], ... ,nums2[ik - 1]).Return the maximum possible score.
A subsequence of indices of an array is a set that can be derived from the set {0, 1, ..., n-1} by deleting some or no elements.
Example 1:
Input: nums1 = [1,3,3,2], nums2 = [2,1,3,4], k = 3 Output: 12 Explanation: The four possible subsequence scores are: - We choose the indices 0, 1, and 2 with score = (1+3+3) * min(2,1,3) = 7. - We choose the indices 0, 1, and 3 with score = (1+3+2) * min(2,1,4) = 6. - We choose the indices 0, 2, and 3 with score = (1+3+2) * min(2,3,4) = 12. - We choose the indices 1, 2, and 3 with score = (3+3+2) * min(1,3,4) = 8. Therefore, we return the max score, which is 12.
Example 2:
Input: nums1 = [4,2,3,1,1], nums2 = [7,5,10,9,6], k = 1 Output: 30 Explanation: Choosing index 2 is optimal: nums1[2] * nums2[2] = 3 * 10 = 30 is the maximum possible score.
Constraints:
n == nums1.length == nums2.length1 <= n <= 1050 <= nums1[i], nums2[j] <= 1051 <= k <= nThe key idea in #2542 Maximum Subsequence Score is to maximize the product of two factors: the sum of selected elements from one array and the minimum value from the corresponding elements in another array. A useful observation is that if we fix the minimum value from the second array, we should choose the largest possible elements from the first array to maximize the sum.
A common strategy is to pair elements from both arrays and sort them in descending order based on the second array. As we iterate through this sorted list, we treat the current value as the potential minimum. To maintain the best possible sum of k elements from the first array, a min-heap (priority queue) is used. The heap keeps track of the top k candidates contributing to the sum, while removing smaller values when necessary.
At each step, compute the potential score using the current sum and the current minimum candidate. This greedy + heap approach efficiently explores optimal combinations with a time complexity of O(n log n) due to sorting and heap operations, and O(k) extra space for the heap.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Greedy + Sorting + Min Heap | O(n log n) | O(k) |
NeetCodeIO
Use these hints if you're stuck. Try solving on your own first.
How can we use sorting here?
Try sorting the two arrays based on second array.
Loop through nums2 and compute the max product given the minimum is nums2[i]. Update the answer accordingly.
In this approach, the idea is to pair up elements of nums1 and nums2 into tuples. Then, sort these pairs by nums2 in descending order. This way, we process elements with higher values in nums2 first. Using a priority queue (min-heap), we can efficiently keep track of the k largest nums1 values, which we use to calculate the score. The maximum score is computed by iterating through potential minimums, maintaining the current sum of the largest k values seen so far.
Time Complexity: O(n log n) due to sorting and heap operations.
Space Complexity: O(k) for the min-heap storing k elements.
1import heapq
2
3def maxScore(nums1, nums2, k):
4 pairs = sorted(zip(nums2, nums1), reverse=True)
5 min_heap = []
6 current_sum = 0
7 max_score = 0
8 for num2, num1 in pairs:
9 heapq.heappush(min_heap, num1)
10 current_sum += num1
11 if len(min_heap) > k:
12 current_sum -= heapq.heappop(min_heap)
13 if len(min_heap) == k:
14 max_score = max(max_score, current_sum * num2)
15 return max_score
16
17# Example usage
18print(maxScore([1,3,3,2], [2,1,3,4], 3)) # Output: 12The solution sorts nums2 together with nums1. It processes from the largest nums2 value, maintaining a sum and a priority queue to track the largest k values of nums1. The score is calculated as the product of this sum and the current nums2 value in the loop, updating the maximum score as needed.
This approach emphasizes efficient subsequence selection by partitioning the array. Divide the array in such a way that potential results can be directly computed without redundant calculations. Use recursion to evaluate possible subsequences efficiently.
Time Complexity: O(n log n) primary by sorting and heap operations.
Space Complexity: O(k) for the priority queue.
1function maxScore(nums1, nums2, k) {
2
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, problems involving greedy strategies, heaps, and sorting are common in FAANG-style interviews. #2542 Maximum Subsequence Score tests optimization thinking, heap usage, and efficient handling of constraints.
A min-heap (priority queue) is the most suitable data structure. It helps maintain the k largest elements contributing to the sum while efficiently removing the smallest element when the heap exceeds size k.
The optimal approach uses a greedy strategy combined with sorting and a min-heap. By sorting pairs based on the second array and maintaining the top k values from the first array in a heap, we can efficiently compute the best score candidate at each step.
Sorting by the second array allows us to treat each value as the potential minimum in the score formula. This ensures that when we compute the score, the current element correctly represents the minimum value among the chosen subsequence.
This JavaScript solution employs array methods and manual management of minimum values from min-heap, leveraging native array operations for computing scores.