Solution: Find Subsequence of Length K with the Largest Sum
Let's solve the Find Subsequence of Length K with the Largest Sum problem using the Top K Elements pattern.
We'll cover the following
Statement
You are given an integer array nums
and an integer k
. Your task is to find a nums
of length k
that has the largest possible sum.
Constraints:
nums.length
nums[i]
k
nums.length
Solution
To solve this problem, we use a min heap to track the largest k
elements as we iterate through the array. This approach ensures that we always maintain the largest elements while discarding smaller ones. After populating the heap with the k
largest elements, we extract them into a list. Since the heap maintains no particular order related to the original indexes, we then sort the list by the original indexes of the elements to preserve the relative order of those k
elements in the input array. Finally, we extract the values from the sorted list and return them as the subsequence.
The steps of the algorithm are as follows:
Create an empty
minHeap
to store pairs of elements and their corresponding indexes.For each element in the
nums
array, perform the following:Push the current element and its index
i
as a tuple into theminHeap
usingminHeap.offer
.If the size of
minHeap
exceedsk
, then remove the smallest element from the heap usingminHeap.poll()
. This keeps only the largestk
elements.
After the loop finishes, the heap contains the
k
largest elements. However, since we need to return the subsequence in the same order as the original array, the elements in the heap are sorted based on their original indexes (a[1]
). This ensures that the output subsequence preserves the relative order fromnums
.The final
result
list is created by extracting only the element values (a[0]
) from the sorted list of tuples. This gives the subsequence with the largest sum of lengthk
, in the correct order.Return the
result
list containing thek
largest elements in their original order.
Let’s look at the following illustration to get a better understanding of the solution:
Level up your interview prep. Join Educative to access 80+ hands-on prep courses.