Maximum Subsequence Score

Med

#2322Time: O(N^2 * logN). The outer loop runs `N` times. Inside, we iterate `N` times to build the `candidates` list (size up to `N`). Sorting this list takes `O(N log N)`. So, the total time is `N * (N + N log N) = O(N^2 log N)`.Space: O(N). In each iteration of the outer loop, we create a `candidates` list that can store up to `N` elements.1 company

Patterns

Greedy

Algorithms

Sorting

Data structures

Array Heap (Priority Queue)

Companies

DE Shaw

Prompt

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₀, i₁, ..., i_{k - 1}, 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₀] + nums1[i₁] +...+ nums1[i_{k - 1}]) * min(nums2[i₀] , nums2[i₁], ... ,nums2[i_{k - 1}]).

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.

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⁵
0 <= nums1[i], nums2[j] <= 10⁵
1 <= k <= n

Approaches

2 approaches with complexity analysis and trade-offs.

This approach iterates through every element in nums2 and considers it as the potential minimum for a valid subsequence. For each potential minimum nums2[i], it finds all other elements j where nums2[j] is greater than or equal to nums2[i]. From this group of candidates, it selects the k elements with the largest corresponding nums1 values to maximize the sum. The score is then calculated and compared with the maximum score found so far.

Algorithm

Initialize maxScore = 0.
For each index i from 0 to n-1:
- Let minVal = nums2[i].
- Create a list candidates of all nums1[j] where nums2[j] >= minVal.
- If candidates.size() < k, continue to the next i.
- Sort candidates in descending order.
- Calculate currentSum as the sum of the first k elements of candidates.
- Update maxScore = max(maxScore, currentSum * minVal).
Return maxScore.

Walkthrough

The core idea is to fix the minimum element of the nums2 subsequence and then find the best nums1 sum. By iterating through every possible choice for this minimum value, we can explore all valid scenarios. For each choice, we gather all eligible elements and pick the best k of them to maximize the sum part of the score formula.

Here's the step-by-step algorithm:

Initialize a variable maxScore to 0.
Iterate through each index i from 0 to n-1.
For each i, let minVal = nums2[i]. This minVal is our candidate for the minimum of the k chosen nums2 values.
Create a list of nums1 values for all indices j where nums2[j] >= minVal. These are the nums1 values we are allowed to choose from.
If the size of this list is less than k, we cannot form a subsequence of length k, so we continue to the next i.
If the list has k or more elements, sort it in descending order.
Calculate the sum of the first k elements from the sorted list. This gives the maximum possible sum of nums1 values for the chosen minVal.
Calculate the current score by multiplying this sum with minVal.
Update maxScore = max(maxScore, currentScore).
After iterating through all possible i, maxScore will hold the result.

1import java.util.ArrayList;2import java.util.Collections;3import java.util.List;4 5class Solution {6    public long maxScore(int[] nums1, int[] nums2, int k) {7        int n = nums1.length;8        long maxScore = 0;9 10        for (int i = 0; i < n; i++) {11            int currentMin = nums2[i];12            List<Integer> candidates = new ArrayList<>();13            for (int j = 0; j < n; j++) {14                if (nums2[j] >= currentMin) {15                    candidates.add(nums1[j]);16                }17            }18 19            if (candidates.size() < k) {20                continue;21            }22 23            Collections.sort(candidates, Collections.reverseOrder());24 25            long currentSum = 0;26            for (int l = 0; l < k; l++) {27                currentSum += candidates.get(l);28            }29 30            maxScore = Math.max(maxScore, currentSum * currentMin);31        }32 33        return maxScore;34    }35}

Complexity

Time

O(N^2 * logN). The outer loop runs `N` times. Inside, we iterate `N` times to build the `candidates` list (size up to `N`). Sorting this list takes `O(N log N)`. So, the total time is `N * (N + N log N) = O(N^2 log N)`.

Space

O(N). In each iteration of the outer loop, we create a `candidates` list that can store up to `N` elements.

Trade-offs

Pros

Conceptually simpler than the optimized approach.
Correctly breaks down the problem by fixing one variable (the minimum value).

Cons

Very inefficient due to repeated work. For each potential minimum, it rescans the entire array and re-sorts a potentially large list.
Will result in a "Time Limit Exceeded" (TLE) error for large inputs as specified in the constraints.

This is an optimized approach that avoids the repeated work of the previous method. The key idea is to process the elements in a specific order. We pair up nums1[i] and nums2[i] and sort these pairs based on nums2 values in descending order. By iterating through the sorted pairs, we can efficiently maintain the sum of the k largest nums1 values seen so far using a min-heap of size k.

Algorithm

Create pairs (nums1[i], nums2[i]).
Sort the pairs in descending order based on nums2 values.
Initialize a min-heap pq, currentSum = 0, maxScore = 0.
For each pair (n1, n2) in the sorted list:
- Add n1 to pq and currentSum.
- If pq.size() > k, remove the smallest element: currentSum -= pq.poll().
- If pq.size() == k, calculate score: maxScore = max(maxScore, currentSum * n2).
Return maxScore.

