Skip to main content
Talentd

Maximum Subsequence Score - Solution & Explanation

MediumArrayGreedySortingHeap (Priority Queue)10 min readAsked at: Amazon, Microsoft, Google +2
Practice this problem

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 i0, i1, ..., ik - 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[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.length
  • 1 <= n <= 105
  • 0 <= nums1[i], nums2[j] <= 105
  • 1 <= k <= n

Approach Overview

Problem 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.

Approach 1: Sorting with Priority Queue

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.

Code

PythonC++

Python

C++

Complexity

Time Complexity: O(n log n) due to sorting and heap operations.
Space Complexity: O(k) for the min-heap storing k elements.

Try this approach in the editor →

Approach 2: Divide and Conquer (Optimal Subsequence Selection)

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.

Code

JavaJavaScript

Java

JavaScript

Complexity

Time Complexity: O(n log n) primary by sorting and heap operations.
Space Complexity: O(k) for the priority queue.

Try this approach in the editor →

Approach 3: Sorting + Priority Queue (Min Heap)

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.

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Sorting with Priority Queue

Time Complexity: O(n log n) due to sorting and heap operations.
Space Complexity: O(k) for the min-heap storing k elements.

Divide and Conquer (Optimal Subsequence Selection)

Time Complexity: O(n log n) primary by sorting and heap operations.
Space Complexity: O(k) for the priority queue.

Sorting + Priority Queue (Min Heap)—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Sorting with Priority QueueO(n log n)O(k)General optimal solution; standard interview approach combining sorting and heap
Divide and Conquer Subsequence SelectionO(n log n)O(n)Useful for recursive or segment-based implementations where candidate ranges are processed independently

Video Solution

Maximum Subsequence Score - Leetcode 2542 - Python • NeetCodeIO • 34,059 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Maximum Subsequence Score easy or hard?
Maximum Subsequence Score is rated Medium difficulty on LeetCode. The implementation is straightforward once the greedy insight is discovered, but identifying that sorting by nums2 converts the minimum constraint into a manageable iteration is the main challenge.
Maximum Subsequence Score Python/Java solution
In Python, the solution typically uses heapq as a min-heap while iterating over sorted pairs. Java implementations use PriorityQueue with the same logic. Both follow the pattern of sorting by nums2, maintaining k nums1 values, and updating the best score.
How to solve Maximum Subsequence Score in O(n)?
An O(n) solution is generally not feasible because the algorithm must consider ordering by nums2 values. Sorting the elements is necessary to evaluate candidates for the minimum multiplier, which introduces an O(n log n) lower bound in typical implementations.
What is the best approach for Maximum Subsequence Score?
The optimal approach sorts pairs by nums2 in descending order and uses a min-heap to maintain the k largest nums1 values seen so far. For each candidate minimum nums2, compute the score using the current sum of the heap. This greedy + priority queue strategy runs in O(n log n) time and O(k) space.
Is Maximum Subsequence Score asked at Google/Amazon/Meta?
Greedy problems involving heaps, sorting, and subsequence selection are common in interviews at companies like Google, Amazon, and Meta. This problem specifically tests the ability to transform a minimum constraint into a sorted greedy scan with a priority queue.
What data structure is used in Maximum Subsequence Score?
A min-heap (priority queue) is the core data structure. It keeps track of the k largest nums1 values while iterating through elements sorted by nums2. This allows efficient updates to the running sum used to compute the score.
What is the time complexity of Maximum Subsequence Score?
The optimal solution runs in O(n log n) time due to sorting the pairs and performing heap operations while scanning the array. The heap size is limited to k, so each insertion or removal costs O(log k). Space complexity is O(k).

Ready to solve this problem?

Practice Maximum Subsequence Score with our built-in code editor and test cases.

Practice on FleetCode
Previous

IPO

Next

Minimum Cost to Hire K Workers