#2542

Medium

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Maximum Subsequence Score

Maximize the score of a subsequence by selecting indices based on nums1 and nums2, using a greedy approach and sorting.

array greedy sorting heap priority queue

Problem Statement

You are given two arrays, nums1 and nums2, each of size n, and an integer k. You need to select a subsequence of length k from nums1. The score of the subsequence is calculated by summing the elements from nums1 at the selected indices, and multiplying this sum by the minimum element in nums2 at those same indices.

Your task is to return the maximum possible score that can be obtained. Sorting and greedy strategies play a crucial role in determining which indices to select in order to achieve the maximum score.

Examples

Example 1

Input: nums1 = [1,3,3,2], nums2 = [2,1,3,4], k = 3

Output: 12

The four possible subsequence scores are:

We choose the indices 0, 1, and 2 with score = (1+3+3) * min(2,1,3) = 7.
We choose the indices 0, 1, and 3 with score = (1+3+2) * min(2,1,4) = 6.
We choose the indices 0, 2, and 3 with score = (1+3+2) * min(2,3,4) = 12.
We choose the indices 1, 2, and 3 with score = (3+3+2) * min(1,3,4) = 8. Therefore, we return the max score, which is 12.

Example 2

Input: nums1 = [4,2,3,1,1], nums2 = [7,5,10,9,6], k = 1

Output: 30

Choosing index 2 is optimal: nums1[2] * nums2[2] = 3 * 10 = 30 is the maximum possible score.

Constraints

n == nums1.length == nums2.length
1 <= n <= 105
0 <= nums1[i], nums2[j] <= 105
1 <= k <= n

Solution Approach

Sorting the Pairs

Sort the indices based on the corresponding values from nums2 in descending order. By doing so, you can focus on the larger values of nums2 first, ensuring the smallest value in the subsequence is maximized.

Greedy Index Selection

After sorting, select the k largest values from nums1 at the sorted indices. This ensures that the sum of the selected values from nums1 is maximized, which contributes to a higher score when multiplied by the minimum of nums2.

Efficient Score Calculation with a Min-Heap

Use a min-heap to manage the selection of indices. By keeping track of the k largest values in nums1 efficiently, the final score can be computed as the sum of the largest elements multiplied by the smallest corresponding value from nums2.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on sorting the arrays, which is O(n log n), followed by operations to select the k largest values, which is O(k log k) using a heap. The space complexity is O(k) due to the heap storage for the selected indices.

What Interviewers Usually Probe

Candidate understands greedy algorithms and the importance of sorting in optimization problems.
Ability to implement a heap and manage subsequence selection efficiently.
Shows familiarity with complexity trade-offs between sorting and heap-based solutions.

Common Pitfalls or Variants

Common pitfalls

Not sorting nums2 properly, leading to a suboptimal selection of indices.
Incorrectly handling edge cases where k = 1 or k = n, which can change the dynamics of the subsequence.
Failing to utilize the min-heap effectively, leading to inefficient or incorrect subsequence score calculations.

Follow-up variants

Consider variations where nums1 and nums2 have different ranges of values.
Explore approaches where k is dynamically adjusted based on certain conditions.
Change the problem to use different operations, such as summing the elements instead of multiplying.

FAQ

What is the key pattern for solving the Maximum Subsequence Score problem?

The key pattern is a greedy choice plus invariant validation. This involves selecting the largest values from nums1 based on the sorted indices of nums2.

How do I maximize the score of the subsequence?

Maximizing the score involves sorting nums2, selecting the top k elements from nums1, and ensuring the minimum element from nums2 is used to compute the score.

Why is sorting necessary in this problem?

Sorting helps by ensuring that the largest values in nums2 correspond to the selected indices, allowing the subsequence score to be maximized efficiently.

What is the role of the heap in the solution?

The heap is used to efficiently select the k largest values from nums1 after sorting, ensuring that the correct subsequence is chosen to maximize the score.

How does GhostInterview assist in solving this problem?

GhostInterview helps by providing clear explanations of greedy strategies, sorting techniques, and heap usage, which are essential for solving the Maximum Subsequence Score problem.

terminal

Solution

Solution 1: Sorting + Priority Queue (Min Heap)

Sort nums2 and nums1 in descending order according to nums2, then traverse from front to back, maintaining a min heap. The heap stores elements from nums1, and the number of elements in the heap does not exceed $k$. At the same time, maintain a variable $s$ representing the sum of the elements in the heap, and continuously update the answer during the traversal process.

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:
        nums = sorted(zip(nums2, nums1), reverse=True)
        q = []
        ans = s = 0
        for a, b in nums:
            s += b
            heappush(q, b)
            if len(q) == k:
                ans = max(ans, s * a)
                s -= heappop(q)
        return ans

Continue Practicing

#2551 put marbles in bags #2497 maximum star sum of a graph #2611 mice and cheese