Maximum Subsequence Score
Problem
Given two integer arrays nums1 and nums2 of equal length and an integer k, select exactly k indices such that the score, defined as the sum of nums1 elements at those indices multiplied by the minimum nums2 element at those indices, is maximized. Return this maximum score.
- 1 ≤ nums1.length == nums2.length ≤ 10⁵
- 1 ≤ nums1[i], nums2[i] ≤ 10⁵
- 1 ≤ k ≤ nums1.length
Example
nums1 = [1,3,3,2], nums2 = [2,1,3,4], k = 312First, form pairs (nums2[i], nums1[i]) and sort them in descending order by nums2: pairs = [(4,2), (3,3), (2,1), (1,3)]. Iterate through these pairs, maintaining a min-heap of nums1 values to track the current k candidates. For k = 3, after processing the first three pairs, the heap contains 2, 3, 1, so the sum of nums1 is 2 + 3 + 1 = 6, and the minimum nums2 among these pairs is 2. The score is 6 * 2 = 12, which is the maximum achievable score.
Approach
Straightforward Solution
A brute-force approach would try all combinations of k elements, which is combinatorially explosive (O(n choose k)) and infeasible for large n.
Core Observation
The score depends on the sum of selected nums1 elements and the minimum nums2 element among them. To maximize the product, one must balance a large sum with a large minimum multiplier.
Path to Optimal
PreviewSorting pairs by nums2 descending ensures that when iterating, the current nums2 value is the minimum among all previously considered pairs…
Full step-by-step walkthrough on Pro →
Optimal Approach
PreviewSort pairs by nums2 descending. Iterate through pairs, pushing nums1 values into a min-heap and accumulating their sum…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
O(n log n)
Sorting takes O(n log n). Iterating through n pairs, each heap push/pop operation costs O(log k). Since the heap size is at most k, total heap operations are O(n log k). Since k ≤ n, the overall time complexity is dominated by sorting, so it is O(n log n).
Space
O(k)
The min-heap stores at most k elements, so auxiliary space is O(k). The sorted pairs array uses O(n) space but is input-derived and typically not counted as extra.
Pattern Spotlight
Heap / Priority Queue (Sorted Greedy with Min-Heap over Values)
When maximizing a product involving a sum and a minimum, sorting by the minimum factor and using a min-heap to maintain the largest sum of fixed size allows efficient exploration of all candidate subsets.
Solution
| 1 | import heapq
|
| 2 |
|
| 3 | class Solution:
|
| 4 | def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:
|
| 5 | pairs = sorted(zip(nums2, nums1), reverse=True)
|
| 6 | min_heap = []
|
| 7 | total = 0
|
| 8 | ans = 0
|
| 9 |
|
| 10 | for m, v in pairs:
|
| 11 | heapq.heappush(min_heap, v)
|
| 12 | total += v
|
| 13 |
|
| 14 | if len(min_heap) > k:
|
| 15 | total -= heapq.heappop(min_heap)
|
| 16 |
|
| 17 | if len(min_heap) == k:
|
| 18 | ans = max(ans, total * m)
|
| 19 |
|
| 20 | return ans |
Step-by-Step Solution
Sort Pairs by nums2 Descending to Fix the Minimum Multiplier
| 5 | pairs = sorted(zip(nums2, nums1), reverse=True)
|
Objective
To order the pairs so that the current nums2 value represents the minimum multiplier for the selected subset.
Key Insight
Sorting by nums2 descending ensures that as the iteration progresses, the current nums2 value is the smallest among all considered pairs, fixing the minimum multiplier for the current selection. This ordering transforms the problem into a linear scan where the minimum is known at each step.
Interview Quick-Check
Core Logic
Sorting pairs by nums2 descending sets the current nums2 as the minimum multiplier for the subset formed by the heap elements.
Common Pitfalls & Bugs
Sorting ascending would not guarantee the current nums2 is the minimum, breaking the logic of the heap-based approach.
Maintain a Min-Heap of nums1 Values to Track the Largest Sum of k Elements
To efficiently keep track of the k largest nums1 values corresponding to the current minimum nums2 multiplier.
Calculate and Update the Maximum Score When Exactly k Elements Are Selected
To compute the current score as the product of the sum of selected nums1 elements and the current minimum nums2 multiplier, updating the maximum answer found.
Return the Maximum Score Found After Processing All Pairs
To output the highest score computed during the iteration over all pairs.
3 more steps with full analysis available on Pro.
Line Analysis
This solution has 5 Critical lines interviewers watch for.
pairs = sorted(zip(nums2, nums1), reverse=True)Sort pairs of (nums2, nums1) in descending order by nums2.
Sorting by nums2 descending ensures that the current nums2 value is the minimum multiplier for the subset of nums1 values considered so far, enabling a linear scan with a fixed minimum at each step.
if len(min_heap) > k:If the heap size exceeds k, remove the smallest nums1 value.
Maintaining exactly k elements in the heap ensures the subset size constraint is respected and the sum reflects the largest possible sum of k elements.
total -= heapq.heappop(min_heap)Subtract the removed smallest nums1 value from the total sum.
Adjusting the sum after popping maintains correctness of the sum for the current subset of size k.
Full line-by-line criticality + rationale for all 12 lines available on Pro.
Test Your Understanding
Why does sorting pairs by nums2 descending and maintaining a min-heap of nums1 values guarantee that the current nums2 value is the minimum in the selected subset?
See the answer with Pro.
Related Problems
Heap / Priority Queue pattern
Don't just read it. Drill it.
Reconstruct Maximum Subsequence Score from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Maximum Subsequence Score drill