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 i0, i1, ..., ik - 1, your score is defined as:
nums1 multiplied with the minimum of the selected elements from nums2.(nums1[i0] + nums1[i1] +...+ nums1[ik - 1]) * min(nums2[i0] , nums2[i1], ... ,nums2[ik - 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.length1 <= n <= 1050 <= nums1[i], nums2[j] <= 1051 <= k <= nProblem Overview: You are given two arrays nums1 and nums2 and an integer k. Choose exactly k indices such that the score (sum of selected nums1) * (minimum selected nums2) is maximized. The challenge is balancing a large sum from nums1 while keeping the minimum value from nums2 as high as possible.
Approach 1: Sorting with Priority Queue (O(n log n) time, O(k) space)
The key observation: if a value from nums2 becomes the minimum of the chosen subsequence, then every other selected element must have nums2 greater than or equal to it. Sort pairs (nums1[i], nums2[i]) in descending order of nums2. As you iterate, treat the current nums2 as the minimum candidate. Maintain a min-heap of the largest k values from nums1 and track their running sum. Each time the heap reaches size k, compute the score using the current nums2. The heap ensures you always keep the best k contributors to the sum while iterating through decreasing minimum values. This approach combines sorting, greedy selection, and a priority queue to efficiently explore all valid minimum candidates.
Approach 2: Divide and Conquer (Optimal Subsequence Selection) (O(n log n) time, O(n) space)
Another way to think about the problem is recursively splitting the candidate range of indices after sorting by nums2. Each segment represents a potential range where a specific nums2 value acts as the minimum. Within each segment, select the best k contributors from nums1 and propagate partial results upward. The divide-and-conquer structure reduces repeated work by reusing partial sums and candidate sets across recursive segments. While the complexity remains O(n log n), this approach is useful when implementing language-specific optimizations or when integrating with segment-based selection techniques.
Recommended for interviews: The sorting + priority queue solution is the expected answer. It demonstrates strong algorithmic intuition: reduce the problem by fixing the minimum nums2, then greedily maximize the sum using a heap. Interviewers typically want to see the insight that sorting by nums2 converts the "minimum constraint" into a linear scan.
In this approach, the idea is to pair up elements of nums1 and nums2 into tuples. Then, sort these pairs by nums2 in descending order. This way, we process elements with higher values in nums2 first. Using a priority queue (min-heap), we can efficiently keep track of the k largest nums1 values, which we use to calculate the score. The maximum score is computed by iterating through potential minimums, maintaining the current sum of the largest k values seen so far.
The solution sorts nums2 together with nums1. It processes from the largest nums2 value, maintaining a sum and a priority queue to track the largest k values of nums1. The score is calculated as the product of this sum and the current nums2 value in the loop, updating the maximum score as needed.
Time Complexity: O(n log n) due to sorting and heap operations.
Space Complexity: O(k) for the min-heap storing k elements.
This approach emphasizes efficient subsequence selection by partitioning the array. Divide the array in such a way that potential results can be directly computed without redundant calculations. Use recursion to evaluate possible subsequences efficiently.
The Java implementation uses List to manage pairs and utilizes the built-in sorting method for ordering. It implements similar logic using priority queues to track k largest elements for scoring.
Java
JavaScript
Time Complexity: O(n log n) primary by sorting and heap operations.
Space Complexity: O(k) for the priority queue.
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.
The time complexity is O(n times log n), and the space complexity is O(n). Here, n is the length of the array nums1.
| Approach | Complexity |
|---|---|
| Sorting with Priority Queue | Time Complexity: O(n log n) due to sorting and heap operations. |
| Divide and Conquer (Optimal Subsequence Selection) | Time Complexity: O(n log n) primary by sorting and heap operations. |
| Sorting + Priority Queue (Min Heap) | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting with Priority Queue | O(n log n) | O(k) | General optimal solution; standard interview approach combining sorting and heap |
| Divide and Conquer Subsequence Selection | O(n log n) | O(n) | Useful for recursive or segment-based implementations where candidate ranges are processed independently |
Maximum Subsequence Score - Leetcode 2542 - Python • NeetCodeIO • 33,051 views views
Watch 9 more video solutions →Practice Maximum Subsequence Score with our built-in code editor and test cases.
Practice on FleetCode