⚡Flashcard Drill➔
NeetCode #538LC-2542MediumHeap / Priority Queue
← Back to All Problems

#538 · #2542 · Maximum Subsequence Score(最大子序列的分数)

📌 Problem Statement & Constraints

You are given two arrays nums1 and nums2 of equal length, and an integer k. Choose k indices; the score is (sum of nums1 at those indices) * (minimum of nums2 at those indices). Return the maximum score. Constraints: 1 <= k <= nums1.length <= 10^5, 1 <= nums1[i], nums2[i] <= 10^5.

💡 Core Algorithmic Approaches

  1. Sort the pairs by nums2 descending, so the current pair's nums2 is the minimum among those considered so far.
  2. Maintain a min-heap of the k largest nums1 values seen so far, plus their sum.
  3. Once the heap has exactly k elements, the candidate score is sum * current_nums2.
  4. The heap's size cap is what keeps the sum maximal for a fixed minimum.

💻 Benchmark Python3 Implementation

class Solution:
    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:
        import heapq
        pairs = sorted(zip(nums2, nums1), reverse=True)   # by nums2 descending
        h = []                             # the k largest nums1 so far
        total = 0
        best = 0
        for n2, n1 in pairs:
            heapq.heappush(h, n1)
            total += n1
            if len(h) > k:
                total -= heapq.heappop(h)  # evict the smallest
            if len(h) == k:
                best = max(best, total * n2)   # n2 is the minimum so far
        return best

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n log n): the sort plus O(n) heap operations.
💾 Space Complexity
O(k) for the heap.

⚠️ Interview Pitfalls & Follow-ups

  • Sorting ascending by nums2: the current element must be the minimum, so the order is descending.
  • Computing the score before the heap reaches size k: fewer than k indices is not a valid selection.
  • Keeping a max-heap of nums1: the smallest must be evicted to maximise the sum, so a min-heap is required.
  • Trying to sort by nums1: the minimum of nums2 drives the ordering.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Heap / Priority Queue Problems