Max Subsequence Score LeetCode 2542

LeetCode 2542 Maximum Subsequence Score gives you two integer arrays nums1 and nums2 of equal length n, and an integer k. Your task is to choose exactly k indices from the array and compute a score based on those choices.

The score is defined as the sum of nums1 at the chosen indices multiplied by the minimum value of nums2 at those same indices. Formally: score = (sum of nums1[i] for chosen i) * (min of nums2[i] for chosen i). You want to maximize this score.

At first glance it looks like a two-dimensional optimization — you have to balance the sum of nums1 values against how low the minimum of nums2 values drops. A brute-force approach checking every combination of k indices would be O(n choose k), which is far too slow.

The key insight is to fix the minimum of nums2. If we sort all index pairs by nums2 in descending order, then as we scan left to right, each new element we process has the current smallest nums2 value seen so far. That element becomes the definitive minimum for any group we form using it.

With the minimum of nums2 fixed at each step, we want to maximize the sum of nums1 over k elements. We maintain a min-heap of size k that always holds the k largest nums1 values seen so far. The heap lets us efficiently evict the smallest nums1 value when we add a new candidate and the heap exceeds size k.

This reduces the problem to a single O(n log n) sort followed by O(n log k) heap operations — a dramatic improvement over brute force. The score at each step is the current heap sum multiplied by the current nums2 value, and we track the running maximum.

The algorithm pairs nums1[i] and nums2[i], then sorts the pairs by nums2 descending. It uses a min-heap to track the k largest nums1 values seen so far, along with a running sum of those values.

For the first k elements, we push each nums1 value into the heap and add it to the running sum. No score is recorded yet because we need exactly k elements. Starting from the (k+1)th element onward, we push the new nums1 value, add it to the sum, then pop the heap minimum and subtract it — maintaining the heap at exactly size k.

After each operation from index k-1 onward, we compute score = running_sum * current_nums2 and update the global maximum. The final answer is the maximum score observed across all positions.

The sort step ensures that when we consider position i, nums2[i] is the smallest nums2 value among all pairs we have processed (indices 0 through i in sorted order). Any group of k indices that includes position i must use nums2[i] as its minimum — no way around it, because all earlier indices have larger nums2 values.

Given that the minimum is fixed at nums2[i], the only lever we control is the sum of nums1. A min-heap of size k gives us the k largest nums1 values seen so far in O(log k) time per operation. Because we try every possible nums2 minimum (every position in the sorted order), we exhaustively cover all candidate optimal subsets.

No valid k-element subset is ever skipped. Every subset has some element with the smallest nums2 — that element determines which iteration of our loop computes the score for that subset. The heap guarantees the best possible nums1 sum for that minimum, so the algorithm considers the best achievable score for every candidate minimum value.

Consider nums1 = [1, 3, 3, 2], nums2 = [2, 1, 3, 4], k = 3. After pairing and sorting by nums2 descending we get: [(2, 4), (3, 3), (1, 2), (3, 1)]. The first value in each pair is nums1, the second is nums2.

Processing the first k = 3 elements: add 2 (sum = 2), add 3 (sum = 5), add 1 (sum = 6). After the third element, score = 6 * 2 = 12. The heap contains [1, 2, 3] (min-heap).

Next element is (3, 1). Push 3 onto heap → heap = [1, 2, 3, 3], sum = 9. Pop min (1) → heap = [2, 3, 3], sum = 8. Score = 8 * 1 = 8. Maximum remains 12. The final answer is 12.

In Python, zip(nums1, nums2) creates the pairs, sorted(..., key=lambda x: -x[1]) sorts by nums2 descending, and heapq provides the min-heap. The total time complexity is O(n log n) for the sort plus O(n log k) for n heap operations each costing O(log k). Space complexity is O(k) for the heap.

In Java, you create a 2D array or list of pairs, sort with a lambda comparator on the nums2 column descending, and use a PriorityQueue as the min-heap. The logic is identical — push, check size, pop if over k, update max score.

Both implementations stay well within the constraints for n = 100,000. The sort dominates at O(n log n). The heap operations are O(n log k) which is at most O(n log n) in the worst case when k = n, but typically much faster for small k.

Maximum Subsequence Score belongs to a broader family of heap and greedy problems. Kth Largest Element in a Stream (LeetCode 703) introduces the min-heap-of-size-k pattern for online streaming inputs. Course Schedule III (LeetCode 630) uses a max-heap to greedily swap out the longest course when the total time budget is exceeded — a similar "keep the best k" idea.

Minimum Interval to Include Each Query (LeetCode 1851) combines sorting and a heap to answer range queries efficiently. The Smallest Number in Infinite Set (LeetCode 2336) and Find Median from Data Stream (LeetCode 295) further explore heap-based data structure design. Mastering the sort-then-heap pattern unlocks all of these.

The unifying theme is: when a problem involves selecting a subset to optimize a quantity, consider sorting by the factor that determines the "worst case" for that subset, then use a heap to greedily maximize or minimize the remaining factor. This pattern scales to O(n log n) and handles large n comfortably.