Coding Interview PatternsMaximum Subsequence Score
MediumTop K Elements

Maximum Subsequence Score

Explanation & Solution

Practice Problem

Description

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 of length k from nums1 and nums2.

The score of the chosen subsequence is defined as the sum of the selected elements from nums1 multiplied by the minimum of the selected elements from nums2.

Return the maximum possible score.

A subsequence of indices is a set of distinct indices chosen from [0, 1, ..., n - 1]. The elements selected by those indices from nums1 and nums2 are used to compute the score.

Examples

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

Output: 12

Explanation: Selecting indices 0, 2, and 3 gives nums1 values [1,3,2] (sum = 6) and nums2 values [2,3,4] (min = 2). Score = 6 * 2 = 12.

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

Output: 30

Explanation: Selecting index 2 gives nums1 value [3] (sum = 3) and nums2 value [10] (min = 10). Score = 3 * 10 = 30.

Input:nums1 = [2,1,14,12], nums2 = [11,7,13,6], k = 3
0
2
1
1
2
14
3
12
0
11
1
7
2
13
3
6

Output: 168

Explanation: Selecting indices 0, 2, and 3 gives nums1 values [2,14,12] (sum = 28) and nums2 values [11,13,6] (min = 6). Score = 28 * 6 = 168.

Constraints

  • n == nums1.length == nums2.length
  • 1 <= n <= 10^5
  • 0 <= nums1[i], nums2[i] <= 10^5
  • 1 <= k <= n

Approach

Top K Elements pattern

1. Sort Indices by nums2 in Descending Order

  • Create an array of indices [0, 1, ..., n-1] and sort them by their corresponding nums2 values in descending order.
  • This ensures that as we iterate, the current nums2[idx] is always the minimum among all nums2 values considered so far.

2. Initialize a Min-Heap and Running Sum

  • Use a min-heap of size at most k to track the largest k values from nums1 seen so far.
  • Maintain a running heapSum to efficiently compute the sum of elements in the heap.

3. Iterate Through Sorted Indices

  • For each index (in sorted order by nums2 descending):
  • Push nums1[idx] into the heap and add it to heapSum.
  • If the heap size exceeds k, pop the smallest element and subtract it from heapSum. This ensures we always keep the top-k largest nums1 values.

4. Compute Score When Heap Has Exactly k Elements

  • When the heap size equals k, compute the score as heapSum * nums2[idx].
  • Since indices are sorted by nums2 descending, nums2[idx] is guaranteed to be the minimum of all selected nums2 values.
  • Track the maximum score across all iterations.

5. Return the Maximum Score

  • After processing all indices, return the maximum score found.

Key Insight

By sorting indices by nums2 descending and iterating in that order, the current nums2 value is always the minimum for any subset of indices considered so far. The min-heap greedily maintains the top-k nums1 values to maximize the sum component. This transforms a combinatorial problem into a single-pass greedy algorithm.

Time
O(n log n) for sorting + O(n log k) for heap operations = **O(n log n)**
Space
O(n) for the indices array and O(k) for the heap = **O(n)**

Visualization

Input:
[1, 3, 3, 2], k = 3
10313223
—

No animation available

Left (L)Right (R)ConvergedDone
0 steps

Solution Code

Previous
Kth Smallest Element in a Sorted Matrix
Next
IPO