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
Sorting pairs by nums2 descending ensures that when iterating, the current nums2 value is the minimum among all previously considered pairs. Maintaining a min-heap of nums1 values allows keeping track of the largest possible sum of k elements corresponding to the current minimum nums2. This transforms the problem into a single pass over the sorted pairs with O(log k) heap updates per element.
Optimal Approach
Sort pairs by nums2 descending. Iterate through pairs, pushing nums1 values into a min-heap and accumulating their sum. When the heap size exceeds k, pop the smallest nums1 value to maintain exactly k elements. At each step where the heap size is k, calculate the score as sum * current nums2 (which is the minimum in the current selection) and update the answer if larger. This yields an O(n log n) time solution.
Time
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
| 6 | min_heap = []
|
| 7 | total = 0
|
| 8 | ans = 0
|
| 10 | for m, v in pairs:
|
| 11 | heapq.heappush(min_heap, v)
|
| 12 | total += v
|
| 14 | if len(min_heap) > k:
|
| 15 | total -= heapq.heappop(min_heap)
|
Objective
To efficiently keep track of the k largest nums1 values corresponding to the current minimum nums2 multiplier.
Key Insight
Using a min-heap allows discarding the smallest nums1 value when the heap size exceeds k, ensuring the sum always reflects the largest possible sum of k elements for the current minimum multiplier. This dynamic maintenance is crucial for maximizing the product.
Interview Quick-Check
Core Logic
The min-heap stores the current k largest nums1 values, enabling efficient updates to the sum when elements are added or removed.
State & Boundaries
When the heap size exceeds k, the smallest nums1 value is removed to maintain exactly k elements.
Common Pitfalls & Bugs
Failing to remove the smallest element when heap size exceeds k leads to incorrect sums and invalid subsets.
Calculate and Update the Maximum Score When Exactly k Elements Are Selected
| 17 | if len(min_heap) == k:
|
| 18 | ans = max(ans, total * m)
|
Objective
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.
Key Insight
Only when the heap size is exactly k does the current sum and minimum multiplier form a valid candidate subset. Calculating the product at this point ensures all subsets of size k are considered, and tracking the maximum guarantees the optimal solution is found.
Interview Quick-Check
Core Logic
Calculate score as sum * current nums2 only when heap size is k, ensuring valid subsets.
Common Pitfalls & Bugs
Calculating score before heap size reaches k or after popping elements leads to invalid or incomplete subsets.
Return the Maximum Score Found After Processing All Pairs
| 20 | return ans |
Objective
To output the highest score computed during the iteration over all pairs.
Key Insight
After considering all possible minimum multipliers and corresponding sums, the stored maximum score represents the optimal selection of k elements maximizing the product.
Interview Quick-Check
Core Logic
Returning the maximum score after processing all pairs ensures the global optimum is reported.
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.
if len(min_heap) == k:If the heap size is exactly k, compute the current score.
Only subsets of size k are valid; computing the score here ensures correctness and completeness of candidate evaluation.
ans = max(ans, total * m)Update the answer with the maximum score found so far.
Tracking the maximum score guarantees the final returned value is the optimal solution.
min_heap = []Initialize an empty min-heap to store nums1 values.
The min-heap maintains the k largest nums1 values efficiently, allowing quick removal of the smallest when exceeding k elements.
heapq.heappush(min_heap, v)Push the current nums1 value v into the min-heap.
Adding v to the heap updates the candidate subset of nums1 values for the current minimum multiplier m.
total += vAdd the current nums1 value v to the total sum.
Updating the sum reflects the inclusion of v in the current candidate subset, necessary for score calculation.
return ansReturn the maximum score after processing all pairs.
This returns the globally optimal score computed from all valid subsets considered during iteration.
total = 0Initialize total sum of selected nums1 elements to zero.
Tracking the sum of elements in the heap is essential for calculating the score at each step.
ans = 0Initialize the running maximum score before evaluating any candidate subsets.
A dedicated variable for the running maximum score ensures each candidate score is compared consistently and that the final result reflects the best subset seen so far.
for m, v in pairs:Iterate over each pair (nums2 value m, nums1 value v) in sorted order.
Processing pairs in descending nums2 order ensures the current m is the minimum multiplier for the current subset.
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?
Because iterating in descending order of nums2 ensures that the current nums2 is the smallest among all previously considered pairs, so when the heap contains k nums1 values from these pairs, the current nums2 is the minimum multiplier for that subset.
Related Problems
Heaps 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