Walkthrough

The score is (sum of k nums1 elements) * (min of k nums2 elements). If we fix the min of k nums2 elements to be m, we should choose k elements whose nums2 values are all at least m, and whose nums1 sum is maximized. This means we should pick the k largest nums1 values from the pool of eligible elements.

To do this efficiently, we can iterate through all possible values of m. The possible values for m are the elements of nums2. Let's process these m values from largest to smallest.

The algorithm is as follows:

Create an array of pairs, where each pair contains (nums1[i], nums2[i]).
Sort this array of pairs in descending order based on the nums2 values. This ensures that when we iterate through the pairs, the nums2 value of the current pair is a candidate for the minimum, and all previously seen elements have a nums2 value greater than or equal to it.
Initialize a min-heap (PriorityQueue in Java) to keep track of the k largest nums1 values encountered so far. Also, initialize currentSum to track the sum of elements in the heap and maxScore to 0.
Iterate through the sorted pairs (n1, n2): a. Add the current nums1 value, n1, to the min-heap and to currentSum. b. If the heap's size exceeds k, it means we have k+1 elements. To maintain the k largest, we must remove the smallest element. We poll from the min-heap (which removes the smallest element) and subtract it from currentSum. c. Once the heap's size reaches k, we have a valid group of k elements. The sum of their nums1 values is currentSum. The minimum of their nums2 values is the current n2 (due to our sorting). d. Calculate the score currentSum * n2 and update maxScore if it's larger.
After the loop, maxScore holds the maximum possible score.

1import java.util.Arrays;2import java.util.PriorityQueue;3 4class Solution {5    public long maxScore(int[] nums1, int[] nums2, int k) {6        int n = nums1.length;7        int[][] pairs = new int[n][2];8        for (int i = 0; i < n; i++) {9            pairs[i][0] = nums1[i];10            pairs[i][1] = nums2[i];11        }12 13        // Sort pairs by nums2 in descending order14        Arrays.sort(pairs, (a, b) -> b[1] - a[1]);15 16        // Min-heap to store the k largest nums1 values17        PriorityQueue<Integer> minHeap = new PriorityQueue<>(k);18        long currentSum = 0;19        long maxScore = 0;20 21        for (int i = 0; i < n; i++) {22            int n1 = pairs[i][0];23            int n2 = pairs[i][1];24 25            minHeap.add(n1);26            currentSum += n1;27 28            if (minHeap.size() > k) {29                currentSum -= minHeap.poll();30            }31 32            if (minHeap.size() == k) {33                maxScore = Math.max(maxScore, currentSum * n2);34            }35        }36 37        return maxScore;38    }39}

Complexity

Time

O(N log N). Sorting the pairs takes `O(N log N)`. The loop runs `N` times, and each heap operation (add/poll) takes `O(log K)`. So the loop takes `O(N log K)`. The total complexity is dominated by sorting, resulting in `O(N log N)`.

Space

O(N). We need `O(N)` space to store the pairs for sorting. The min-heap requires `O(K)` space. Thus, the total space complexity is `O(N + K) = O(N)`.

Trade-offs

Pros

Highly efficient and passes the time limits for the given constraints.
Clever use of sorting and a min-heap to avoid re-computation. By processing elements in order of decreasing nums2 values, we can maintain the sum of the top k nums1 values incrementally.

Cons

The logic is more complex to understand compared to the brute-force approach.
Requires extra space for storing pairs, which could be a concern for extremely large N if memory is severely constrained.

Solutions

Solution

1class Solution {2public3  long maxScore(int[] nums1, int[] nums2, int k) {4    int n = nums1.length;5    int[][] nums = new int[n][2];6    for (int i = 0; i < n; ++i) {7      nums[i] = new int[]{nums1[i], nums2[i]};8    }9    Arrays.sort(nums, (a, b)->b[1] - a[1]);10    long ans = 0, s = 0;11    PriorityQueue<Integer> q = new PriorityQueue<>();12    for (int i = 0; i < n; ++i) {13      s += nums[i][0];14      q.offer(nums[i][0]);15      if (q.size() == k) {16        ans = Math.max(ans, s * nums[i][1]);17        s -= q.poll();18      }19    }20    return ans;21  }22}

1class Solution {2public:3  long long maxScore(vector<int> &nums1, vector<int> &nums2, int k) {4    int n = nums1.size();5    vector<pair<int, int>> nums(n);6    for (int i = 0; i < n; ++i) {7      nums[i] = {-nums2[i], nums1[i]};8    }9    sort(nums.begin(), nums.end());10    priority_queue<int, vector<int>, greater<int>> q;11    long long ans = 0, s = 0;12    for (auto &[a, b] : nums) {13      s += b;14      q.push(b);15      if (q.size() == k) {16        ans = max(ans, s * -a);17        s -= q.top();18        q.pop();19      }20    }21    return ans;22  }23};

1class Solution:2    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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem