We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Subsequence Score

Number: 2636

Difficulty: Medium

Paid? No

Companies: Amazon, Google, Adobe, DE Shaw

Problem Description

Given two 0-indexed integer arrays, nums1 and nums2, of equal length n and an integer k, choose a subsequence of indices of length k. The score for a chosen subsequence is defined as the sum of the selected elements from nums1 multiplied by the minimum of the corresponding elements from nums2. The goal is to return the maximum possible score.

Key Insights

  • The score is determined by both the sum of selected nums1 elements and the minimum of the selected nums2 elements.
  • Sorting pairs of (nums2, nums1) in descending order by their nums2 values lets you control the minimum value in any selected group.
  • By iterating through these sorted pairs, each candidate's nums2 becomes the current “minimum” in the candidate group.
  • Maintain a min-heap (priority queue) for the k highest nums1 values encountered so far to maximize the sum.
  • When the heap size exceeds k, remove the smallest nums1 value to keep only the k best contributions.
  • Calculate the score as (current sum of heap) * (current nums2) each time the heap size equals k, and update the maximum score.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting and O(n log k) for heap operations, resulting overall in O(n log n). Space Complexity: O(n) for storing pairs and O(k) for the heap.

Solution

The solution involves first pairing elements from nums2 and nums1 and then sorting these pairs in descending order based on nums2. This ensures that as you iterate, the current nums2 value is the minimum for the candidate subsequence. A min-heap is used to always maintain the k largest nums1 values encountered so far. By iterating through the sorted pairs, you update a running sum of nums1 values and calculate the score whenever exactly k elements have been selected. The maximum score found during the process is returned as the solution.

Code Solutions

import heapq

def maxScore(nums1, nums2, k):
    # Create pairs of (nums2, nums1) and sort in descending order by nums2
    pairs = [(n2, n1) for n1, n2 in zip(nums1, nums2)]
    pairs.sort(key=lambda x: -x[0])
    
    min_heap = []  # Min-heap to maintain the largest k nums1 values
    current_sum = 0
    max_score = 0
    
    # Iterate through sorted pairs
    for n2, n1 in pairs:
        heapq.heappush(min_heap, n1)
        current_sum += n1
        
        # Ensure the heap contains at most k elements
        if len(min_heap) > k:
            current_sum -= heapq.heappop(min_heap)
        
        # When we have exactly k elements, compute the score
        if len(min_heap) == k:
            max_score = max(max_score, current_sum * n2)
    
    return max_score

# Example usage:
nums1 = [1, 3, 3, 2]
nums2 = [2, 1, 3, 4]
k = 3
print("Maximum Subsequence Score:", maxScore(nums1, nums2, k))
← Back to All Questions