Maximum Subsequence Score

Problem Statement:-

You are given two 0-indexed integer arrays nums1 and nums2 of equal length n and a positive integer k. You must choose a subsequence of indices from nums1 of length k.

For chosen indices i<sub>0</sub>, i<sub>1</sub>, ..., i<sub>k - 1</sub>, your score is defined as:

• The sum of the selected elements from nums1 multiplied with the minimum of the selected elements from nums2.

• It can defined simply as: (nums1[i<sub>0</sub>] + nums1[i<sub>1</sub>] +...+ nums1[i<sub>k - 1</sub>]) * min(nums2[i<sub>0</sub>] , nums2[i<sub>1</sub>], ... ,nums2[i<sub>k - 1</sub>]).

Return the maximum possible score.

A subsequence of indices of an array is a set that can be derived from the set {0, 1, ..., n-1} by deleting some or no elements.

Link: https://leetcode.com/problems/maximum-subsequence-score/description/

Problem Explanation with examples:-

Example 1

Input: nums1 = [1,3,3,2], nums2 = [2,1,3,4], k = 3
Output: 12
Explanation: 
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
Explanation: 
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 <= 10<sup>5</sup>

• 0 <= nums1[i], nums2[j] <= 10<sup>5</sup>

• 1 <= k <= n

Intuition:-

• Here DP won't work because the constraints are too high and we won't get too many overlapping subproblems.

• A greedy approach with respect to the first array would be sufficient if we sort the second array in descending order.

• We need to maximize the sum of the first array and the product of the second array. So first of all we will sort the 2nd array in descending order and keep checking what is the maximum sum possible if we take the current element of the 2nd array as the minimum.

• For keeping only k elements, we will use a min heap so that whenever the size of the heap becomes greater than k, we will pop the minimum element from the heap.

• We will keep a running sum of the elements in the heap and multiply it with the current element of the 2nd array and update the answer.

Solution:-

• Create an array of pairs of nums1 and nums2 and sort it in descending order of nums2.

• Create a min heap and a variable sm to keep track of the sum of the elements in the heap. Also, create a variable ans to keep track of the answer.

• Iterate over the array of pairs and add the current element of nums1 to sm and push it to the heap. If the size of the heap becomes greater than k, pop the minimum element from the heap and subtract it from sm.

• If the size of the heap becomes equal to k, update the answer by multiplying sm with the current element of nums2.

• Return the answer.

Code:-

JAVA Solution

class Solution {
    public int maxScore(int[] nums1, int[] nums2, int k) {
        int[][] pairs = new int[nums1.length][2];
        for (int i = 0; i < nums1.length; i++) {
            pairs[i][0] = nums1[i];
            pairs[i][1] = nums2[i];
        }

        Arrays.sort(pairs, new Comparator<int[]>() {
            public int compare(int[] a, int[] b) {
                return b[1] - a[1];
            }
        });

        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        int sum = 0;
        int ans = 0;

        for (int[] pair : pairs) {
            sum += pair[0];
            minHeap.offer(pair[0]);
            if (minHeap.size() > k) {
                int n1Pop = minHeap.poll();
                sum -= n1Pop;
            }
            if (minHeap.size() == k) {
                ans = Math.max(ans, sum * pair[1]);
            }
        }
        return ans;
    }
}

Python Solution

class Solution:
    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:
        pairs = [(n1,n2) for n1,n2 in zip(nums1,nums2)]
        pairs.sort(key=lambda x: x[1], reverse=True)

        minHeap = []
        sm = 0
        ans = 0

        for n1,n2 in pairs:
            sm += n1
            heapq.heappush(minHeap, n1)
            if len(minHeap) > k:
                n1Pop = heapq.heappop(minHeap)
                sm -= n1Pop
            if len(minHeap) == k:
                ans = max(ans, sm*n2)

        return ans

Complexity Analysis:-

TIME:-

The time complexity of add method is O(n log n), where n is the length of the input arrays nums1 and nums2. This is because of the sorting operation on the pairs array.

SPACE:-

The space complexity is O(n), where n is the length of the input arrays nums1 and nums2. This is due to the additional space used to store the pairs array and the minHeap priority queue.

References:-

• Greedy

• Heap

Connect with me:-

• Twitter

• Github

• LinkedIn