Maximum Subsequence Score

How it works

This is a space-optimized version that packs both values into a single 64-bit integer. Since the problem constraints allow values up to 10^5, we can use bit shifting to combine nums2 (upper bits) and nums1 (lower bits). Sorting these combined values gives us the same ordering as sorting by nums2, and we can extract both values using bitwise operations.

Steps

1. For each index, create a combined value: (nums2[i] << 30) | nums1[i].
2. Sort the combined array in descending order (sorts by nums2 primarily).
3. Process each combined value:
   • Extract nums1 and nums2 using bit operations.
   • Add nums1 to heap and sum; remove smallest if heap exceeds k.
   • When heap has exactly k elements, calculate and track maximum score.
4. Return the maximum score.

Complexity

• Time complexity: O(n log n)
• Space complexity: O(n)

Things to watch for

Using a Max-Heap Instead of a Min-Heap

To maximize the sum of k elements from nums1, you need to keep the k largest values seen so far. This requires a min-heap so you can efficiently remove the smallest element when the heap exceeds size k. Using a max-heap makes it impossible to efficiently evict the smallest element, leading to incorrect tracking of the top k values.

Forgetting to Sort by nums2 in Descending Order

The algorithm relies on processing elements in decreasing order of nums2 values so that each new element becomes the new minimum. If you sort in ascending order or forget to sort entirely, the minimum tracking breaks and the score calculation becomes incorrect.

Not Updating the Sum When Removing from the Heap

When the heap size exceeds k and you pop the smallest element, you must also subtract that element's value from your running sum. Forgetting to update the sum after removal causes it to include values no longer in the heap, producing inflated and incorrect scores.

from typing import List
import heapq

class Solution:
    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:
        n = len(nums1)
        arr = [(nums2[i] << 30) | nums1[i] for i in range(n)]
        arr.sort(reverse=True)

        minHeap = []
        n1Sum = 0
        res = 0

        for num in arr:
            n1, n2 = num & ((1 << 30) - 1), num >> 30
            n1Sum += n1
            heapq.heappush(minHeap, n1)

            if len(minHeap) > k:
                n1Sum -= heapq.heappop(minHeap)

            if len(minHeap) == k:
                res = max(res, n1Sum * n2)

        return res

class Solution {
public:
    long long maxScore(vector<int>& nums1, vector<int>& nums2, int k) {
        int n = nums1.size();
        vector<long long> arr(n);
        for (int i = 0; i < n; i++) {
            arr[i] = ((long long) nums2[i] << 30) | nums1[i];
        }

        sort(arr.rbegin(), arr.rend());
        priority_queue<int, vector<int>, greater<int>> minHeap;
        long long n1Sum = 0, res = 0;

        for (long long& num : arr) {
            int n1 = num & ((1LL << 30) - 1);
            int n2 = num >> 30;
            n1Sum += n1;
            minHeap.push(n1);

            if (minHeap.size() > k) {
                n1Sum -= minHeap.top();
                minHeap.pop();
            }
            if (minHeap.size() == k) {
                res = max(res, n1Sum * (long long)n2);
            }
        }

        return res;
    }
};