You are given an integer array nums and an integer k. You want to find a subsequence of nums of length k that has the largest sum.
Return any such subsequence as an integer array of length k.
A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.
Example 1:
Input: nums = [2,1,3,3], k = 2 Output: [3,3] Explanation: The subsequence has the largest sum of 3 + 3 = 6.
Example 2:
Input: nums = [-1,-2,3,4], k = 3 Output: [-1,3,4] Explanation: The subsequence has the largest sum of -1 + 3 + 4 = 6.
Example 3:
Input: nums = [3,4,3,3], k = 2 Output: [3,4] Explanation: The subsequence has the largest sum of 3 + 4 = 7. Another possible subsequence is [4, 3].
Constraints:
1 <= nums.length <= 1000-105 <= nums[i] <= 1051 <= k <= nums.lengthProblem Overview: Given an integer array nums and an integer k, return a subsequence of length k with the largest possible sum. The subsequence must preserve the original order of elements in the array.
The key detail: you want the k largest values, but you must output them in the same relative order they appeared in the original array. That means you cannot simply sort and return the top elements; you must track their indices and restore the order.
Approach 1: Sorting and Selecting Top K Elements (O(n log n) time, O(n) space)
Pair every element with its index, then sort these pairs by value in descending order. After sorting, take the first k elements because they contribute the largest possible sum. These elements are not necessarily in the correct subsequence order, so sort the selected k pairs again by their original indices. Finally, extract the values in that order to produce the valid subsequence.
This approach is straightforward and easy to implement using standard sorting. The extra index sorting step ensures the subsequence constraint is preserved. For most interview scenarios, this method is perfectly acceptable and easy to reason about.
Approach 2: Using Priority Queue (Min-Heap) (O(n log k) time, O(k) space)
Maintain a min-heap that stores at most k elements. As you iterate through the array, push each element along with its index into the heap. If the heap size exceeds k, remove the smallest value. This guarantees the heap always contains the k largest elements seen so far.
Once the scan finishes, the heap contains exactly the elements forming the maximum-sum subsequence. Since heap order does not match the original array order, extract the elements and sort them by index before building the final result. This method leverages a priority queue to avoid sorting the entire array and reduces complexity when k is much smaller than n.
Recommended for interviews: The sorting solution clearly demonstrates the insight that the answer consists of the k largest values while preserving indices. The min-heap approach is more scalable with O(n log k) time and shows stronger understanding of priority queues and optimization techniques.
Approach: Sort the array of numbers based on their values while remembering their original indices. Then, select the top k elements with the largest values and use their indices to construct the subsequence from the original array.
This approach involves two main steps: sorting the array elements along with their original indices and selecting the largest k elements from this sorted structure. Once the top k elements are found, maintain their original order by using the stored indices.
This program sorts the array based on their values while keeping track of the original indices using a struct. The qsort function is utilized for sorting. After sorting, the top k elements are selected and arranged in the order they originally appeared in the input array.
Time Complexity: O(n log n), due to sorting the elements.
Space Complexity: O(n), required for storing elements and indices.
Approach: Utilize a Min-Heap (or Priority Queue) to keep track of the k largest elements in the array. This method involves iterating through the array and inserting each element into the heap, ensuring that the heap size does not exceed k. If the heap exceeds k elements, the smallest element is removed. This approach keeps only the top k elements.
Finally, extract the elements from the heap and reconstruct the subsequence in the order they appear in the original array using their indices.
This solution utilizes a Min-Heap in Java's PriorityQueue. Each entry in the queue is a pair consisting of the number and its index. As we iterate through the array, we keep adding pairs to the heap and ensure its size remains k by removing the smallest element when necessary. The final list of indices is sorted and used to form the resultant subsequence.
Time Complexity: O(n log k), because each insertion and deletion in the heap takes log k time.
Space Complexity: O(k), for storing the k largest elements.
First, we create an index array idx, where each element is an index of the array nums. Then, we sort the index array idx based on the values in nums, with the sorting rule being nums[i] < nums[j], where i and j are two indices in the index array idx.
After sorting, we take the last k elements of the index array idx. These k elements correspond to the largest k elements in the array nums. Then, we sort these k indices to get the order of the largest k elements in the array nums.
The time complexity is O(n log n), and the space complexity is O(log n). Here, n is the length of the array.
| Approach | Complexity |
|---|---|
| Sorting and Selecting Top K Elements | Time Complexity: O(n log n), due to sorting the elements. Space Complexity: O(n), required for storing elements and indices. |
| Using Priority Queue (Min-Heap) | Time Complexity: O(n log k), because each insertion and deletion in the heap takes log k time. Space Complexity: O(k), for storing the k largest elements. |
| Sorting | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting and Selecting Top K Elements | O(n log n) | O(n) | Simple implementation when array size is moderate and readability matters |
| Priority Queue (Min-Heap) | O(n log k) | O(k) | Best when k is much smaller than n and you want a more optimal scalable solution |
Find Subsequence of Length K With the Largest Sum | 2 Approaches | Leetcode 2099 | codestorywithMIK • codestorywithMIK • 7,674 views views
Watch 9 more video solutions →Practice Find Subsequence of Length K With the Largest Sum with our built-in code editor and test cases.
Practice on FleetCode