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
- Sort the pairs by
nums2descending, so the current pair'snums2is the minimum among those considered so far. - Maintain a min-heap of the
klargestnums1values seen so far, plus their sum. - Once the heap has exactly
kelements, the candidate score issum * current_nums2. - 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 thankindices 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 ofnums2drives the ordering.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.