Maximum Subsequence Score — Solution in Python, Java & C++
Maximum Subsequence Score solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Maximum Subsequence Score is a medium coding problem on arrays, sorting and greedy, asked in Amazon, Google and Flipkart interviews.
- Difficulty: Medium
- Topics: Arrays, Sorting, Greedy, Heap
- Asked at: Amazon, Google, Flipkart
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Two arrays of the same length are given. Choose a subsequence of exactly k indices. Its score is the sum of the chosen nums1 values multiplied by the minimum of the chosen nums2 values.
Return the maximum score.
Example 1
Input: nums1 = [1,3,3,2], nums2 = [2,1,3,4], k = 3
Output: 12
Explanation: Indices 0, 2 and 3: `(1 + 3 + 2) × min(2, 3, 4) = 6 × 2`.
Example 2
Input: nums1 = [4,2,3,1,1], nums2 = [7,5,10,9,6], k = 1
Output: 30
Explanation: Index 2 alone: `3 × 10`.
Example 3
Input: nums1 = [1,1], nums2 = [5,5], k = 2
Output: 10
Constraints
n == nums1.length == nums2.length1 <= n <= 10000 <= nums1[i], nums2[j] <= 10001 <= k <= n
Hints for Maximum Subsequence Score
Hint 1
Fix which element supplies the minimum of
nums2— then every other pick must havenums2at least that large.Hint 2
Sort the indices by
nums2descending and sweep: at each step the current element is the minimum so far.Hint 3
Among the elements seen so far, keep the
klargestnums1values in a min-heap.
How to solve Maximum Subsequence Score
Sort by nums2 descending. Sweeping in that order, the element just added is the smallest nums2 among those considered, so it fixes the multiplier; the best sum is then simply the k largest nums1 values seen, which a size-k min-heap maintains.
Approach
- Sort the indices by
nums2, largest first. - Push each
nums1value onto a min-heap, tracking the running sum. - If the heap exceeds
k, pop the smallest and subtract it. - Once the heap holds exactly
k, scoresum × nums2[current]and keep the best.
Why it works
Sorting descending is what lets the multiplier be read off for free: every element already in the heap has a nums2 at least as large as the current one, so the current one is the minimum. Dropping the smallest nums1 when the heap overflows is safe because it can never be part of the best sum for this or any later multiplier.
Complexity
- Time —
O(n log n) - Space —
O(n)
Pitfalls
- The subsequence must hold exactly
kindices, so scores are only taken once the heap is full. - Sorting ascending by
nums2breaks the "current element is the minimum" invariant. - The products reach
10^6 × 10^3, so a 32-bit int is enough here but only just.
Reference solution
Python
from typing import List
import heapq
def maxScore(nums1: List[int], nums2: List[int], k: int) -> int:
order = sorted(range(len(nums1)), key=lambda i: -nums2[i])
heap = []
total = 0
best = 0
for i in order:
heapq.heappush(heap, nums1[i])
total += nums1[i]
if len(heap) > k:
total -= heapq.heappop(heap)
if len(heap) == k:
best = max(best, total * nums2[i])
return bestJava
public static int maxScore(int[] nums1, int[] nums2, int k) {
int n = nums1.length;
Integer[] order = new Integer[n];
for (int i = 0; i < n; i++) order[i] = i;
Arrays.sort(order, (a, b) -> nums2[b] - nums2[a]);
PriorityQueue<Integer> heap = new PriorityQueue<>();
long sum = 0, best = 0;
for (int i : order) {
heap.add(nums1[i]);
sum += nums1[i];
if (heap.size() > k) sum -= heap.poll();
if (heap.size() == k) best = Math.max(best, sum * nums2[i]);
}
return (int) best;
}C++
int maxScore(vector<int>& nums1, vector<int>& nums2, int k) {
int n = (int) nums1.size();
vector<int> order(n);
for (int i = 0; i < n; i++) order[i] = i;
sort(order.begin(), order.end(), [&](int a, int b) { return nums2[a] > nums2[b]; });
priority_queue<int, vector<int>, greater<int>> heap;
long long sum = 0, best = 0;
for (int i : order) {
heap.push(nums1[i]);
sum += nums1[i];
if ((int) heap.size() > k) {
sum -= heap.top();
heap.pop();
}
if ((int) heap.size() == k) best = max(best, sum * nums2[i]);
}
return (int) best;
}JavaScript
var maxScore = function(nums1, nums2, k) {
var n = nums1.length, i;
var order = [];
for (i = 0; i < n; i++) order.push(i);
order.sort(function(a, b) { return nums2[b] - nums2[a]; });
var heap = [];
var push = function(v) {
heap.push(v);
var j = heap.length - 1;
while (j > 0) {
var p = (j - 1) >> 1;
if (heap[p] <= heap[j]) break;
var t = heap[p]; heap[p] = heap[j]; heap[j] = t;
j = p;
}
};
var pop = function() {
var top = heap[0];
var last = heap.pop();
if (heap.length > 0) {
heap[0] = last;
var j = 0;
for (;;) {
var l = 2 * j + 1, r = l + 1, s = j;
if (l < heap.length && heap[l] < heap[s]) s = l;
if (r < heap.length && heap[r] < heap[s]) s = r;
if (s === j) break;
var t = heap[s]; heap[s] = heap[j]; heap[j] = t;
j = s;
}
}
return top;
};
var sum = 0, best = 0;
for (var t2 = 0; t2 < order.length; t2++) {
var idx = order[t2];
push(nums1[idx]);
sum += nums1[idx];
if (heap.length > k) sum -= pop();
if (heap.length === k) {
var score = sum * nums2[idx];
if (score > best) best = score;
}
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms